ผลต่างระหว่างรุ่นของ "ต้นไม้แดงดำ"

ต้นไม้แดงดำ (Red-Black Tree)
	ตัวอย่างต้นไม้แดงดำ
ความสำคัญของลำดับ	เรียงจากน้อยไปมาก
การซ้ำกันของสมาชิก	ไม่อนุญาตให้ซ้ำ
เวลาที่ใช้ค้นหาตามค่า	O (log n)
เวลาที่ใช้ในการเข้าถึง	O (log n)
การทำให้ว่าง	ทำรากให้เป็น null
เวลาที่ใช้ทำให้ว่าง	O (1)
โครงสร้างต้นแบบ	ต้นไม้ค้นหาแบบทวิภาค,ต้นไม้ได้ดุล 2-3-4
โครงสร้างที่นำไปใช้	ต้นไม้แบบบี

เรียกดูประวัติแบบโต้ตอบ

← การแก้ไขก่อนหน้า การแก้ไขถัดไป →

เนื้อหาที่ลบ เนื้อหาที่เพิ่ม

เห็นภาพข้อความวิกิ

ในบรรทัด

รุ่นแก้ไขเมื่อ 01:20, 9 พฤษภาคม 2552

ต้นไม้แดงดำ (อังกฤษ: Red-Black Tree) เป็นต้นไม้ค้นหาแบบทวิภาคที่ประยุกต์แนวคิดมาจากต้นไม้ได้ดุล 2-3-4 ให้เป็นต้นไม้ค้นหาแบบทวิภาค โดยที่ปมของต้นไม้แดงดำจะมีการเก็บตัวแปรหนึ่ง มักเรียกว่าสีแดงและสีดำ มีสองสีซึ่งสามารถเก็บด้วยค่าความจริงหรือตัวแปรขนาดหนึ่งบิตได้ และทำให้ต้นไม้นี้ถูกเรียกชื่อว่า ต้นไม้แดงดำ

ลักษณะของต้นไม้แดงดำ

ต้นไม้แดงดำเป็นต้นไม้ที่นำแนวคิดมาจากต้นไม้ได้ดุล 2-3-4 โดยใช้ปมแบบสองทั้งหมด โดยสำหรับปมแบบ สามจะถูกแทนด้วยปมแบบสองสองปมเรียงกันโดยลูกใดลูกหนึ่งเป็นสีแดง ส่วนปมแบบสี่จะถูกแทนด้วยปมแบบ สองสามปมโดยลูกทั้งคู่เป็นสีแดง การเรียงแบบนี้จะทำให้เกิดกฎที่ว่า "ห้ามปมที่เป็นพ่อ-ลูกกันเป็นสีแดงเหมือนกัน"

จุดเด่นของต้นไม้แดงดำ

ต้นไม้แดงดำดัดแปลงมาจากต้นไม้ได้ดุล 2-3-4 ซึ่งถูกกันความสูงระหว่าง log2n ถึง log4n แต่เพียงขยายปมแบบสามกับปมแบบสี่เป็นปมแบบสอง ทำให้ความสูงอาจเพิ่มจากต้นไม้ได้ดุล 2-3-4 ที่สมมูลกันประมาณสองเท่า เพราะความสูงเพิ่มอีกหนึ่งเท่าเมื่อขยายปมแบบสามและสี่ให้เป็นเป็นปมแบบสอง ดังนั้นความสูงก็ยังอยู่ในช่วง log2n ถึง log4n

บริการที่มักจะมี

การเพิ่ม การลบ และการค้นหา

ความเร็วที่ใช้ในการทำงาน

เนื่องจากต้นไม้แดงดำ มีความสูงจำกัดแน่นอนเป็น log2n ถึง log4n จึงประกันเวลาการทำงานอยู่ใน O (log n)

ประเภทข้อมูลที่ใช้สร้างต้นไม้แดงดำ

