Лучший способ рассчитать высоту в бинарном дереве поиска? (балансировка AVL-дерева) - PullRequest
Новая
       72

Лучший способ рассчитать высоту в бинарном дереве поиска? (балансировка AVL-дерева)

58 голосов
/ 22 февраля 2009

Я ищу лучший способ для расчета баланса узлов в 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-деревьев, но, похоже, просто упускаю это существенное прозрение.

Редактировать: Примеры кода предпочтительнее академических формул, поскольку мне всегда было легче понять что-то в коде, но любая помощь очень ценится.

Редактировать: Хотелось бы пометить все ответы как "принятые", но для меня ответ Ника был первым, который заставил меня сказать "ага".

Ответы [ 9 ]

75 голосов
/ 23 февраля 2009

часть 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)) * ), если вы будете хранить и обновлять информацию о высоте в дереве, а не вычислять ее каждый раз. ( О (п) )

Часть 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

Надеюсь, это имеет смысл

4 голосов
/ 25 марта 2009

Вам не нужно вычислять глубину дерева на лету.

Вы можете поддерживать их при выполнении операций.

Кроме того, вам на самом деле не нужно следить за глубиной; Вы можете просто отслеживать разницу между глубиной дерева слева и справа.

http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx

Просто отследить коэффициент баланса (разницу между левым и правым поддеревьями) мне проще из программирования POV, за исключением того, что сортировка коэффициента баланса после поворота является PITA ...

4 голосов
/ 23 февраля 2009

  • Высота легко определяется с помощью рекурсии, берется максимальная высота поддеревьев плюс один.

  • «Коэффициент баланса R» относится к правому поддереву дерева, которое, как я полагаю, не сбалансировано.

2 голосов
/ 31 октября 2010

Вот альтернативный способ определения высоты. Добавьте дополнительный атрибут к вашему узлу с именем 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
}

Приветствия

1 голос
/ 25 марта 2009

Вот где это сбивает с толку, текст гласит: «Если коэффициент баланса R равен 1, это означает, что вставка произошла на (внешней) правой стороне этого узла и слева вращение необходимо ". Но из m понимания текста сказано (как я цитировал), что если коэффициент баланса был в пределах [-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

И СЕЙЧАС, если мы повернем влево, мы получим вот это ... 

 P
  \
   LC
  /  \
 O    RC

Magic! нам удалось избавиться от уровня дерева - мы установили баланс дерева .

Балансировка дерева означает избавление от лишней глубины и более полную упаковку верхних уровней - это именно то, что мы только что сделали.

Все, что связано с одинарным / двойным вращением, заключается в том, что ваше поддерево должно выглядеть так: 

 P
  \
   O
    \
     LC
      \
       RC

перед поворотом - и вам может потребоваться повернуть вправо, чтобы войти в это состояние. Но если вы уже в этом состоянии, вам нужно только повернуть налево.

1 голос
/ 23 февраля 2009

Вот где это сбивает с толку, текст гласит: «Если коэффициент баланса R равен 1, это означает, что вставка произошла на (внешней) правой стороне этого узла, и необходимо левое вращение». Но из моего понимания в тексте сказано (как я цитировал), что если коэффициент баланса был в пределах [-1, 1], то тогда балансировка не нужна?

R является правым дочерним узлом текущего узла N.

Если balance(N) = +2, то вам нужно какое-то вращение. Но какой поворот использовать? Ну, это зависит от balance(R): если balance(R) = +1, то вам нужно повернуть влево на N; но если balance(R) = -1, то вам понадобится какое-то двойное вращение.

1 голос
/ 23 февраля 2009

Ну, вы можете вычислить высоту дерева с помощью следующей рекурсивной функции: 

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 будет правильной, но она не будет иметь ожидаемой логарифмической производительности.

0 голосов
/ 16 октября 2017

Это 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
0 голосов
/ 24 октября 2015

Дайте 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

...