Разница в весе балансирующего дерева и высоте балансирующего дерева
Могут ли некоторые объяснить, в чем разница между балансирующим по дереву весом и балансирующим по высоте деревом?
АВЛ - балансирующее дерево
1 ответ
Сбалансированные по высоте деревья двоичного поиска требуют, чтобы высота левого и правого поддерева отличалась не более чем на единицу. Для сбалансированных по весу деревьев двоичного поиска требуется, чтобы количество узлов в левом и правом двоичном дереве поиска отличалось не более чем на один.
Помните, что высота отличается от количества узлов. По определению высота - самый длинный путь в дереве.
Например, если у нас есть BST, сбалансированный по высоте, он будет уравновешен, если высота левого поддерева отличается от высоты правого максимум на 1. Так как высота не определяет количество узлов только самой длинной траектории, это означает, что количество узлов в левом и правом поддеревьях может отличаться более чем на 1.
Общее правило Балансировка веса BST - для балансировки используется количество узлов в левом и правом поддеревьях. BST сбалансирован по высоте - для балансировки используется высота левого и правого поддеревьев.
Примечание: AVL - дерево выравнивания высоты.