Балансираното двоично дърво е известно също като балансирано по височина дърво. Дефинира се като двоично дърво, когато разликата между височината на лявото поддърво и дясното поддърво е не повече от 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 µs, докато времето, необходимо за търсене на елемент в дървовидна диаграма, е log(100 000), което е равно на 16,6 µs. Можем да наблюдаваме огромната разлика във времето между горните две дървета. Следователно заключаваме, че балансираното двоично дърво осигурява търсене по-бързо от линейната дървовидна структура на данни.