Идеально сбалансированное двоичное дерево поиска

У меня есть теоретический вопрос о Balanced BST.

Я хотел бы построить Perfect Balanced Tree с 2^k - 1 узлами из обычного unbalanced BST. Самое простое решение, которое я могу придумать, - это использовать отсортированный Array/Linked list и рекурсивно разделить массив на подмассивы и построить из него Perfect Balanced BST.

Однако в случае очень больших размеров дерева мне нужно будет создать Array/List того же размера, поэтому этот метод будет потреблять большой объем памяти.

Другой вариант — использовать AVL функции поворота, вставляя элемент за элементом и балансируя дерево поворотами в зависимости от Tree Balance Factor — три высоты левого и правого поддеревьев.

Мои вопросы: прав ли я в своих предположениях? Есть ли другой способ создать идеальный BST из несбалансированного BST?


c algorithm linked-list avl-tree binary-search-tree
person OlejkaKL    schedule 24.12.2012    source источник
comment
Некоторые функции поворота имеют смысл, если у вас есть большое дерево и вы хотите преобразовать его без существенного изменения существующей структуры. - Действительно ли результат должен быть идеально сбалансированным? Какова предыстория вопроса?   -  person michas    schedule 24.12.2012
comment
Да, он должен быть идеально сбалансирован. Это часть академического проекта. Что вы подразумеваете под некоторыми функциями вращения? Насколько я знаю, есть четыре функции вращения, которые довольно легко реализовать.   -  person OlejkaKL    schedule 24.12.2012
comment
Различные виды деревьев используют немного разные способы вращения. Например сравните АВЛ и красно-черные деревья.   -  person michas    schedule 24.12.2012

Ответы (3)


arrow_upward
1
arrow_downward

Я еще не нашел очень подходящей ситуации, когда нужно идеально сбалансированное дерево поиска. Если в вашем случае это действительно необходимо, я хотел бы услышать об этом. Обычно лучше и быстрее иметь почти сбалансированное дерево.

Если у вас большое дерево поиска, отбрасывать всю существующую структуру обычно не очень хорошая идея. Использование функций поворота — хороший способ получить более сбалансированное дерево, сохранив при этом большую часть существующей структуры. Но обычно вы используете подходящую структуру данных, чтобы убедиться, что у вас никогда не будет полностью несбалансированного дерева. Так называемые самобалансирующиеся деревья.

Например, есть дерево AVL, красно-черное дерево или растянутое дерево, в которых используются несколько разные варианты вращения для сохранения баланса дерева.

Если у вас действительно полностью несбалансированное дерево, у вас может быть другая проблема. - В вашем случае вращение AVL, вероятно, лучший способ исправить это.

person michas    schedule 24.12.2012

arrow_upward
2
arrow_downward

AVL и подобные деревья не идеально сбалансированы, поэтому я не уверен, насколько они полезны в этом контексте.

Вы можете построить двусвязный список из узлов дерева, используя указатели left и right вместо указателей forward и backward. Отсортируйте этот список и постройте дерево рекурсивно снизу вверх, используя список слева направо.

Построение дерева размера 1 тривиально: просто откусите самый левый узел от списка.

Теперь, если вы можете построить дерево размера N, вы также можете построить дерево размера 2N+1: постройте дерево размера N, затем откусите один узел, затем постройте другое дерево размера N. Единственный узел будет корнем вашего большего дерева, а два меньших дерева будут его левым и правым поддеревьями. Поскольку список отсортирован, дерево автоматически становится действительным деревом поиска.

Это также легко изменить для размеров, отличных от 2^k-1.

Обновление: поскольку вы начинаете с дерева поиска, вы можете построить отсортированный список непосредственно из него в O(N) времени и O(log N) пространстве (возможно, даже в O(1) пространстве, приложив немного изобретательности), и построить дерево снизу вверх также в O(N) времени и O(log N) (или O(1)) пробел.

person n. 1.8e9-where's-my-share m.    schedule 24.12.2012

arrow_upward
0
arrow_downward

Если у вас ограниченная память, вы можете использовать операции разделения и объединения, которые можно выполнять в дереве AVL за время O (log n), и я считаю, что это постоянное пространство.

Если вы также смогли сохранить статистику заказов, вы можете разделить по медиане, сделать левый и правый края идеальными, а затем соединить.

Псевдокод (для рекурсивной версии) будет

void MakePerfect (AVLTree tree) {

    Tree left, right;
    Data median;

    SplitOnMedian(tree, &left, &median, &right);
    left = MakePerfect(left);
    right = MakePerfect(right);
    return Join(left, median, right);
}

Я считаю, что это может быть реализовано за время O (n) и пространство O (log n).

person TexMan    schedule 24.12.2012