ปมของต้นไม้แดงดำนั้นมีข้อมูลเพิ่มมาจากปมของต้นไม้ค้นหาแบบทวิภาคแบบปกติคือจะมีการเพิ่มตัวแปรที่เก็บ สี แดงดำ อาจเป็น ตัวเลข หรือค่าความจริง ซึ่งใช้หน่วยจำเพิ่มขึ้นเพียงแค่หนึ่งบิตต่อหนึ่งปม

การสร้างบริการของต้นไม้แดงดำ

การเพิ่มสมาชิก

การเพิ่มสมาชิกของต้นไม้แดงดำจะเลียนแบบการทำงานของต้นไม้ได้ดุล 2-3-4 ซึ่งมีการเปลี่ยนสมาชิกของปมให้สูงขึ้นไป หรือการแตกปม เหล่านี้สามารถแทนด้วยต้นไม้แดงดำด้วยวิธีการจัดการตามสมบัติของต้นไม้แดงดำที่ว่า "ห้ามปมที่เป็นพ่อ-ลูกกันเป็นสีแดงเหมือนกัน"และจัดการดังต่อไปนี้ได้

เพิ่มสมาชิกโดยใช้วิธีการเดียวกับต้นไม้ค้นหาแบบทวิภาคทั่วไป เพียงแต่ปมที่เพิ่มใหม่นี้ให้เป็นปมสีแดง
สำรวจว่าปมพ่อของปมใหม่ที่เพิ่มขึ้นเป็นสีแดงหรือไม่ ถ้าใช่ก็จะขัดกับสมบัติที่"ห้ามปมที่เป็นพ่อ-ลูกกันเป็นสีแดงเหมือนกัน"ก็จะทำได้สองวิธีดังนี้
1. การสลับสีสามปม ในกรณีที่มีการต่อในลักษณะคล้ายกับต่อปมแบบสี่ การสลับสีสามปมจะเสมือนการแตกปมในต้นไม้ได้ดุล2-3-4
2. การหมุนปมและสลับสีสามปม ในบางกรณีการสลับสีสามปมเฉยๆ ไม่อาจช่วยให้ถูกต้องกับสมบัติที่ว่า"ห้ามปมที่เป็นพ่อ-ลูกกันเป็นสีแดงเหมือนกัน" ดังนั้นการหมุนปมเท่านั้นจึงช่วยให้สมบัติถูกต้องแบบนี้จะสอดคล้องกับการเพิ่มข้อมูลในปมในต้นไม้ได้ดุล2-3-4

การลบสมาชิก

การค้นหาสมาชิก

การค้นหาสมาชิกนั้นสะดวกมากกว่าต้นไม้ได้ดุล2-3-4 เพราะใช้วิธีค้นหาแบบเดียวกับต้นไม้ค้นหาแบบทวิภาคได้

ดูเพิ่ม

@@ บรรทัด 1: / บรรทัด 1: @@
+{{ขาดอ้างอิง}}
-{{รอการตรวจสอบ}}
 {{กล่องข้อมูล โครงสร้างข้อมูล
-|ชื่อ=ต้นไม้แดงดำ (Red-Black Tree)
+| ชื่อ = ต้นไม้แดงดำ (Red-Black Tree)
-|ภาพ=[[ภาพ:Red-black tree example.svg|200px]]
+| ภาพ = [[ไฟล์:Red-black tree example.svg|200px]]
-|description=ตัวอย่าง[[ต้นไม้แดงดำ]]
+| description = ตัวอย่าง'''ต้นไม้แดงดำ'''
-|order=เรียงจากน้อยไปมาก
+| order = เรียงจากน้อยไปมาก
-|same=ไม่อนุญาตให้ซ้ำ
+| same = ไม่อนุญาตให้ซ้ำ
-|findi=
+| findi =
-|finde=O(log n)
+| finde = O (log n)
-|access=O(log n)
+| access = O (log n)
-|empty=ทำรากให้เป็น null
+| empty = ทำรากให้เป็น null
-|emptytime=O(1)
+| emptytime = O (1)
-|parent=[[ต้นไม้ค้นหาแบบทวิภาค]],[[ต้นไม้ได้ดุล 2-3-4]]
+| parent = [[ต้นไม้ค้นหาแบบทวิภาค]],[[ต้นไม้ได้ดุล 2-3-4]]
-|children=[[ต้นไม้แบบบี]]
+| children = [[ต้นไม้แบบบี]]
 }}
