Измените 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;
    }
}

Я не ищу кого-то, кто проведет меня через это задание, - просто ищу совета относительно того, как мне следует поступить так, чтобы не сломатьсянаполовину код. Я предполагаю, что мне нужно будет что-то делать для проверки коэффициента баланса дерева каждый раз, когда что-то добавляется или удаляется, а затем восстанавливать дерево или «вращать», когда он не сбалансирован.1004 *

Спасибо за любой совет заранее.:) Цените все советы.

-Chris

Answer 1

Статья AVL tree в Википедии дает все необходимое для реализации этого вида самобалансируемого дерева (мне особенно нравится картинка , показывающая повороты, необходимые для восстановления баланса). В основном вам нужно реализовать левый и правый поворот дерева и использовать его в ваших add и remove методах в соответствии с правилами, приведенными в статье.

Если вы более предприимчивы, попробуйте реализовать красно-черное дерево. Хорошее описание с псевдокодом можно найти в Введение в алгоритмы .