Лучший способ вычислить высоту в двоичном дереве поиска?(балансировка AVL-дерева)
https://stackoverflow.com/questions/575772
-
05-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я ищу наилучший способ рассчитать баланс узлов в AVL-дерево.Я думал, что у меня это работает, но после некоторой интенсивной вставки / обновления я вижу, что это работает некорректно (вообще).
Это своего рода вопрос из двух частей, первая часть будет заключаться в том, как вычислить высоту поддерева, я знаю определение "Высота узла - это длина самого длинного нисходящего пути к листу от этого узла". и я понимаю это, но мне не удается это реализовать.И чтобы еще больше сбить меня с толку, эту цитату можно найти в Википедии о высоте деревьев "Обычно значение -1 соответствует поддереву без узлов, тогда как ноль соответствует поддереву с одним узлом".
И вторая часть - это получение коэффициента баланса поддерева в дереве AVL, у меня нет проблем с пониманием концепции, "получите высоту вашего L и R поддеревья и вычитание R От L".И это определяется примерно так: BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]
Чтение в википедии говорит об этом в первых нескольких строках, описывающих вставки в дерево AVL: "Если коэффициент баланса становится равным -1, 0 или 1, то дерево по-прежнему находится в форме AVL, и никаких поворотов не требуется".
Затем он продолжает, говоря следующее "Если коэффициент баланса становится 2 или -2, то дерево с корнем в этом узле несбалансировано, и требуется поворот дерева.Для балансировки дерева потребуется самое большее один или два поворота". - что мне нетрудно понять.
Но (да, всегда есть "но").
Вот тут-то все и сбивает с толку, в тексте говорится "Если коэффициент баланса R равен 1, это означает, что вставка произошла на (внешней) правой стороне этого узла и требуется поворот влево".Но, насколько я понимаю, в тексте сказано (как я цитировал), что если фактор баланса находится в пределах [-1, 1] значит, не было необходимости в балансировании?
Я чувствую, что я так близок к пониманию концепции, я уменьшил вращение дерева, реализовал обычное дерево двоичного поиска и на грани понимания AVL-деревьев, но, похоже, мне не хватает этого важного прозрения.
Редактировать: Примеры кода предпочтительнее академических формул, поскольку мне всегда было легче разобраться в чем-то в коде, но я очень ценю любую помощь.
Редактировать: Хотел бы я отметить все ответы как "принятые", но для меня ответ Ника был первым, что заставило меня воскликнуть "ага".
Решение
Часть 1 - высота
Как говорит starblue, высота просто рекурсивна.В псевдокоде:
height(node) = max(height(node.L), height(node.R)) + 1
Теперь высоту можно было определить двумя способами.Это может быть количество узлов в пути от корня к этому узлу, или это может быть количество ссылок.В соответствии с страница, на которую вы ссылались, наиболее распространенным определением является количество ссылок.В этом случае полный псевдокод был бы:
height(node):
if node == null:
return -1
else:
return max(height(node.L), height(node.R)) + 1
Если бы вам нужно было количество узлов, код был бы следующим:
height(node):
if node == null:
return 0
else:
return max(height(node.L), height(node.R)) + 1
В любом случае, алгоритм перебалансировки, я думаю, должен работать одинаково.
Однако ваше дерево будет намного эффективнее (O(ln(n))) если вы сохраняете и обновляете информацию о высоте в дереве, а не вычисляете ее каждый раз.(O(n))
Часть 2 - балансировка
Когда говорится "Если коэффициент баланса R равен 1", то речь идет о коэффициенте баланса правой ветви, когда коэффициент баланса вверху равен 2.В нем рассказывается вам, как выбрать, выполнять ли одиночный поворот или двойной.В псевдокоде (подобном python):
if balance factor(top) = 2: // right is imbalanced
if balance factor(R) = 1: //
do a left rotation
else if balance factor(R) = -1:
do a double rotation
else: // must be -2, left is imbalanced
if balance factor(L) = 1: //
do a left rotation
else if balance factor(L) = -1:
do a double rotation
Я надеюсь, что в этом есть смысл
Другие советы
Высота легко реализуется рекурсией, возьмите максимальную высоту поддеревьев плюс единицу.
"Коэффициент баланса R" относится к правому поддереву дерева, которое, я полагаю, вышло из равновесия.
Вам не нужно вычислять глубину дерева "на лету".
Вы можете поддерживать их по мере выполнения операций.
Кроме того, на самом деле вам не нужно отслеживать глубины;вы можете просто отслеживать разницу между левой и правой глубинами дерева.
http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx
Простое отслеживание коэффициента баланса (разница между левым и правым поддеревьями), как мне показалось, проще из POV программирования, за исключением того, что сортировка коэффициента баланса после поворота - это ЛАВАШ...
Вот альтернативный способ определения высоты.Добавьте дополнительный атрибут к вашему узлу под названием height:
class Node
{
data value; //data is a custom data type
node right;
node left;
int height;
}
Теперь мы выполним простой обход дерева в ширину и продолжим обновлять значение высоты для каждого узла:
int height (Node root)
{
Queue<Node> q = Queue<Node>();
Node lastnode;
//reset height
root.height = 0;
q.Enqueue(root);
while(q.Count > 0)
{
lastnode = q.Dequeue();
if (lastnode.left != null){
lastnode.left.height = lastnode.height + 1;
q.Enqueue(lastnode.left);
}
if (lastnode.right != null){
lastnode.right.height = lastnode.height + 1;
q.Enqueue(lastnode.right);
}
}
return lastnode.height; //this will return a 0-based height, so just a root has a height of 0
}
Ваше здоровье,
Ну, вы можете вычислить высоту дерева с помощью следующей рекурсивной функции:
int height(struct tree *t) {
if (t == NULL)
return 0;
else
return max(height(t->left), height(t->right)) + 1;
}
с соответствующим определением max() и struct tree.Вам следует потратить время, чтобы выяснить, почему это соответствует определению, основанному на длине пути, которое вы цитируете.Эта функция использует ноль в качестве высоты пустого дерева.
Однако для чего-то вроде дерева AVL я не думаю, что вы на самом деле вычисляете высоту каждый раз, когда вам это нужно.Вместо этого каждый узел дерева дополняется дополнительным полем, которое запоминает высоту поддерева, имеющего корни в этом узле.Это поле необходимо поддерживать в актуальном состоянии, поскольку дерево изменяется путем вставок и удалений.
Я подозреваю, что, если вы каждый раз вычисляете высоту вместо того, чтобы кэшировать ее внутри дерева, как было предложено выше, форма дерева AVL будет правильной, но она не будет иметь ожидаемой логарифмической производительности.
Вот где это сбивает с толку, в тексте говорится "Если коэффициент баланса R равен 1, это означает, что вставка произошла на (внешней) правой стороне этого узла и требуется поворот влево".Но, насколько я понимаю, в тексте сказано (как я цитировал), что если коэффициент баланса находится в пределах [-1, 1], то в балансировке нет необходимости?
R является правым дочерним элементом текущего узла N.
Если balance(N) = +2, тогда вам нужна какая-то ротация.Но какое вращение использовать?Ну, это зависит от balance(R):если balance(R) = +1 затем вам нужен поворот влево на N;но если balance(R) = -1 тогда вам понадобится какой-нибудь двойной поворот.
Вот где это сбивает с толку, в тексте говорится "Если коэффициент баланса R равен 1, это означает, что вставка произошла на (внешней) правой стороне этого узла и слева требуется поворот".Но, насколько я понимаю, в тексте сказано (как я цитировал), что если коэффициент баланса был в пределах [-1, 1], то в балансировке не было необходимости?
Ладно, время прозрения.
Подумайте, что делает вращение.Давайте подумаем о повороте налево.
P = parent
O = ourself (the element we're rotating)
RC = right child
LC = left child (of the right child, not of ourself)
P
\
O
\
RC
/
LC
P
\
RC
/
O
\
LC
10
\
15
\
20
/
18
10
\
20
/
15
\
18
basically, what happens is;
1. our right child moves into our position
2. we become the left child of our right child
3. our right child's left child becomes our right
Теперь, важная вещь, на которую вы должны обратить внимание здесь - этот поворот влево НЕ ИЗМЕНИЛ ГЛУБИНУ ДЕРЕВА.Мы не стали более уравновешенными из-за того, что сделали это.
Но - и вот в чем волшебство AVL - если бы мы сначала повернули нужного дочернего элемента вправо, то получили бы вот что...
P
\
O
\
LC
\
RC
И теперь, если мы повернем O влево, то получим вот что...
P
\
LC
/ \
O RC
Магия!нам удалось избавиться от уровня дерева - мы создали дерево баланса.
Балансировка дерева означает избавление от лишней глубины и более полное заполнение верхних уровней - это именно то, что мы только что сделали.
Весь этот материал об одинарных / двойных поворотах заключается просто в том, что ваше поддерево должно выглядеть следующим образом;
P
\
O
\
LC
\
RC
прежде чем вы повернетесь - и вам, возможно, придется повернуть направо, чтобы войти в это состояние.Но если вы уже находитесь в этом состоянии, вам нужно всего лишь повернуть влево.
Дать BinaryTree<T, Comparator>::Node a subtreeHeight элемент данных, инициализированный в 0 в своем конструкторе и автоматически обновляемый каждый раз с помощью:
template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::Node::setLeft (std::shared_ptr<Node>& node) {
const std::size_t formerLeftSubtreeSize = left ? left->subtreeSize : 0;
left = node;
if (node) {
node->parent = this->shared_from_this();
subtreeSize++;
node->depthFromRoot = depthFromRoot + 1;
const std::size_t h = node->subtreeHeight;
if (right)
subtreeHeight = std::max (right->subtreeHeight, h) + 1;
else
subtreeHeight = h + 1;
}
else {
subtreeSize -= formerLeftSubtreeSize;
subtreeHeight = right ? right->subtreeHeight + 1 : 0;
}
}
template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::Node::setRight (std::shared_ptr<Node>& node) {
const std::size_t formerRightSubtreeSize = right ? right->subtreeSize : 0;
right = node;
if (node) {
node->parent = this->shared_from_this();
subtreeSize++;
node->depthFromRoot = depthFromRoot + 1;
const std::size_t h = node->subtreeHeight;
if (left)
subtreeHeight = std::max (left->subtreeHeight, h) + 1;
else
subtreeHeight = h + 1;
}
else {
subtreeSize -= formerRightSubtreeSize;
subtreeHeight = left ? left->subtreeHeight + 1 : 0;
}
}
Обратите внимание, что элементы данных subtreeSize и depthFromRoot также обновляются.Эти функции вызываются при вставке узла (все протестированные), например
template <typename T, typename Comparator>
inline std::shared_ptr<typename BinaryTree<T, Comparator>::Node>
BinaryTree<T, Comparator>::Node::insert (BinaryTree& tree, const T& t, std::shared_ptr<Node>& node) {
if (!node) {
std::shared_ptr<Node> newNode = std::make_shared<Node>(tree, t);
node = newNode;
return newNode;
}
if (getComparator()(t, node->value)) {
std::shared_ptr<Node> newLeft = insert(tree, t, node->left);
node->setLeft(newLeft);
}
else {
std::shared_ptr<Node> newRight = insert(tree, t, node->right);
node->setRight(newRight);
}
return node;
}
При удалении узла используйте другую версию removeLeft и removeRight путем замены subtreeSize++; с subtreeSize--;.Алгоритмы для rotateLeft и rotateRight также может быть адаптирован без особых проблем.Было протестировано и пройдено следующее:
template <typename T, typename Comparator>
void BinaryTree<T, Comparator>::rotateLeft (std::shared_ptr<Node>& node) { // The root of the rotation is 'node', and its right child is the pivot of the rotation. The pivot will rotate counter-clockwise and become the new parent of 'node'.
std::shared_ptr<Node> pivot = node->right;
pivot->subtreeSize = node->subtreeSize;
pivot->depthFromRoot--;
node->subtreeSize--; // Since 'pivot' will no longer be in the subtree rooted at 'node'.
const std::size_t a = pivot->left ? pivot->left->subtreeHeight + 1 : 0; // Need to establish node->heightOfSubtree before pivot->heightOfSubtree is established, since pivot->heightOfSubtree depends on it.
node->subtreeHeight = node->left ? std::max(a, node->left->subtreeHeight + 1) : std::max<std::size_t>(a,1);
if (pivot->right) {
node->subtreeSize -= pivot->right->subtreeSize; // The subtree rooted at 'node' loses the subtree rooted at pivot->right.
pivot->subtreeHeight = std::max (pivot->right->subtreeHeight, node->subtreeHeight) + 1;
}
else
pivot->subtreeHeight = node->subtreeHeight + 1;
node->depthFromRoot++;
decreaseDepthFromRoot(pivot->right); // Recursive call for the entire subtree rooted at pivot->right.
increaseDepthFromRoot(node->left); // Recursive call for the entire subtree rooted at node->left.
pivot->parent = node->parent;
if (pivot->parent) { // pivot's new parent will be its former grandparent, which is not nullptr, so the grandparent must be updated with a new left or right child (depending on whether 'node' was its left or right child).
if (pivot->parent->left == node)
pivot->parent->left = pivot;
else
pivot->parent->right = pivot;
}
node->setRightSimple(pivot->left); // Since pivot->left->value is less than pivot->value but greater than node->value. We use the NoSizeAdjustment version because the 'subtreeSize' values of 'node' and 'pivot' are correct already.
pivot->setLeftSimple(node);
if (node == root) {
root = pivot;
root->parent = nullptr;
}
}
где
inline void decreaseDepthFromRoot (std::shared_ptr<Node>& node) {adjustDepthFromRoot(node, -1);}
inline void increaseDepthFromRoot (std::shared_ptr<Node>& node) {adjustDepthFromRoot(node, 1);}
template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::adjustDepthFromRoot (std::shared_ptr<Node>& node, int adjustment) {
if (!node)
return;
node->depthFromRoot += adjustment;
adjustDepthFromRoot (node->left, adjustment);
adjustDepthFromRoot (node->right, adjustment);
}
Вот весь код целиком: http://ideone.com/d6arrv
Это решение, похожее на BFS, довольно простое.Просто перепрыгивайте уровни один за другим.
def getHeight(self,root, method='links'):
c_node = root
cur_lvl_nodes = [root]
nxt_lvl_nodes = []
height = {'links': -1, 'nodes': 0}[method]
while(cur_lvl_nodes or nxt_lvl_nodes):
for c_node in cur_lvl_nodes:
for n_node in filter(lambda x: x is not None, [c_node.left, c_node.right]):
nxt_lvl_nodes.append(n_node)
cur_lvl_nodes = nxt_lvl_nodes
nxt_lvl_nodes = []
height += 1
return height
