AVL Tree — странность вращения: нарушение свойства BST

На самом деле ты не сделал ничего плохого.

В комментариях вы говорите: «Я думал, что сторона L меньше или равна текущему значению узла, а сторона R больше значения. Я ошибаюсь в этом?»

... и да, вы ошибаетесь в этом.

Для деревьев с повторяющимися значениями условие, что правая ветвь содержит только элементы строго большего размера, несовместимо с операциями балансировки. Попробуйте следующее: свяжите 20 копий одного и того же значения в дерево. Если вы можете связать только одинаковые значения слева, вам нужно создать односвязный список. Ваше дерево будет состоять из 20 уровней и полностью несбалансировано.

О повторяющихся значениях в дереве можно думать так: в дереве действительно нет повторяющихся значений :-) BST определяет общее упорядочение, а допустимые операции перебалансировки, такие как повороты, preserve этот общий порядок.

Когда вы вставите этот второй 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;
}

Таким образом, у вас больше нет дубликатов :)