แนะนำต้นไม้แดง - ดำ  


ระดับความยาก ยาก
ถามบ่อยใน อเมซอน CodeNation Facebook Google Uber
โครงสร้างข้อมูลขั้นสูง ต้นไม้ค้นหาแบบไบนารี ต้นไม้ไบนารี โครงสร้างข้อมูล ต้นไม้

Red Black Tree เป็นต้นไม้ไบนารีที่ปรับสมดุลในตัวเอง ในแผนภูมินี้ทุกโหนดจะเป็นโหนดสีแดงหรือโหนดสีดำ ในบทนำต้นไม้สีแดง - ดำนี้เราจะพยายามพูดถึงคุณสมบัติพื้นฐานทั้งหมด

สรรพคุณของต้นแดง - ดำ  

  1. ทุกโหนดจะแสดงเป็นสีแดงหรือสีดำ
  2. โหนดรากจะเป็นสีดำเสมอ
  3. โหนดสีแดงไม่สามารถมีแม่สีแดงหรือลูกสีแดง (เช่นไม่มีสองโหนดสีแดงอยู่ติดกัน)
  4. ทุกเส้นทางจากโหนดใด ๆ ไปยังลูกหลาน NIL ต้องมีโหนดสีดำจำนวนเท่ากัน

ตัวอย่างต้นไม้แดง - ดำที่ถูกต้องและไม่ถูกต้อง

แนะนำต้นไม้แดง - ดำหมุด

แนะนำต้นไม้แดง - ดำหมุด

การวิเคราะห์ความซับซ้อนของเวลา  

การดำเนินการ BST ทั้งหมดเช่นการค้นหาการแทรกการลบ ฯลฯ สามารถทำได้ในเวลา O (h) โดยที่ h คือความสูงของต้นไม้สีแดงดำและสำหรับ BST ที่สมดุลความสูงจะเป็นไปตามลำดับเสมอ บันทึก (n) [n-> จำนวนโหนด]

ค้นหา = O (บันทึก (n))
การแทรก = O (บันทึก (n))
การลบ = O (บันทึก (n))

ความสูงสีดำในต้นไม้สีแดง - ดำ  

ความสูงสีดำในต้นไม้สีแดงดำหมายถึงจำนวนโหนดสีดำบนเส้นทางที่เรียบง่าย (คุณไม่ได้เยี่ยมชมโหนดเดียวกันสองครั้ง) จากโหนดใด ๆ ไปยังใบไม้ (ซึ่งคือ NIL) มันแสดงด้วย bh (x)

ความสูงของต้นไม้แดง - ดำ  

แตกต่าง AVL ต้นไม้ความสมดุลของความสูงไม่เข้มงวดเท่า แต่ในต้นไม้สีแดง - ดำจำนวนการหมุนจะน้อยกว่าเมื่อเทียบกับต้นไม้ AVL
ความสูงของต้นไม้สีแดง - ดำ h <= 2 (log (n + 1)) {Base of log is 2} พิสูจน์ ทำไมความสูงของต้นไม้ RB จึงเป็น <= 2 log (n + 1)

ดูสิ่งนี้ด้วย
Recursion

เพื่อรักษาสมดุลของความสูงต้นไม้สีแดงดำใช้การเปลี่ยนสีและการปรับโครงสร้าง

คุณสามารถดูว่าต้นไม้ RB เปลี่ยนสีและปรับโครงสร้างตัวเองอย่างไร โปรดคลิกที่นี่เพื่ออ่านรายละเอียดเพิ่มเติม.

การเปลี่ยนสี

หมายถึงการเปลี่ยนสีของโหนดสีแดงเป็นสีดำและในทางกลับกันจะทำเมื่อใดก็ตามที่พี่น้องของแม่สีแดงของโหนดสีแดงเป็นสีแดง

แนะนำต้นไม้แดง - ดำหมุด

 

การปรับโครงสร้างหนี้

มันหมายถึงการหมุนของต้นไม้มันจะทำทุกครั้งที่ลูกแดงมีพ่อแม่สีแดงและลุงดำหรือลุง มีสี่กรณีในการปรับโครงสร้าง

  • ขวา
  • ซ้าย
  • ขวาซ้าย
  • ซ้ายขวา

หมุด

การใช้งาน

  • ใช้ในห้องสมุดในโลกแห่งความเป็นจริงเพื่อใช้ BST ที่ปรับสมดุลในตัวเอง
  • ใช้เป็น ทรีเซ็ต และ TreeMap ใน JAVA และชุดและแผนที่ใน C ++

ค้นหา

ต้นไม้สีแดง - ดำคือ BST ดังนั้นการค้นหาใน RBT จึงเหมือนกับการค้นหาใน BST ทุกประการสีของโหนดไม่สำคัญ