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

Ответ 1

Часть 1 - высота

Как отмечает starblue, высота просто рекурсивна. В псевдокоде:

height(node) = max(height(node.L), height(node.R)) + 1

Теперь высота может быть определена двумя способами. Это может быть количество узлов в пути от корня до этого node, или это может быть количество ссылок. Согласно странице на которую вы ссылаетесь, наиболее распространенным определением является количество ссылок. В этом случае полный псевдокод будет:

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 like) Псевдокод:

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

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

Ответ 2

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

• "Балансовый фактор R" относится к правильному поддереву дерева, которое, вне всякого сомнения, вне баланса.

Ответ 3

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

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

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

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

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

Ответ 4

Здесь альтернативный способ найти высоту. Добавьте дополнительный атрибут к node height:

class Node
{
data value; //data is a custom data type
node right;
node left;
int height;
}

Теперь мы сделаем простой обход дерева по ширине и продолжаем обновлять значение высоты для каждого node:

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
}

Приветствия,

Ответ 5

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

int height(struct tree *t) {
    if (t == NULL)
        return 0;
    else
        return max(height(t->left), height(t->right)) + 1;
}

с соответствующим определением max() и struct tree. Вы должны найти время, чтобы понять, почему это соответствует определению, основанному на длине пути, которую вы цитируете. Эта функция использует ноль в качестве высоты пустого дерева.

Однако, для чего-то вроде дерева AVL, я не думаю, что вы на самом деле вычисляете высоту каждый раз, когда вам это нужно. Вместо этого каждое дерево node дополняется дополнительным полем, которое запоминает высоту поддерева, корневого в этом node. Это поле должно быть обновлено до тех пор, пока дерево не будет изменено вставками и удалениями.

Я подозреваю, что если вы каждый раз вычисляете высоту, а не кешируете ее в дереве, как это было предложено выше, то форма дерева AVL будет правильной, но она не будет иметь ожидаемой логарифмической производительности.

Ответ 6

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

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

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

Ответ 7

Здесь, где он запутывается, текст гласит: "Если коэффициент баланса R равен 1, означает, что вставленная на (внешняя) правая сторона этого node и левая ротация необходима". Но из понимания текста в тексте говорилось (как я цитировал), что если коэффициент баланса находился в пределах [-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 left child becomes our right

Теперь, большая вещь, которую вы должны заметить здесь - эта левая ротация НЕ ИЗМЕНИЛА ГЛУБИНА ДЕРЕВА. Мы не более сбалансированы, потому что сделали это.

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

 P
  \
   O
    \
     LC
      \
       RC

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

 P
  \
   LC
  /  \
 O    RC

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

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

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

 P
  \
   O
    \
     LC
      \
       RC

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

Ответ 8

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

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;
}

При удалении 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 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

Ответ 9

Это 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