ต้นไม้การค้นหาไบนารีที่สมดุลในโครงสร้างข้อมูล

ที่นี่เราจะมาดูกันว่าแผนผังการค้นหาไบนารีที่สมดุลคืออะไร ต้นไม้การค้นหาแบบไบนารี (BST) คือต้นไม้ไบนารีซึ่งมีองค์ประกอบน้อยกว่าที่ลูกด้านซ้ายและมีองค์ประกอบมากกว่าที่ลูกด้านขวา

ความซับซ้อนของเวลาเฉลี่ยสำหรับการค้นหาองค์ประกอบใน BST คือ O(log n) ขึ้นอยู่กับความสูงของแผนผังการค้นหาแบบไบนารี เพื่อรักษาคุณสมบัติของแผนผังการค้นหาแบบไบนารี บางครั้งทรีจะเอียง ต้นไม้เบ้จะเป็นแบบนี้ −

อันที่จริงนี่คือต้นไม้ แต่นี่ดูเหมือนเป็นรายการที่เชื่อมโยง สำหรับต้นไม้ชนิดนี้ เวลาในการค้นหาจะเป็น O(n) นั่นไม่ได้ผลสำหรับไบนารีทรี

เพื่อแก้ปัญหาเหล่านี้ เราสามารถสร้างต้นไม้ที่มีความสูงสมดุลได้ ดังนั้นต้นไม้จะไม่ถูกฆ่า อย่างเข้มแข็งเราจะสร้างสมดุล ดังนั้นแต่ละด้านของโหนดจะมีแผนผังย่อยซึ่งมีความสูงเกือบเท่ากัน

มีเทคนิคต่างๆ ในการทรงตัว บางส่วนของพวกเขาคือ −

• ต้นไม้ AVL

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

แบบฟอร์มที่สมดุลของความสูงจากตัวอย่างด้านบนจะเป็นดังนี้ −