在 java 中实现 avl 树时遇到问题

Question

大家好，我一直在尝试实现AVL树，但没有成功。我正在练习以获得这个概念。到目前为止，我已经成功地插入到树中，获取树的高度，检查它是否平衡，树中的节点数，找到三个中的最小值和最大值，并检查树中是否有值。现在我正在尝试平衡树，同时在树中插入一个新节点，但没有成功。请你指导我做错了什么。下面是我的结果代码。请耐心等待并感谢。下面是我的节点类：二进制节点.java

public class BinaryNode<T> {
private T data;
private BinaryNode<T> rightChild;
private BinaryNode<T> leftChild;
public BinaryNode(){}
public BinaryNode(T data){
    this(data, null, null);
}
public BinaryNode(T data, BinaryNode<T> leftChild, BinaryNode<T> rightChild){
    this.data = data;
    this.leftChild = leftChild;
    this.rightChild = rightChild;
}
public void setLeftChild(BinaryNode<T> leftChild){
    this.leftChild = leftChild;
}
public void setRightChild(BinaryNode<T> rightChild){
    this.rightChild = rightChild;
}
public BinaryNode<T> getRightChild() {
    return rightChild;
}
public BinaryNode<T> getLeftChild() {
    return leftChild;
}
public T getData(){
    return data;
}
public int Height(){
    return getHeight(this);
}
//returns the height of the tree
private int getHeight(BinaryNode<T> root){
    if(root == null){
        return -1;
    }
    else
        return 1+Math.max(getHeight(root.getLeftChild()), getHeight(root.getRightChild()));
}
//functions get the number of nodes availabe in the tree
protected int getNumberOfNodes(){
   int a=0,b=0;
   if(leftChild!=null){
       a = leftChild.getNumberOfNodes();
           }
       if(rightChild!=null){
       b = rightChild.getNumberOfNodes();
       }
   return a+b+1;
}
 public void balance(){
   balance(this);
 }
private void balance(BinaryNode<T> root){
   int balance = getHeight(root.getLeftChild())-getHeight(root.getRightChild());
   if(balance>2){
       if(getHeight(root.getLeftChild())>=getHeight(root.getRightChild())){
           rotateRight(root);
       }
       else{
           doubleRotateRight(root);
       }
   }
   else if(balance<-2){
       if(getHeight(root.getRightChild())>=getHeight(root.getLeftChild())){
           rotateLeft(root);
       }
       else{
           doubleRotateLeft(root);
       }
   }
   else{
       getHeight(root);
   }
 }
//right right rotation
private BinaryNode<T> rotateRight(BinaryNode<T> root){
    BinaryNode<T> nodeA = root.getLeftChild();
    root.setLeftChild(nodeA.getRightChild());
    nodeA.setRightChild(root);
    return nodeA;
}
//left left rotation
private BinaryNode<T> rotateLeft(BinaryNode<T> root){
    BinaryNode<T> nodeA = root.getRightChild();
    root.setRightChild(nodeA.getLeftChild());
    nodeA.setLeftChild(root);
    return nodeA;
}
//right left rotation
private BinaryNode<T> doubleRotateLeft(BinaryNode<T> root){
    BinaryNode<T> nodeA = root.getLeftChild();
    root.setRightChild(rotateRight(nodeA));
    return rotateLeft(root);
}
//left right rotation
private BinaryNode<T> doubleRotateRight(BinaryNode<T> root){
    BinaryNode<T> nodeA = root.getRightChild();
    root.setLeftChild(rotateLeft(nodeA));
    return rotateRight(root);
}

}

二进制搜索树：

