In java create an AVLTreeMap class which implements some Map

In java, create an AVLTreeMap class which implements some Map interface.

Solution

package com;

import java.util.ArrayList;
import java.util.List;
public class AVLTree<T extends Comparable<T>> extends BinarySearchTree<T> implements BinarySearchTree.INodeCreator<T> {

    private enum Balance {
        LEFT_LEFT, LEFT_RIGHT, RIGHT_LEFT, RIGHT_RIGHT
    };

       public AVLTree() {
        this.creator = this;
    }

      public AVLTree(INodeCreator<T> creator) {
        super(creator);
    }

    protected Node<T> addValue(T id) {
        Node<T> nodeToReturn = super.addValue(id);
        AVLNode<T> nodeAdded = (AVLNode<T>) nodeToReturn;

        while (nodeAdded != null) {
            nodeAdded.updateHeight();
            balanceAfterInsert(nodeAdded);
            nodeAdded = (AVLNode<T>) nodeAdded.parent;
        }

        return nodeToReturn;
    }

    private void balanceAfterInsert(AVLNode<T> node) {
        int balanceFactor = node.getBalanceFactor();
        if (balanceFactor > 1 || balanceFactor < -1) {
            AVLNode<T> parent = null;
            AVLNode<T> child = null;
            Balance balance = null;
            if (balanceFactor < 0) {
                parent = (AVLNode<T>) node.lesser;
                balanceFactor = parent.getBalanceFactor();
                if (balanceFactor < 0) {
                    child = (AVLNode<T>) parent.lesser;
                    balance = Balance.LEFT_LEFT;
                } else {
                    child = (AVLNode<T>) parent.greater;
                    balance = Balance.LEFT_RIGHT;
                }
            } else {
                parent = (AVLNode<T>) node.greater;
                balanceFactor = parent.getBalanceFactor();
                if (balanceFactor < 0) {
                    child = (AVLNode<T>) parent.lesser;
                    balance = Balance.RIGHT_LEFT;
                } else {
                    child = (AVLNode<T>) parent.greater;
                    balance = Balance.RIGHT_RIGHT;
                }
            }

            if (balance == Balance.LEFT_RIGHT) {
              
                rotateLeft(parent);
                rotateRight(node);
            }
           else if (balance == Balance.RIGHT_LEFT) {
              
                rotateRight(parent);
                rotateLeft(node);
            }
            else if (balance == Balance.LEFT_LEFT) {
             
                rotateRight(node);
            }
          else
           {
            
                rotateLeft(node);
            }

            node.updateHeight();
            child.updateHeight();
            parent.updateHeight();
        }
    }

    protected Node<T> removeValue(T value)
         {
                Node<T> nodeToRemoved = this.getNode(value);
        if (nodeToRemoved != null)
               {
                       Node<T> replacementNode = this.getReplacementNode(nodeToRemoved);

                        AVLNode<T> nodeToRefactor = null;
            if (replacementNode != null)
                nodeToRefactor = (AVLNode<T>) replacementNode.parent;
            if (nodeToRefactor == null)
                nodeToRefactor = (AVLNode<T>) nodeToRemoved.parent;
            if (nodeToRefactor != null && nodeToRefactor.equals(nodeToRemoved))
                nodeToRefactor = (AVLNode<T>) replacementNode;

                       replaceNodeWithNode(nodeToRemoved, replacementNode);

                        if (nodeToRefactor != null)
             {
                while (nodeToRefactor != null)
                   {
                    nodeToRefactor.updateHeight();
                    balanceAfterDelete(nodeToRefactor);
                    nodeToRefactor = (AVLNode<T>) nodeToRefactor.parent;
                }
            }
        }
        return nodeToRemoved;
    }

        private void balanceAfterDelete(AVLNode<T> node) {
        int balanceFactor = node.getBalanceFactor();
        if (balanceFactor == -2 || balanceFactor == 2) {
            if (balanceFactor == -2) {
                AVLNode<T> ll = (AVLNode<T>) node.lesser.lesser;
                int lesser = (ll != null) ? ll.height : 0;
                AVLNode<T> lr = (AVLNode<T>) node.lesser.greater;
                int greater = (lr != null) ? lr.height : 0;
                if (lesser >= greater) {
                    rotateRight(node);
                    node.updateHeight();
                    if (node.parent != null)
                        ((AVLNode<T>) node.parent).updateHeight();
                } else {
                    rotateLeft(node.lesser);
                    rotateRight(node);

                    AVLNode<T> p = (AVLNode<T>) node.parent;
                    if (p.lesser != null)
                        ((AVLNode<T>) p.lesser).updateHeight();
                    if (p.greater != null)
                        ((AVLNode<T>) p.greater).updateHeight();
                    p.updateHeight();
                }
            } else if (balanceFactor == 2) {
                AVLNode<T> rr = (AVLNode<T>) node.greater.greater;
                int greater = (rr != null) ? rr.height : 0;
                AVLNode<T> rl = (AVLNode<T>) node.greater.lesser;
                int lesser = (rl != null) ? rl.height : 0;
                if (greater >= lesser) {
                    rotateLeft(node);
                    node.updateHeight();
                    if (node.parent != null)
                        ((AVLNode<T>) node.parent).updateHeight();
                } else {
                    rotateRight(node.greater);
                    rotateLeft(node);

                    AVLNode<T> p = (AVLNode<T>) node.parent;
                    if (p.lesser != null)
                        ((AVLNode<T>) p.lesser).updateHeight();
                    if (p.greater != null)
                        ((AVLNode<T>) p.greater).updateHeight();
                    p.updateHeight();
                }
            }
        }
    }

