AVL 树 - 旋转奇数：打破 BST 属性

Question

当我在 AVL Tree 实现上工作时，我遇到了一个旋转破坏 BST 的情况属性。

我很确定我做错了什么，但我不知道是什么。

我将 41、49、21 和 47 插入到 AVL 树中。当我再次添加 49 时，它发出 "Out of Balance" 如下所示的信号。

                 (Out of balance !!!)
                 (   at 49 L-R      )
     41                41
    /  \              /  \
   21   49  =>      21    49
       /                 /
      47               47
                         \
                          49

因此我尝试将 47 向左旋转，49 向右旋转，如下所示

          Rotate 47         Rotate 49
           to Left          to Right 
     41               41                 41
    /  \     =>      /  \      =>       /  \  
   21   49         21    49           21    49 
       /                /                  /  \
      47               49                47    49
        \             /
         49          47

这棵树平衡得更好，但我认为我在 49

的右侧有 49 破坏了右下子树中的 BST 属性

    49
   /  \
  47  49

我认为平衡这棵树的最好方法是遵循

但我不知道如何使用 41-49-21-47-49 号码添加序列到达那里。也许这不是正确的结果，但我在这里迷路了。

最佳结果是什么？我应该如何到达那里？

有人能告诉我我做错了什么吗？

非常感谢！！！

Answer 1

对于您的情况，如果键和值一致，则可能如下所示。假设您的节点 class 如下：

class Node {
    int value;     //Value
    int height;    //Height
    Node left;     //Left child
    Node right;    //Right child
    int count = 1; //keeps track of how many duplicate values were inserted
}

然后，当插入一个新值时，如果有一个新值等于当前节点的值，您可以递增 count。下面是我对 AVL 树插入的实现：

public Node insert(Node root, int value) {
    if (root == null) {
        root = new Node();
        root.value = value;
        return root;
    } else if (root.value > value) {
        root.left = insert(root.left, value);
        root.height = Math.max(root.height, root.left.height + 1);
    } else if (root.value < value) {
        root.right = insert(root.right, value);
        root.height = Math.max(root.height, root.right.height + 1);
    } else {
        // consider duplicates the same node
        root.count++;
    }

    Node a = root;
    //left subtree must be rebalanced
    if (balanceFactor(root) == 2) {
        Node b = a.left;
        //it's a left left case
        if (balanceFactor(b) == 1) {
            Node b2 = b.right;
            b.right = a;
            a.left = b2;
            a.height = getHeight(a);
            b.height = getHeight(b);
            return b;
        } else {//it's a left right case
            Node c = b.right;
            Node c1 = c.left;
            Node c2 = c.right;
            a.left = c2;
            c.right = a;
            c.left = b;
            b.right = c1;
            a.height = getHeight(a);
            b.height = getHeight(b);
            c.height = getHeight(c);
            return c;
        }
    } else if (balanceFactor(root) == -2) {//right subtree must be rebalanced
        Node b = a.right;
        //it's a left left case
        if (balanceFactor(b) == -1) {
            Node b1 = b.left;
            b.left = a;
            a.right = b1;
            a.height = getHeight(a);
            b.height = getHeight(b);
            return b;
        } else {//it's a left right case
            Node c = b.left;
            Node c1 = c.left;
            Node c2 = c.right;
            c.right = b;
            c.left = a;
            b.left = c2;
            a.right = c1;
            a.height = getHeight(a);
            b.height = getHeight(b);
            c.height = getHeight(c);
            return c;
        }
    }

    return root;
}

private static int getHeight(Node node) {
    int l = (node.left == null ? 0 : node.left.height + 1);
    int r = (node.right == null ? 0 : node.right.height + 1);
    return Math.max(l, r);
}

private static int balanceFactor(Node node) {
    int left = node.left == null ? -1 : node.left.height;
    int right = node.right == null ? -1 : node.right.height;

    return left - right;
}

这样，您就不会再有重复了:)

Answer 2

你其实并没有做错什么。

在评论中，你说"I thought L side is smaller or equal to current node value and R side is bigger value. Am I wrong about this?"

...是的，你错了。

对于具有重复值的树，右分支仅包含严格较大的元素的条件与平衡操作不兼容。试试这个：link 将 20 个相同值的副本放入一棵树中。如果您只能 link 左边的值相等，那么您必须制作一个单 link 列表。您的树将有 20 层深并且完全不平衡。

考虑树中重复值的方法是树中确实没有任何重复值:-) BST 定义了 total 排序，并且有效像旋转这样的重新平衡操作保留这个总排序。

当您将第二个 49 插入树中时，您将把它放在第一个 49 的左侧或右侧。如果你把它放在左边，那么它会根据树的顺序变小，并且在任何重新平衡之后它总是变小。如果你把它放在右边，那么它将变大，并且会根据树的顺序保持变大。

如果你考虑一下，它必须是这样的，因为平衡操作甚至不看节点中的值。它们 link 组合在一起的方式决定了顺序，并且顺序不会改变。

AVL 树 - 旋转奇数：打破 BST 属性

AVL Tree - rotation oddity: Breaking BST property

algorithm

avl-tree

binary-search-tree