public class BinarySearchTree<T extends Comparable<? super T>> {
private BinaryNode<T> root;
public BinarySearchTree() {}
public BinarySearchTree(T data){
    root = new BinaryNode<T>(data);
}
public void insert(T data){
    BinaryNode<T> newNode = new BinaryNode<T>(data);
    if(isEmpty()){
        root = newNode;
    }
    else
        insertElements(root, newNode);
}
private void insertElements(BinaryNode<T> root, BinaryNode<T> newNode){
    if(newNode.getData().compareTo(root.getData())<0){
        if(root.getLeftChild()==null){
            root.setLeftChild(newNode);
        }
        else
            insertElements(root.getLeftChild(), newNode);
            //balance(root.getLeftChild());
    }
    else{
        if(root.getRightChild()==null){
            root.setRightChild(newNode);
        }
        else{
            insertElements(root.getRightChild(), newNode);
            //balance(root.getRightChild()); 
        }
    }
    balance(root);
}
public void balance(BinaryNode<T> root){
    root.balance();
}
public boolean isEmpty(){
    return (root==null);
}
public void preOrder(){
    preOrder(root);
}
private void preOrder(BinaryNode<T> root){
    if(root == null){
        return;
    }
    else{
        System.out.println(root.getData());
        preOrder(root.getLeftChild());
        preOrder(root.getRightChild());
    }
}
public int getHeight(){
    return root.Height();
}
//gets the number of nodes in the tree
public int getNumberOfNodes(){
    return root.getNumberOfNodes();
}
//returns true or false if tree is balanced
 public boolean isBalanced(){
       if(root==null){
           return true;
       }
           if(checkHeight(root)==-1){
               return false;
           }
           else{
               return true;
       }
   }
 //checks to see if the tree is balanced. 
 private int checkHeight(BinaryNode<T> root){
     if(root==null){
         return 0;
     }
     int left = checkHeight(root.getLeftChild());
     int right = checkHeight(root.getRightChild());
     if(left==-1||right==-1){
         return -1;
     }
     if(Math.abs(left-right)>1){
         return -1;
     }
     else
         return Math.max(left, right)+1;
 }
 public T findMin(){
     return findMin(root);
 }
 private T findMin(BinaryNode<T> root){
     if(root==null){
         return null;
     }
     else if(root.getLeftChild()==null){
         return root.getData();
     }
     else
         return findMin(root.getLeftChild());
 }
 public T findMax(){
     return findMax(root);
 }
 private T findMax(BinaryNode<T> root){
     if(root==null){
         return null;
     }
     else if(root.getRightChild()==null){
         return root.getData();
     }
     else return findMax(root.getRightChild());
 }
 public boolean contains(T entry){
     return contains(root, entry);
 }
 private boolean contains(BinaryNode<T> root, T entry){
    if(root == null){
        return false;
    }
    else if(entry.compareTo(root.getData())<0){
        return contains(root.getLeftChild(), entry);
    }
    else if(entry.compareTo(root.getData())>0){
        return contains(root.getRightChild(), entry);
    }
    else{
        if(entry.compareTo(root.getData())==0){
        return true;
        }
        else
            return false;
    }
 }
 public void makeEmpty(){
     this.root = null;
  }
}

测试类：

public class Test {
public static void main(String[] args) {
    // TODO Auto-generated method stub
        BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
        tree.insert(5);
        tree.insert(10);
        tree.insert(20);
        tree.preOrder(); //prints out the tree in a pre-order list
        System.out.println("Height of tree: " +tree.getHeight());
        System.out.println("Number of Nodes: "+tree.getNumberOfNodes());
        System.out.println("Balanced: "+tree.isBalanced());
        System.out.println("Find max:  "+ tree.findMax());
        System.out.println("Find min: "+tree.findMin());
        System.out.println("Contains: "+tree.contains(1));
 }
}

以下是结果。但我错了，因为这棵树不平衡。似乎有些不对劲。因为每次我插入一个新节点时，我也会平衡尝试平衡树。请有人帮助我并检测我做错了什么。如果代码很长，我深表歉意。结果：

5
10
20
Height of tree: 2
Number of Nodes: 3
Balanced: false
Find max:  20
Find min: 5
Contains: false

Answer 1

您的方法BinarySearchTree#checkHeight(BinaryNode<T> root)报告，如果左右子树的高度相差超过一个，则树将失去平衡。但是，当您插入节点时，它最终会调用方法 BinaryNode#balance(BinaryNode<T> root) ，除非子树高度相差超过 2，否则该方法不会旋转节点。您需要修改后一种方法，以便在高度相差超过 1 时旋转节点。此外，在该方法else情况下调用getHeight(root)似乎毫无用处。

可能还有其他问题，但这是我看到的唯一问题。