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

จากวิกิพีเดีย สารานุกรมเสรี
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
Iamion (คุย | ส่วนร่วม)
BotKung (คุย | ส่วนร่วม)
เก็บกวาด +แจ้งรอตรวจสอบด้วยบอต
บรรทัด 1: บรรทัด 1:
{{รอการตรวจสอบ}}
{{กล่องข้อมูล โครงสร้างข้อมูล
{{กล่องข้อมูล โครงสร้างข้อมูล
|ชื่อ=ต้นไม้แดงดำ (Red-Black Tree)
|ชื่อ=ต้นไม้แดงดำ (Red-Black Tree)
บรรทัด 26: บรรทัด 27:
เนื่องจากต้นไม้แดงดำ มีความสูงจำกัดแน่นอนเป็น log2n ถึง log4n จึงประกันเวลาการทำงานอยู่ใน [[สัญกรณ์โอใหญ่|O(log n)]]
เนื่องจากต้นไม้แดงดำ มีความสูงจำกัดแน่นอนเป็น log2n ถึง log4n จึงประกันเวลาการทำงานอยู่ใน [[สัญกรณ์โอใหญ่|O(log n)]]
== [[ประเภทข้อมูล]]ที่ใช้สร้างต้นไม้แดงดำ ==
== [[ประเภทข้อมูล]]ที่ใช้สร้างต้นไม้แดงดำ ==
ปมของต้นไม้แดงดำนั้นมีข้อมูลเพิ่มมาจากปมของต้นไม้ค้นหาแบบทวิืภาคแบบปกติคือจะมีการเพิ่มตัวแปรที่่เก็บ
ปมของต้นไม้แดงดำนั้นมีข้อมูลเพิ่มมาจากปมของต้นไม้ค้นหาแบบทวิภาคแบบปกติคือจะมีการเพิ่มตัวแปรที่เก็บ
สี แดงดำ อาจเป็น ตัวเลข หรือค่าความจริง ซึ่งใช้หน่วยจำเพิ่มขึ้นเพียงแค่หนึ่งบิตต่อหนึ่งปม
สี แดงดำ อาจเป็น ตัวเลข หรือค่าความจริง ซึ่งใช้หน่วยจำเพิ่มขึ้นเพียงแค่หนึ่งบิตต่อหนึ่งปม
== การสร้างบริการของต้นไม้แดงดำ ==
== การสร้างบริการของต้นไม้แดงดำ ==
บรรทัด 47: บรรทัด 48:




{{โครงสร้างข้อมูล}}


[[หมวดหมู่:โครงสร้างข้อมูลที่เป็นต้นไม้]]
[[หมวดหมู่:โครงสร้างข้อมูลที่เป็นต้นไม้]]
{{โครงสร้างข้อมูล}}


[[en:Red-black Tree]]
[[en:Red-black Tree]]

รุ่นแก้ไขเมื่อ 06:14, 11 มิถุนายน 2551

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

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

การลบสมาชิก

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

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

ดูเพิ่ม