将BinarySearchTree修改为平衡（AVL）：Java

Question

我需要修改我创建的二进制搜索树以确保它是平衡的。根据我的说明，我只需要修改添加和删除方法。这是我目前有：

package proj; 

public class BinarySearchTree<T extends Comparable<T>>{ 
    public static void main(String[] args) { 
     BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>(); 
     tree.add(5); 
     tree.add(1); 
     tree.add(2); 
     tree.add(6); 
    } 

    private Node<T> root; 
    private int size; 
    String inorder = ""; 
    String preorder = ""; 

    public BinarySearchTree(){ 
     root = null; 
     size = 0; 
    } 

    //adds a new item to the queue 
    public void add(T obj) { 
     Node<T> n = new Node<T>(obj); 
     if(root == null) { 
      root = n; 
     } else { 
      add(root, n); 
     } 
     size++; 
    } 

    private void add(Node<T> subtree, Node<T> n) { 
     if(subtree.getValue().compareTo(n.getValue()) > 0) { 
      if(subtree.getLeftChild() == null) { 
       subtree.setLeftChild(n); 
       n.setParent(subtree); 
      } else { 
       add(subtree.getLeftChild(), n); 
      } 
     } else { 
      if(subtree.getRightChild() == null) { 
       subtree.setRightChild(n); 
       n.setParent(subtree); 
      } else { 
       add(subtree.getRightChild(), n); 
      } 
     } 
    } 

    //returns the head of the queue 
    public T peek(){ 
     Node<T> current = root; 
     while(current.getLeftChild() != null){ 
      current = current.getLeftChild(); 
     } 
     return current.getValue(); 
    } 

    //removes the head of the queue and returns it 
    public T remove(){ 
     if(root == null){ 
      return null; 
     } 

     Node<T> current = root; 
     while(current.getLeftChild() != null){ 
      current = current.getLeftChild(); 
     } 
     if(current.getParent() == null) { 
      root = current.getRightChild(); 
      if(root != null){ 
       root.setParent(null); 
      } 
     } else { 
      current.getParent().setLeftChild(current.getRightChild()); 
      if(current.getRightChild() != null){ 
       current.getRightChild().setParent(current.getParent()); 
      } 
     } 
     size--; 
     return current.getValue(); 
    } 

    //returns the position of an element in the queue, or -1 if it is not found 
    public int search(T searchItem){ 
     String tempOrdered = inorder(root); 
     for(int i = 0; i<tempOrdered.length(); i++){ 
      if(String.valueOf(tempOrdered.charAt(i)).equals(searchItem.toString())){ 
       return i; 
      } 
     } 
     return -1; 
    } 

    //returns number of nodes in the tree 
    //returns the total number of elements in the queue 
    public int getSize(){ 
     return size; 
    } 
    public String inorder() { 
     inorder = ""; 
     if(root == null) 
      return inorder; 
     return inorder(root); 
    } 

    //returns an in-order, comma-separated string of every element in the queue 
    private String inorder(Node<T> n){ 
     if(n.getLeftChild() != null){ 
      inorder(n.getLeftChild()); 
     } 
     inorder += n.getValue(); 
     if(n.getRightChild() != null){ 
      inorder(n.getRightChild()); 
     } 
     return inorder; 
    } 

    public String preorder() { 
     preorder = ""; 
     if(root == null) 
      return preorder; 
     return preorder(root); 
    } 

    //returns a pre-ordered, comma-separated string of every element in the queue 
    private String preorder(Node<T> n){ 
     preorder+= n.getValue(); 
     if(n.getLeftChild() != null){ 
      preorder(n.getLeftChild()); 
     } 
     if(n.getRightChild() != null){ 
      preorder(n.getRightChild()); 
     } 

     return preorder; 
    } 

    //returns the height of the tree; returns -1 if the tree is empty 
    public int height(Node<T> n){ 
     if(n == null){ 
      return -1; 
     } 
     return Math.max(height(n.getLeftChild()), height(n.getRightChild()))+ 1; 
    } 

    //returns the root node 
    public Node<T> getRoot(){ 
     return root; 
    } 
} 

我不找人通过这个任务走在我 - 只是寻找一些建议，以我应该如何去这样做，所以我不破坏代码我猜测我需要做一些事情来检查每次添加或删除某些东西时树的平衡因子，然后重建树或在不平衡时“旋转”。

感谢您提前给出的任何建议。 :)欣赏所有的提示。

克里斯

Answer 1

的AVL tree文章在维基百科上给出了所有你需要实现这种自我平衡树（我特别喜欢the picture需要再平衡显示旋转）的。基本上你需要实现左右树的旋转，并根据文章中给出的规则在你的add和remove方法中使用它。

如果你更冒险，尝试实施红黑树。有关伪代码的很好的描述可以在Introduction to Algorithms中找到。