Збалансоване бінарне дерево також відоме як збалансоване дерево за висотою. Він визначається як бінарне дерево, коли різниця між висотою лівого піддерева та правого піддерева не перевищує m, де m зазвичай дорівнює 1. Висота дерева – це кількість ребер на найдовшому шляху між кореневий вузол і листковий вузол.
Наведене вище дерево є a двійкове дерево пошуку . Двійкове дерево пошуку — це дерево, у якому кожен вузол ліворуч має нижче значення, ніж його батьківський вузол, а вузол правого боку має більше значення, ніж його батьківський вузол. У наведеному вище дереві n1 є кореневим вузлом, а n4, n6, n7 є листовими вузлами. Вузол n7 є найдальшим вузлом від кореневого вузла. n4 і n6 містять 2 ребра, і існують три ребра між кореневим вузлом і вузлом n7. Оскільки n7 є найдальшим від кореневого вузла; отже, висота вищезгаданого дерева дорівнює 3.
Тепер ми побачимо, чи збалансоване дерево вище чи ні. Ліве піддерево містить вузли n2, n4, n5 і n7, а праве піддерево містить вузли n3 і n6. Ліве піддерево має два листкові вузли, тобто n4 і n7. Є лише одне ребро між вузлом n2 і n4 і два ребра між вузлами n7 і n2; отже, вузол n7 є найдальшим від кореневого вузла. Висота лівого піддерева дорівнює 2. Праве піддерево містить лише один листовий вузол, тобто n6, і має лише одне ребро; тому висота правого піддерева дорівнює 1. Різниця між висотами лівого піддерева і правого піддерева дорівнює 1. Оскільки ми отримали значення 1, ми можемо сказати, що наведене вище дерево є деревом із збалансованою висотою. Цей процес обчислення різниці між висотами слід виконувати для кожного вузла, наприклад n2, n3, n4, n5, n6 і n7. Коли ми обробимо кожен вузол, то побачимо, що значення k не перевищує 1, тому ми можемо сказати, що наведене вище дерево є збалансованим бінарне дерево .
У наведеному вище дереві n6, n4 і n3 є листовими вузлами, де n6 є найдальшим вузлом від кореневого вузла. Три ребра існують між кореневим вузлом і листовим вузлом; отже, висота вищевказаного дерева дорівнює 3. Коли ми розглядаємо n1 як кореневий вузол, тоді ліве піддерево містить вузли n2, n4, n5 і n6, тоді як піддерево містить вузол n3. У лівому піддереві n2 є кореневим вузлом, а n4 і n6 є листовими вузлами. Серед n4 і n6 вузлів n6 є найдальшим вузлом від свого кореневого вузла, а n6 має два ребра; отже, висота лівого піддерева дорівнює 2. Праве піддерево має дочірні елементи ліворуч і праворуч; отже, висота правого піддерева дорівнює 0. Оскільки висота лівого піддерева дорівнює 2, а правого піддерева дорівнює 0, то різниця між висотою лівого піддерева та правого піддерева дорівнює 2. Згідно з визначенням, різниця між висотою лівого піддерева і правого піддерева не має бути більше 1. У цьому випадку різниця дорівнює 2, що більше 1; отже, наведене вище бінарне дерево є незбалансованим бінарним деревом пошуку.
Навіщо нам потрібне збалансоване бінарне дерево?
Давайте зрозуміємо необхідність збалансованого бінарного дерева на прикладі.
Наведене вище дерево є двійковим деревом пошуку, оскільки всі вузли лівого піддерева менші за батьківський вузол, а всі праві вузли піддерева більші за батьківський вузол. Припустімо, ми хочемо знайти значення 79 у наведеному вище дереві. Спочатку ми порівнюємо значення вузла n1 із 79; оскільки значення 79 не дорівнює 35 і воно більше за 35, тому ми переходимо до вузла n3, тобто 48. Оскільки значення 79 не дорівнює 48, а 79 більше за 48, тому ми рухаємося праворуч дочірній елемент 48. Значення правого дочірнього вузла 48 дорівнює 79, що дорівнює значенню для пошуку. Кількість переходів, необхідних для пошуку елемента 79, дорівнює 2, а максимальна кількість переходів, необхідних для пошуку будь-якого елемента, становить 2. Середній випадок для пошуку елемента - O(logn).
Наведене вище дерево також є бінарним деревом пошуку, оскільки всі вузли лівого піддерева менші за батьківський вузол, а всі праві вузли піддерева більші за батьківський вузол. Припустимо, ми хочемо знайти значення 79 у наведеному вище дереві. Спочатку ми порівнюємо значення 79 із вузлом n4, тобто 13. Оскільки значення 79 більше за 13, ми переходимо до правого дочірнього вузла 13, тобто n2 (21). Значення вузла n2 дорівнює 21, що менше за 79, тому ми знову рухаємося праворуч від вузла 21. Значення правого дочірнього вузла 21 дорівнює 29. Оскільки значення 79 більше за 29, ми рухаємося праворуч дочірній елемент вузла 29. Значення правого дочірнього вузла 29 становить 35, що менше за 79, тому ми переходимо до правого дочірнього вузла 35, тобто до 48. Значення 79 більше за 48, тому ми переходимо до правого дочірнього вузла вузла 48. Значення правого дочірнього вузла 48 дорівнює 79, що дорівнює значенню для пошуку. У цьому випадку кількість переходів, необхідних для пошуку елемента, дорівнює 5. У цьому випадку найгіршим є O(n).
Якщо кількість вузлів збільшується, формула, яка використовується в деревоподібній діаграмі1, є більш ефективною, ніж формула, використана в деревоподібній діаграмі2. Припустимо, кількість вузлів, доступних в обох вищевказаних деревах, становить 100 000. Для пошуку будь-якого елемента на деревоподібній діаграмі2 час, витрачений на 100 000 мкс, тоді як час, витрачений на пошук елемента на деревоподібній діаграмі, становить log(100 000), що дорівнює 16,6 мкс. Ми можемо спостерігати величезну різницю в часі між двома деревами вище. Отже, ми робимо висновок, що балансове бінарне дерево забезпечує пошук швидше, ніж структура даних лінійного дерева.