当我在做AVL树实现时，我遇到了旋转破坏BST属性的情况。
我很确定我做错了什么，但我无法弄清楚它是什么。
我将 41、49、21 和 47 插入到 AVL 树中。当我再次添加 49 时，它发出"失衡"的信号，如下所示。
(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
这棵树平衡得更好，但我想我在右下角的子树中破坏了 BST 属性，在 49 的右侧有 49
49
/
47 49
我认为平衡这棵树的最好方法是遵循
47
/
41 49
/ /
21 49
但我不知道如何使用 41-49-21-47-49 数字添加序列到达那里。 也许这不是正确的结果，但我在这里迷失了方向。
最佳结果是什么，我应该如何到达那里？
有人可以告诉我我做错了什么吗？
多谢！！！
你实际上没有做错任何事。
在评论中，你说"我认为L端小于或等于当前节点值，R端是更大的值。难道我说错了吗？
。是的，你错了。
对于具有重复值的树，右分支仅包含严格较大的元素的条件与平衡操作不兼容。 试试这个：将 20 个相同值的副本链接到一棵树中。 如果你只能在左侧链接相等的值，那么你必须创建一个单向链表。 你的树将有20层深，完全不平衡。
考虑树中重复值的方法是树中实际上没有任何重复值：-( BST 定义总排序，有效的再平衡操作(如轮换(将保留此总排序。
当您将第二个49插入树中时，您将把它放在第一个49的左侧或右侧。 如果把它放在左边，那么根据树的顺序，它会变小，并且在任何重新平衡后它总是会变小。 如果你把它放在右边，那么它会更大，并且会根据树的顺序保持更大。
如果您考虑一下，它必须是这种方式，因为平衡操作甚至不查看节点中的值。 它们链接在一起的方式决定了顺序，并且顺序不会改变。
对于您的情况，如果键和值重合，则可能如下所示。假设您的 Node 类如下所示：
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;
}
这样，您就不再有重复项:)