-'''ต้นไม้แดงดำ'''(Red-Black Tree) เป็น[[ต้นไม้ค้นหาแบบทวิภาค]]ที่ประยุกต์แนวคิดมาจาก[[ต้นไม้ได้ดุล 2-3-4]] ให้เป็นต้นไม้ค้นหาแบบทวิภาค โดยที่ปมของต้นไม้แดงดำจะมีการเก็บตัวแปรหนึ่ง มักเรียกว่าสีแดงและสีดำ มีสองสีซึ่งสามารถเก็บด้วยค่าความจริงหรือตัวแปรขนาดหนึ่ง[[บิต]]ได้ และทำให้ต้นไม้นี้ถูกเรียกชื่อว่า '''ต้นไม้แดงดำ'''
+'''ต้นไม้แดงดำ''' ({{lang-en|Red-Black Tree}}) เป็น[[ต้นไม้ค้นหาแบบทวิภาค]]ที่ประยุกต์แนวคิดมาจาก[[ต้นไม้ได้ดุล 2-3-4]] ให้เป็นต้นไม้ค้นหาแบบทวิภาค โดยที่ปมของต้นไม้แดงดำจะมีการเก็บตัวแปรหนึ่ง มักเรียกว่าสีแดงและสีดำ มีสองสีซึ่งสามารถเก็บด้วยค่าความจริงหรือตัวแปรขนาดหนึ่ง[[บิต]]ได้ และทำให้ต้นไม้นี้ถูกเรียกชื่อว่า '''ต้นไม้แดงดำ'''
 == ลักษณะของต้นไม้แดงดำ ==
 ต้นไม้แดงดำเป็นต้นไม้ที่นำแนวคิดมาจากต้นไม้ได้ดุล 2-3-4 โดยใช้ปมแบบสองทั้งหมด โดยสำหรับปมแบบ
@@ บรรทัด 25: / บรรทัด 25: @@
 * การเพิ่ม การลบ และการค้นหา
 == ความเร็วที่ใช้ในการทำงาน ==
-เนื่องจากต้นไม้แดงดำ มีความสูงจำกัดแน่นอนเป็น log2n ถึง log4n จึงประกันเวลาการทำงานอยู่ใน [[สัญกรณ์โอใหญ่|O(log n)]]
+เนื่องจากต้นไม้แดงดำ มีความสูงจำกัดแน่นอนเป็น log2n ถึง log4n จึงประกันเวลาการทำงานอยู่ใน [[สัญกรณ์โอใหญ่|O (log n)]]
 == [[ประเภทข้อมูล]]ที่ใช้สร้างต้นไม้แดงดำ ==
 ปมของต้นไม้แดงดำนั้นมีข้อมูลเพิ่มมาจากปมของต้นไม้ค้นหาแบบทวิภาคแบบปกติคือจะมีการเพิ่มตัวแปรที่เก็บ

ด ค ก แบบชนิดข้อมูลนามธรรมและโครงสร้างข้อมูล
แบบชนิดข้อมูลนามธรรม	คอลเลคชั่น รายการ เซต ต้นไม้ กองซ้อน แถวคอย แถวคอยสองหน้า แถวคอยลำดับความสำคัญ แถวลำดับแบบจับคู่
รายการ	แถวลำดับ รายการโยง แถวลำดับพลวัต
ต้นไม้	ต้นไม้แบบทวิภาค ต้นไม้ค้นหาแบบทวิภาค ทรีพ ต้นไม้แดงดำ ต้นไม้สเปลย์ ต้นไม้แบบที ต้นไม้สเคปโกท โร้ป ฮีป
แถวคอย	แถวคอย แถวคอยสองหน้า แถวคอยลำดับความสำคัญ
แถวลำดับแบบจับคู่	ตารางแฮช
ดูเพิ่ม	ฟังก์ชันแฮช ขั้นตอนวิธี สัญกรณ์โอใหญ่