LINUX.ORG.RU
Форум — Development  

Является ли бинарное дерево сбалансированным?

 ,


0

2

Нубский вопрос. Попробовал реализовать АВЛ-дерево. В качестве теста закидывал случайно перетасованные значения. На одном из прогонов получилось такое дерево. 

           9
    3            11
 1     6     10     13
0 2  5   8        12  16
    4   7
Лист 10 на два уровня выше листьев 4 и 7. Но при этом у любой вершины глубина левого поддерева не превышает глубины правого более чем 1 уровень. Это считается сбалансированным деревом? Если да, то получается что с ростом дерева разница в уровне отдельных листьев может продолжать увеличиваться?

★

Последнее исправление: Archer73 (всего исправлений: 1)
← На что лучше натравливать тайпчекер?
дерево двоичного поиска в ООП →

Это считается сбалансированным деревом?

Да.

Если да, то получается что с ростом дерева разница в уровне отдельных листьев может продолжать увеличиваться?

Нет. Первая же балансировка все исправит.

MuZHiK-2 ★★★★
()

Правильно, в достаточно большом АВЛ дереве разница между самым близким и самым далёким к корню листом может быть сколь угодно большая. Но всё равно не настолько большая, чтобы глубина дерева превысила логарифм от количества узлов. В этом и есть прелесть АВЛ: алгоритм балансировки значительно упрощается насколько можно, чтобы не испортить асимптотическую сложность.

const86 ★★★★★
()

У красно-черных деревьев, насколько понимаю, разница еще больше, чем у АВЛ, но асимптотически находится тоже в разумных пределах

dave ★★★★★
()
Последнее исправление: dave (всего исправлений: 1)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← На что лучше натравливать тайпчекер?
Development
дерево двоичного поиска в ООП →