      protected boolean validateNode(Node<T> node) {
        boolean bst = super.validateNode(node);
        if (!bst)
            return false;

        AVLNode<T> avlNode = (AVLNode<T>) node;
        int balanceFactor = avlNode.getBalanceFactor();
        if (balanceFactor > 1 || balanceFactor < -1) {
            return false;
        }
        if (avlNode.isLeaf()) {
            if (avlNode.height != 1)
                return false;
        } else {
            AVLNode<T> avlNodeLesser = (AVLNode<T>) avlNode.lesser;
            int lesserHeight = 1;
            if (avlNodeLesser != null)
                lesserHeight = avlNodeLesser.height;

            AVLNode<T> avlNodeGreater = (AVLNode<T>) avlNode.greater;
            int greaterHeight = 1;
            if (avlNodeGreater != null)
                greaterHeight = avlNodeGreater.height;

            if (avlNode.height == (lesserHeight + 1) || avlNode.height == (greaterHeight + 1)) {
                return true;
            } else {
                return false;
            }
        }

        return true;
    }

    public String toString() {
        return AVLTreePrinter.getString(this);
    }

    public Node<T> createNewNode(Node<T> parent, T id) {
        return (new AVLNode<T>(parent, id));
    }

    protected static class AVLNode<T extends Comparable<T>> extends Node<T> {

        protected int height = 1;

     
        protected AVLNode(Node<T> parent, T value) {
            super(parent, value);
        }

    
        protected boolean isLeaf() {
            return ((lesser == null) && (greater == null));
        }

      
        protected void updateHeight() {
            int lesserHeight = 0;
            int greaterHeight = 0;
            if (lesser != null) {
                AVLNode<T> lesserAVLNode = (AVLNode<T>) lesser;
                lesserHeight = lesserAVLNode.height;
            }
            if (greater != null) {
                AVLNode<T> greaterAVLNode = (AVLNode<T>) greater;
                greaterHeight = greaterAVLNode.height;
            }

            if (lesserHeight > greaterHeight) {
                height = lesserHeight + 1;
            } else {
                height = greaterHeight + 1;
            }
        }

     
        protected int getBalanceFactor() {
            int lesserHeight = 0;
            int greaterHeight = 0;
            if (lesser != null) {
                AVLNode<T> lesserAVLNode = (AVLNode<T>) lesser;
                lesserHeight = lesserAVLNode.height;
            }
            if (greater != null) {
                AVLNode<T> greaterAVLNode = (AVLNode<T>) greater;
                greaterHeight = greaterAVLNode.height;
            }
            return greaterHeight - lesserHeight;
        }

     
        public String toString() {
            return \"value=\" + id + \" height=\" + height + \" parent=\" + ((parent != null) ? parent.id : \"NULL\")
                    + \" lesser=\" + ((lesser != null) ? lesser.id : \"NULL\") + \" greater=\"
                    + ((greater != null) ? greater.id : \"NULL\");
        }
    }

    protected static class AVLTreePrinter {

        public static <T extends Comparable<T>> String getString(AVLTree<T> tree) {
            if (tree.root == null)
                return \"Tree has no nodes.\";
            return getString((AVLNode<T>) tree.root, \"\", true);
        }

        public static <T extends Comparable<T>> String getString(AVLNode<T> node) {
            if (node == null)
                return \"Sub-tree has no nodes.\";
            return getString(node, \"\", true);
        }

        private static <T extends Comparable<T>> String getString(AVLNode<T> node, String prefix, boolean isTail) {
            StringBuilder builder = new StringBuilder();

            builder.append(prefix + (isTail ? \" \" : \" \") + \"(\" + node.height + \") \" + node.id + \"\ \");
            List<Node<T>> children = null;
            if (node.lesser != null || node.greater != null) {
                children = new ArrayList<Node<T>>(2);
                if (node.lesser != null)
                    children.add(node.lesser);
                if (node.greater != null)
                    children.add(node.greater);
            }
            if (children != null) {
                for (int i = 0; i < children.size() - 1; i++) {
                    builder.append(getString((AVLNode<T>) children.get(i), prefix + (isTail ? \"    \" : \"   \"), false));
                }
                if (children.size() >= 1) {
                    builder.append(getString((AVLNode<T>) children.get(children.size() - 1), prefix
                            + (isTail ? \"    \" : \"   \"), true));
                }
            }

            return builder.toString();
        }
    }