Обновление AVL Tree Проблема - PullRequest
Новая
       15

Обновление AVL Tree Проблема

2 голосов
/ 02 мая 2011

На данный момент я работаю только над реализацией обновления AVL Tree с той же стороны.

Проблема, которую я получаю, заключается в том, что моя функция отображения перестает работать после того, как дерево бинарного поиска проходит через переупорядочение AVL. Я перемещаю указатели соответственно, но когда функция ломается, вставляется другой объект, и я не могу на всю жизнь отладить его. любая помощь будет принята с благодарностью. 

AVLTree tree = new AVLTree(3)
tree.insert(2);
tree.insert(1); //causes the problem
tree.print();

вот мой класс AVLTree 

public class AVLTree {

private boolean verboseMode = true;

private Comparable data;
private AVLTree left, right, parent;
private int rightHeight = -1, leftHeight = -1;

public AVLTree(Comparable obj){
    data = obj; left = null; right = null; parent = null;
}

private AVLTree(Comparable obj, AVLTree l, AVLTree r, AVLTree p){
    data = obj; left = l; right = r; parent = p;
}



public void insert(Comparable obj){
    int compare = obj.compareTo(data);
    if(compare != 0)
        if(compare < 0)
            if(left == null){
                left = new AVLTree(obj, null, null, this);
                // comment out for standard BST //
                left.updateHeight();            //
                left.updateBalance();           //
                // ///////////////////////////////
            } else
                left.insert(obj);
        else
            if(right == null){
                right = new AVLTree(obj, null, null, this);
                // comment out for standard BST //
                right.updateHeight();           //
                right.updateBalance();          //
                // ///////////////////////////////
            } else
                right.insert(obj);
    else
        System.err.printf("Object '%o' already in tree\n", obj);
}

public void updateHeight(){
    if(this.parent != null){
        if(this == this.parent.left)
            this.parent.leftHeight += 1;
        if(this == this.parent.right)
            this.parent.rightHeight += 1;
        this.parent.updateHeight();
    }
}

public void updateBalance(){
    if(this.parent != null){
        int diff = this.parent.leftHeight - this.parent.rightHeight;
        if(diff > 1 || diff < -1){
            if(this.parent.leftHeight > this.parent.rightHeight){
                AVLTree t0 = this.parent.parent;
                AVLTree t1 = this.parent;
                AVLTree t3 = this.parent.right;
                AVLTree t4 = this.right;
                this.right = t1;
                this.right.parent = this;
                if(t0 == null)
                    this.parent = null;
                else {
                    if(this == this.parent.left){
                        this.parent = t0;
                        this.parent.left = this;
                    } else {
                        this.parent = t0;
                        this.parent.right = this;
                    }
                }
                if(t4 == null)
                    this.right.left = null;
                else {
                    this.right.left = t4;
                    this.right.left.parent = this.right;
                }
                if(t3 == null)
                    this.right.right = null;
                else {
                    this.right.right = t3;
                    this.right.right.parent = this.right;
                }
            }               
        } else
            this.parent.updateBalance();
    }           
}       

public void print(){
    String loc = ""; print(loc);
} 
public void print(String loc){
    if(this.left != null){
        String tempLoc = loc+"0";
        left.print(tempLoc);
    }
    if(this.right != null){
        String tempLoc = loc+"1";
        right.print(tempLoc);
    }
    if(!verboseMode){
        System.out.printf("%s[%s], ", data, loc);
    } else
        System.out.printf("%s[%s] \t[%d, %d]\n\n", data, loc, leftHeight, rightHeight);         
}

}

1 Ответ

0 голосов
/ 11 мая 2011

Ваша проблема заключается в следующем: при вызове линии tree.insert(1); //causes the problem вы перетасовываете дерево, и верхний / корневой узел изменяется / переставляется;Но ваша переменная tree указывает на старый корень до того, как дерево будет переставлено.Таким образом, ваш код делает именно то, что вы сказали.

Этот метод можно передать классу:

public AVLTree getRoot () {

    if(parent != null) {
       return parent.getRoot();
    } else {
       return this;
    }
}

, а также создайте следующую функцию main (): 

  public static void main(String[] args) {     
    AVLTree tree = new AVLTree(3);
    System.out.println(tree.getRoot());
    tree.insert(2);
    System.out.println(tree.getRoot());
    tree.insert(1); //causes the problem
    System.out.println(tree.getRoot());
    tree.getRoot().print();
    tree.print();
  }

Пример вывода из цикла выглядит следующим образом: 

AVLTree@47b480
AVLTree@47b480
AVLTree@9b49e6
1[0]  [-1, -1]
3[1]  [1, -1]
2[]   [0, -1]
3[]   [1, -1] //this comes from the second call to print
...