Cfrtjryk

There is an implementation of AVL Tree. This is the link where BST class can be found. Since AVL tree is a BST, therefore, functions are omitted in here since it has already been coded and checked.

* AVL Node

package nodes.treeNodes.binaryTreesNode.avlNode;



import java.util.Iterator;

import java.util.LinkedList;

import java.util.List;



public class AVLNode<T>

{

    private AVLNode<T> parent;

    private AVLNode<T> left;

    private AVLNode<T> right;

    private T data;

    private int leftChildHeight;

    private int rightChildHeight;



    public AVLNode(T data)

    {

        this(null, null, null, data);

    }



    public AVLNode(AVLNode<T> parent, AVLNode<T> left, AVLNode<T> right, T data)

    {

        this.parent = parent;

        this.left = left;

        this.right = right;

        this.data = data;

        fixHeight();

    }



    //Setters and Getters are omitted    



    public int fixHeight()

    {

        leftChildHeight = rightChildHeight = -1;

        AVLNode<T> left = getLeft();

        AVLNode<T> right = getRight();

        if (left != null)

            leftChildHeight = 1 + MAX(left.leftChildHeight, left.rightChildHeight);

        if (right != null)

            rightChildHeight = 1 + MAX(right.leftChildHeight, right.rightChildHeight);

        if (leftChildHeight > rightChildHeight)

            return leftChildHeight;

        return rightChildHeight;

    }



    public Iterator<AVLNode> children()

    {

        List<AVLNode> childList = new LinkedList<>();

        if(this.getLeft() != null) childList.add(getLeft());

        if(this.getRight() != null) childList.add(getRight());

        return childList.iterator();

    }



    public static int MAX(int x, int y)

    {

        if(x > y) return x;

        return y;

    }

}

* AVL Class

package trees.binaryTrees.avlTree;



import nodes.treeNodes.binaryTreesNode.avlNode.AVLNode;



import java.util.Iterator;

import java.util.LinkedList;

import java.util.List;

import java.util.Queue;

import java.util.concurrent.ConcurrentLinkedQueue;



public class AVLTree<T extends Comparable<T>>

{

    private AVLNode<T> root;

    private int size;



    public AVLTree() {}



    //Similar BST functions are omitted



    private void reBalance(AVLNode<T> node)

    {

        if(node == null) return;

        int oldMaxHt = AVLNode.MAX(node.getLeftChildHeight(), node.getRightChildHeight());

        int newHt = node.fixHeight();



        if(newHt > node.getLeftChildHeight() + 1 || newHt > node.getRightChildHeight() + 1)

        {

            //LL

            if(node.getLeftChildHeight() > node.getRightChildHeight() && node.getLeft().getLeftChildHeight() >= node.getLeft().getRightChildHeight())

            {

                rotate(node, node.getLeft(), node.getLeft().getLeft(), node,

                    node.getLeft().getLeft().getLeft(), node.getLeft().getLeft().getRight(),

                    node.getLeft().getRight(), node.getRight());

            }

            else if(node.getLeftChildHeight() > node.getRightChildHeight() && node.getLeft().getRightChildHeight() > node.getLeft().getLeftChildHeight()) //LR

            {

                rotate(node, node.getLeft().getRight(), node.getLeft(), node, node.getLeft().getLeft(),

                    node.getLeft().getRight().getLeft(), node.getLeft().getRight().getRight(), node.getRight());

            }

            else if(node.getRightChildHeight() > node.getLeftChildHeight() && node.getRight().getRightChildHeight() >= node.getRight().getLeftChildHeight()) //RR

            {

                rotate(node, node.getRight(), node, node.getRight().getRight(),

                    node.getLeft(), node.getRight().getLeft(), node.getRight().getRight().getLeft(),

                    node.getRight().getRight().getRight());

            }

            else if(node.getRightChildHeight() > node.getLeftChildHeight() && node.getRight().getLeftChildHeight() > node.getRight().getRightChildHeight()) //RL

            {

                rotate(node, node.getRight().getLeft(), node, node.getRight(), node.getLeft(),

                    node.getRight().getLeft().getLeft(), node.getRight().getLeft().getRight(),

                    node.getRight().getRight());

            }

        }

        newHt = node.fixHeight();

        if(oldMaxHt != newHt) reBalance(node.getParent());

    }



    private void rotate(AVLNode<T> problemNode, AVLNode<T> root, AVLNode<T> left, AVLNode<T> right,

                              AVLNode<T> subTree1, AVLNode<T> subTree2, AVLNode<T> subTree3, AVLNode<T> subTree4)

    {

        AVLNode<T> newLeft = new AVLNode <>(problemNode, subTree1, subTree2, left.getData());

        AVLNode<T> newRight = new AVLNode <>(problemNode, subTree3, subTree4, right.getData());



        if(subTree1 != null) subTree1.setParent(newLeft);

        if(subTree2 != null) subTree2.setParent(newLeft);

        if(subTree3 != null) subTree3.setParent(newRight);

        if(subTree4 != null) subTree4.setParent(newRight);



        newLeft.fixHeight();

        newRight.fixHeight();



        problemNode.setData(root.getData());

        problemNode.setLeft(newLeft);

        problemNode.setRight(newRight);

    }



    @Override

    public String toString()

    {

        return inOrder().toString();

    }

}