java - 修改 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 中找到一个很好的伪代码描述。 .