avl树-旋转奇怪:破坏bst属性

你其实没做错什么。

在注释中,您会说“我认为L边小于或等于当前节点值,而R边是较大的值。我错了吗?”

……是的,你错了。

对于具有重复值的树,右分支仅包含严格较大元素的条件与平衡操作不兼容。试试这个:将20个相同值的副本链接到一个树中。如果只能在左侧链接相等的值,则必须创建单个链接列表。你的树有20层深,完全不平衡。

考虑树中重复值的方法是,树中确实没有任何重复值:-)bst定义 全部的 排序和有效的再平衡操作,如旋转 保存 全部订购。

当你插入第二个 49 你可以把它放在第一棵树的左边或右边 49个 是的。如果你把它放在左边 较小的 根据树的顺序,在任何再平衡之后,它总是更小的。如果你把它放在右边 更大的 ,并将根据树的顺序保持更大。

如果你仔细想想,一定是这样,因为平衡操作 别看了 在节点中的值处。它们连接在一起的方式决定了顺序,而且顺序不会改变。

对于您的情况,如果键和值一致,可以如下所示。假设您的节点类如下所示:

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

这样,你就不再有复制品了:)