B Tree - это самобалансирующееся дерево, подобное AVL-дереву. ЗДЕСЬ мы можем увидеть, как вращение влево и вправо используется для сохранения AVL дерево сбалансировано.
И ЗДЕСЬ - это ссылка, объясняющая вставку в B-дерево. Эта техника вставки не требует вращения, если я не ошибаюсь, чтобы дерево оставалось сбалансированным. А потому и выглядит проще.
Вопрос: Есть ли какой-либо подобный (или любой другой метод без использования вращений) для сохранения баланса avl-дерева?
Ответ и да и нет.
B-деревьям не нужно выполнять ротации, потому что у них есть некоторый резерв с тем, сколько разных ключей они могут упаковать в узел. По мере того, как вы добавляете все больше и больше ключей в B-дерево, вы можете избежать перекоса дерева, поглощая эти ключи в самих узлах.
У двоичных деревьев нет такой роскоши. Если вы вставите ключ в двоичное дерево, он увеличит высоту некоторой ветви в этом дереве на 1 во всех случаях, потому что этот ключ должен перейти в свой собственный узел. Вращение препятствует общему росту дерева, гарантируя, что, если некоторые ветви вырастут слишком сильно, эта высота перетасовывается к остальной части дерева.
У большинства сбалансированных BST есть своего рода стратегия ребалансировки, которая включает ротации, но не все. Одним из ярких примеров стратегии, которая напрямую не связана с ротацией, является дерево козлов отпущения, которое изменяет баланс вырывание огромных поддеревьев из главного дерева, их оптимальное восстановление и последующее приклеивание поддерева обратно к основному дереву. Этот подход технически не предполагает вращения и представляет собой довольно простой способ реализовать сбалансированное дерево.
Тем не менее, наиболее компактные реализации деревьев козлов отпущения действительно используют вращения для преобразования несбалансированного дерева в идеально сбалансированное. Вам не нужно использовать для этого вращения, хотя, если места мало, это, вероятно, лучший способ сделать это.
Надеюсь это поможет!
