Блог

У меня возникли проблемы с изменением корневого указателя моего дерева AVL, независимо от того, является ли это операцией поворота или простым удалением.

Приведенный ниже код предназначен для удаления. если я попытаюсь удалить корень дерева, когда у него нет дочерних элементов (node = null), ничего не произойдет. если я попытаюсь «удалить» корень с дочерним элементом (с помощью setValue()), значение корня изменится (и несколько сработает), но сам объект не изменится, и это не идеально.

 NodeBal delete(NodeBal node, int key) {
    if (node == null) {
        return node;
    } else if (node.getValue() > key) {
        node.setLeft(delete(node.getLeft(), key));
    } else if (node.getValue() < key) {
        node.setRight(delete(node.getRight(), key));
    } else {
        if (node.getLeft() == null || node.getRight() == null) {
            System.out.println("delete() DEBUG: "   (node == this.root));
            node = (node.getLeft() == null) ? node.getRight() : node.getLeft();
        } else {
            NodeBal mostLeftChild = mostLeftChild(node.getRight());
            node.setValue(mostLeftChild.getValue());
            node.setRight(delete(node.getRight(), node.getValue()));
        }
    }
    if (node != null) {
        node = rebalance(node);
    }
return node;
}
 

то же самое происходит и с вращениями:

 public NodeBal rotateRight(NodeBal y) {
    /*
                 Y     
                /                   X
               X   A                / 
              /         --->      Z   Y
             Z   B                /  / 
            /                   D  C B  A
           D   C
    */
    /*
    
    */
    System.out.println("[!] Rotating right. Pivot: "   y.getValue());
    NodeBal x = y.getLeft();
    NodeBal c = x.getRight();
    NodeBal p = fetchParentOf(y.getValue());
    x.setRight(y);
    y.setLeft(c);
    if (p != null){
        p.setLeft(x);
    }
    updateBalance(y);
    updateBalance(x);
    return x;
}
 

возьмем эту операцию балансировки в качестве примера:

            5 <- Root             (Desired)                  (Actual)
          /                          4 <- New root             5
         4     Rotate right 5 -->   /              -->       / 
        /                          3   5 <- Old root         n   n <- nulls
       3
 

Узлы 3 и 4 «исчезли». возможно, потому, что печать (и почти все другие функции) начинаются с корневого узла. узлы 3 и 4 не показаны, потому что они недоступны с 5.

полный код доступен на моем github. Спасибо за чтение!