Class AVLTree

From Ssdlpedia

Jump to: navigation, search

Contents

[edit] Synopsis of Class AVLTree<T>

public class AVLTree<T> extends BalancedSearchTree<T> { 
    /*
     * Forge (1)
     */
        AVLTree(); 
    /*
     * Type (11)
     */
        void invariant(); 
        boolean isEmpty(); 
        void clear(); 
        int count(); 
        int height(); 
        T findMin(); 
        T findMax(); 
        T findRoot(); 
        T find(T x); 
        void inorder(Visitor<T> v); 
        void insert(T x); 
}

Input types: Comparable<T>, Visitor<T>.

Output types: Comparable<T>.

[edit] Synopsis of Class AVLTree.Node<T>

static final class AVLTree.Node<T> implements Checkable, Serializable { 
    /*
     * Type (1)
     */
        void invariant(); 
    /*
     * Utilities (1)
     */
        static int height(Node<T> n); 
}

Input types: Comparable<T>.


[edit] Synopsis of Enum AVLTree.Node.BalancingState

enum AVLTree.Node.BalancingState { 
    /*
     * Type (4)
     */
        abstract Node<T> tipLeft(Node<T> n); 
        abstract Node<T> tipRight(Node<T> n); 
        Node<T> pivotLeft(Node<T> me, Node<T> parent); 
        Node<T> pivotRight(Node<T> me, Node<T> parent); 
    /*
     * Utilities (5)
     */
        static BalancingState[] values(); 
        static BalancingState valueOf(String name); 
        final static BalancingState BALANCED; 
        final static BalancingState LEFT; 
        final static BalancingState RIGHT; 
}

Input types: Comparable<T>, Node<T>.

Output types: Comparable<T>, Node<T>.

[edit] Code

// SSDLPedia
package il.ac.technion.cs.cs236700.tree;

import static il.ac.technion.cs.ssdl.utils.Box.box;
import static il.ac.technion.cs.ssdl.utils.DBC.*;
import il.ac.technion.cs.ssdl.stereotypes.Classical;
import il.ac.technion.cs.ssdl.stereotypes.Instantiable;
import il.ac.technion.cs.ssdl.utils.Defaults;
import il.ac.technion.cs.ssdl.utils.DBC.Checkable;

import java.io.Serializable;

/**
 * An implementation of an AVL tree data structure, minimizing conditionals by
 * using the State Design Pattern for representing the AVL balancing
 * factor of each tree node.
 * 
 * Author: Yossi Gil, the Technion.
 * See:  23/07/2008
 * <T> type of data stored at each tree node
 */
@Instantiable @Classical public class AVLTree<T extends Comparable<T>> extends BalancedSearchTree<T> {
    private static final long serialVersionUID = -292448374970233804L;
    /**
     * The root of this tree
     */
    Node<T> root = null;
    
    /**
     * All nodes in this tree are sorted, and each node in it maintains the AVL
     * property
     */
    @Override public void invariant() {
        inorder(new Visitor<T>() {
            T previous = null;
            
            @Override public void visit(final T current) {
                if (previous != null)
                    positive(current.compareTo(previous), "Previous = %s current = %s", previous, current);
                previous = current;
            }
        });
        if (root != null)
            root.invariant();
    }
    
    @Override public boolean isEmpty() {
        return root == null;
    }
    
    @Override public void clear() {
        root = null;
    }
    
    @Override public int count() {
        return count(root);
    }
    
    @Override public int height() {
        return Node.height(root);
    }
    
    private int count(final Node<T> n) {
        if (n == null)
            return 0;
        return 1 + count(n.left) + count(n.right);
    }
    
    @Override public T findMin() {
        return datatAt(findMin(root));
    }
    
    /**
     * Internal method to find the smallest item in a subtree.
     * 
     * <T> type of data stored at each node
     * n the node that roots the tree.
     * Return: node containing the smallest item.
     */
    private static <T extends Comparable<T>> Node<T> findMin(final Node<T> n) {
        if (n == null)
            return n;
        for (Node<T> $ = n;; $ = $.left)
            if ($.left == null)
                return $;
    }
    
    @Override public T findMax() {
        return datatAt(findMax(root));
    }
    
    @Override public T findRoot() {
        return datatAt(root);
    }
    
    /**
     * Internal method to find the largest item in a subtree.
     * 
     * <T> type of data stored at each node
     * n the node that roots the tree.
     * Return: node containing the largest item.
     */
    private static <T extends Comparable<T>> Node<T> findMax(final Node<T> n) {
        if (n == null)
            return n;
        for (Node<T> $ = n;; $ = $.right)
            if ($.right == null)
                return $;
    }
    
    @Override public T find(final T x) {
        return datatAt(find(x, root));
    }
    
    /**
     * Internal method to find an item in a subtree.
     * 
     * <T> type of data stored at each node
     * x is item to search for.
     * n the node that roots the tree.
     * Return: node containing the matched item.
     */
    private static <T extends Comparable<T>> Node<T> find(final T x, final Node<T> n) {
        for (Node<T> $ = n;;) {
            if ($ == null)
                return $;
            final int comparison = x.compareTo($.data);
            if (comparison == 0)
                return $;
            $ = comparison < 0 ? $.left : $.right;
        }
    }
    
    @Override public void inorder(final Visitor<T> v) {
        inorder(v, root);
    }
    
    /**
     * Traverse a subtree in sorted nodes order
     * 
     * n the node that roots the tree.
     * <T> type of data stored at each node
     * v action to carry out at each node
     */
    private static <T extends Comparable<T>> void inorder(final Visitor<T> v, final Node<T> n) {
        if (n == null)
            return;
        inorder(v, n.left);
        v.visit(n.data);
        inorder(v, n.right);
    }
    
    /**
     * Internal method to get the data field
     * 
     * <T> type of data stored at each node
     * n the node.
     * Return: the element field or null if t is null.
     */
    static <T extends Comparable<T>> T datatAt(final Node<T> n) {
        return n == null ? null : n.data;
    }
    
    @Override public void insert(final T x) {
        if (find(x) != null) // No need for insertion, nor for rebalancing
            return;
        root = insert(x, root);
        root = Defaults.to(balance(root, x), root);
    }
    
    /**
     * Internal method to insert into a subtree.
     * 
     * <T> type of data stored at each node
     * x the data item to insert.
     * n the node that roots the tree.
     * Return: the new root.
     */
    private static <T extends Comparable<T>> Node<T> insert(final T x, final Node<T> n) {
        if (n == null)
            return new Node<T>(x);
        final int comparison = x.compareTo(n.data);
        if (comparison == 0) // Found in tree, do nothing.
            return n;
        if (comparison < 0)
            n.left = insert(x, n.left);
        else
            n.right = insert(x, n.right);
        return n;
    }
    
    /**
     * Update the balance factor of a given node immediately after an
     * element was inserted at it. If the insertion caused the node to violate
     * the AVL balancing property, apply the appropriate rotations to restore
     * this property.
     * 
     * <T> type of data stored at the node
     * n the node under which a new element was inserted
     * x the element just inserted under this node
     * Return: null if the node's height increased as
     *         a result of the insertion and the incurred rotations; otherwise
     *         the node n
     */
    private static <T extends Comparable<T>> Node<T> balance(final Node<T> n, final T x) {
        nonnull(n);
        nonnull(x);
        final int comparison = x.compareTo(n.data);
        if (comparison == 0) // This is the leaf where the node was inserted.
            return null;
        if (comparison < 0) { // Node was inserted to the left of this node
            final Node<T> newLeft = balance(n.left, x);
            if (newLeft == null) // Height of left subtree increased
                return n.tipLeft();
            n.left = newLeft;
            return n;
        }
        // Node was inserted to the right of this node
        final Node<T> newRight = balance(n.right, x);
        if (newRight == null) // Height of right subtree increased
            return n.tipRight();
        n.right = newRight;
        return n;
    }
    
    static final class Node<T extends Comparable<T>> implements Checkable, Serializable {
        private static final long serialVersionUID = 8208109414910621069L;
        /**
         * Data stored in this node
         */
        final T data;
        /**
         * Where nodes with smaller data values can be found
         */
        Node<T> left = null;
        /**
         * Where nodes with smaller data values can be found
         */
        Node<T> right = null;
        /**
         * The tri-state AVL balancing factor of this node
         */
        BalancingState balancing = BalancingState.BALANCED;
        
        /**
         * Set the balancing state of this node
         * 
         * s The new state of this node
         * Return: the node itself
         */
        Node<T> setState(final BalancingState s) {
            balancing = s;
            return this;
        }
        
        /**
         * Instantiate a leaf node
         * 
         * data what to store in this node
         */
        Node(final T data) {
            this.data = data;
        }
        
        Node(final T data, final Node<T> left, final Node<T> right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
        
        @Override public void invariant() {
            nonnull(data);
            final int heightLeft = height(left);
            final int heightRight = height(right);
            nonnegative(heightLeft);
            nonnegative(heightRight);
            switch (heightLeft - heightRight) {
                case 1:
                    sure(balancing == BalancingState.LEFT, "\n\tBalancing = %s hLeft = %d hRight = %d Data = %s", balancing,
                            box(heightLeft), box(heightRight), data);
                    break;
                case 0:
                    sure(balancing == BalancingState.BALANCED, "\n\tBalancing = %s hLeft = %d hRight = %d Data = %s", balancing,
                            box(heightLeft), box(heightRight), data);
                    break;
                case -1:
                    sure(balancing == BalancingState.RIGHT, "\n\tBalancing = %s hLeft = %d hRight = %d Data = %s", balancing,
                            box(heightLeft), box(heightRight), data);
                    break;
                default:
                    unreachable("Node violates the AVL property: left height = %d right height = %d", heightLeft, heightRight);
            }
            if (right != null)
                right.invariant();
            if (left != null)
                left.invariant();
        }
        
        /**
         * Compute the height of a given node
         * 
         * <T> type of data stored at the node
         * n the given node
         * Return: 0 is t is null, a non-negative
         *         integer representing this node's height otherwise
         */
        public static <T extends Comparable<T>> int height(final Node<T> n) {
            if (n == null)
                return 0;
            return Math.max(height(n.left), height(n.right)) + 1;
        }
        
        /**
         * Fix the node balancing factor, and apply corrective rotations as
         * appropriate in the case that the height of the left subtree of this
         * node increased.
         * 
         * Return: null if the node's height
         *         increased as a result of the tipping and the incurred
         *         rotations; otherwise the node n or the node to
         *         replace it in case of rotations.
         */
        Node<T> tipLeft() {
            return balancing.tipLeft(this);
        }
        
        /**
         * Fix the node balancing factor, and apply corrective rotations as
         * appropriate in the case that the height of the right subtree of this
         * node increased.
         * 
         * Return: null if the node's height
         *         increased as a result of the tipping and the incurred
         *         rotations; otherwise the node n or the node to
         *         replace it in case of rotations.
         */
        Node<T> tipRight() {
            return balancing.tipRight(this);
        }
        
        /**
         * Execute a left-right, or left-left pivot at this node and its parent.
         * 
         * parent the parent of this node
         * Return: the new parent node, following the appropriate pivot
         *         operation
         */
        protected Node<T> pivotLeft(final Node<T> parent) {
            return balancing.pivotLeft(this, parent);
        }
        
        /**
         * Execute a right-right, or right-left pivot at this node and its
         * parent.
         * 
         * parent the parent of this node
         * Return: the new parent node, following the appropriate pivot
         *         operation
         */
        protected Node<T> pivotRight(final Node<T> parent) {
            return balancing.pivotRight(this, parent);
        }
        
        /**
         * The balancing state of an AVL node, which can be either
         * #BALANCED, #LEFT or #RIGHT inclined.
         * 
         * Author: Yossi Gil, the Technion.
         * See:  21/07/2008
         */
        enum BalancingState {
            /**
             * Heights of the left- and right- subtrees are the same
             */
            BALANCED() {
                @Override public <T extends Comparable<T>> Node<T> tipLeft(final Node<T> me) {
                    me.setState(LEFT);
                    return null; // height has increased
                }
                
                @Override public <T extends Comparable<T>> Node<T> tipRight(final Node<T> me) {
                    me.setState(RIGHT);
                    return null; // height has increased
                }
                
                @Override public <T extends Comparable<T>> Node<T> pivotLeft(final Node<T> me, final Node<T> parent) {
                    super.pivotLeft(me, parent);
                    unreachable();
                    return null;
                }
                
                @Override public <T extends Comparable<T>> Node<T> pivotRight(final Node<T> me, final Node<T> parent) {
                    super.pivotRight(me, parent);
                    unreachable();
                    return null;
                }
                
                @Override protected BalancingState getLRgrandparentBalancing() {
                    return BALANCED;
                }
                
                @Override protected BalancingState getLRparentBalancing() {
                    return BALANCED;
                }
                
                @Override protected BalancingState getRLgrandparentBalancing() {
                    return BALANCED;
                }
                
                @Override protected BalancingState getRLparentBalancing() {
                    return BALANCED;
                }
            },
            /**
             * Height of the left subtree is greater by one than that of the
             * right subtree.
             */
            LEFT() {
                @Override public <T extends Comparable<T>> Node<T> tipLeft(final Node<T> me) {
                    return me.left.pivotLeft(me);
                }
                
                @Override public <T extends Comparable<T>> Node<T> tipRight(final Node<T> me) {
                    return me.setState(BALANCED);
                }
                
                /**
                 * Implementation of LEFT-LEFT pivot
                 * 
                 * See: AVLTree.Node.BalancingState#pivotLeft(AVLTree.Node,
                 *      AVLTree.Node) Realizes a LEFT-LEFT pivot
                 */
                @Override public <T extends Comparable<T>> Node<T> pivotLeft(final Node<T> me, final Node<T> parent) {
                    parent.left = me.right;
                    me.right = parent;
                    me.balancing = parent.balancing = BALANCED;
                    return me;
                }
                
                /**
                 * Implementation of RIGHT-LEFT pivot
                 * 
                 * See: AVLTree.Node.BalancingState#pivotRight(AVLTree.Node,
                 *      AVLTree.Node) Realizes a RIGHT-LEFT pivot
                 */
                @Override public <T extends Comparable<T>> Node<T> pivotRight(final Node<T> me, final Node<T> parent) {
                    super.pivotRight(me, parent);
                    final Node<T> $ = me.left;
                    me.left = $.right;
                    me.balancing = $.balancing.getRLparentBalancing();
                    parent.right = $.left;
                    parent.balancing = $.balancing.getRLgrandparentBalancing();
                    $.right = me;
                    $.left = parent;
                    $.balancing = BALANCED;
                    return $;
                }
                
                @Override protected BalancingState getLRgrandparentBalancing() {
                    return RIGHT;
                }
                
                @Override protected BalancingState getLRparentBalancing() {
                    return BALANCED;
                }
                
                @Override protected BalancingState getRLgrandparentBalancing() {
                    return BALANCED;
                }
                
                @Override protected BalancingState getRLparentBalancing() {
                    return RIGHT;
                }
            },
            /**
             * Height of the right subtree is greater by one than that of the
             * left subtree.
             */
            RIGHT() {
                @Override public <T extends Comparable<T>> Node<T> tipLeft(final Node<T> me) {
                    return me.setState(BALANCED);
                }
                
                @Override public <T extends Comparable<T>> Node<T> tipRight(final Node<T> me) {
                    return me.right.pivotRight(me);
                }
                
                /**
                 * Implementation of LEFT-RIGHT pivot
                 * 
                 * See: AVLTree.Node.BalancingState#pivotLeft(AVLTree.Node,
                 *      AVLTree.Node) 
                 */
                @Override public <T extends Comparable<T>> Node<T> pivotLeft(final Node<T> me, final Node<T> parent) {
                    super.pivotLeft(me, parent);
                    final Node<T> $ = me.right;
                    me.right = $.left;
                    me.balancing = $.balancing.getLRparentBalancing();
                    parent.left = $.right;
                    parent.balancing = $.balancing.getLRgrandparentBalancing();
                    $.left = me;
                    $.right = parent;
                    $.balancing = BALANCED;
                    return $;
                }
                
                /**
                 * Implementation of RIGHT-RIGHT pivot
                 * 
                 * See: AVLTree.Node.BalancingState#pivotRight(AVLTree.Node,
                 *      AVLTree.Node)
                 */
                @Override public <T extends Comparable<T>> Node<T> pivotRight(final Node<T> me, final Node<T> parent) {
                    parent.right = me.left;
                    me.left = parent;
                    me.balancing = parent.balancing = BALANCED;
                    return me;
                }
                
                @Override protected BalancingState getLRgrandparentBalancing() {
                    return BALANCED;
                }
                
                @Override protected BalancingState getLRparentBalancing() {
                    return LEFT;
                }
                
                @Override protected BalancingState getRLgrandparentBalancing() {
                    return LEFT;
                }
                
                @Override protected BalancingState getRLparentBalancing() {
                    return BALANCED;
                }
            };
            /**
             * Change the balancing factor and apply corrective rotations as
             * appropriate in the case that the height of the left subtree of a
             * node in this state increased.
             * 
             * Return: null if the node's height
             *         increased as a result of the tipping and the incurred
             *         rotations; otherwise the node n itself (in
             *         case no rotations were necessary), or the node to replace
             *         it in case rotations were applied.
             * <T> type of data stored at nodes
             * n the context, that is the node at which tipping of the
             *            scale to the left took place.
             */
            public abstract <T extends Comparable<T>> Node<T> tipLeft(Node<T> n);
            
            /**
             * Change the balancing factor and apply corrective rotations as
             * appropriate in the case that the height of the right subtree of a
             * node in this state increased.
             * 
             * Return: null if the node's height
             *         increased as a result of the tipping and the incurred
             *         rotations; otherwise the node n itself (in
             *         case no rotations were necessary), or the node to replace
             *         it in case rotations were applied.
             * <T> type of data stored at nodes
             * n the context, that is the node at which tipping of the
             *            scale to the left took place.
             */
            public abstract <T extends Comparable<T>> Node<T> tipRight(Node<T> n);
            
            /**
             * Pivoting action, in case pivoting is required, and the current
             * node is the left child of its parent.
             * 
             * <T> type of data stored at nodes
             * me the child node
             * parent the parent node
             * Return: the new parent node
             */
            public <T extends Comparable<T>> Node<T> pivotLeft(final Node<T> me, final Node<T> parent) {
                // Default implementation, setting the method contract
                nonnull(parent);
                nonnull(me);
                require(parent.left == me);
                return parent;
            }
            
            /**
             * Pivoting action, in case pivoting is required, and the current
             * node is the right child of its parent.
             * 
             * <T> type of data stored at nodes
             * me the child node
             * parent the parent node
             * Return: the new parent node
             */
            public <T extends Comparable<T>> Node<T> pivotRight(final Node<T> me, final Node<T> parent) {
                // Default implementation, setting the method contract
                nonnull(parent);
                nonnull(me);
                require(parent.right == me);
                return parent;
            }
            
            /**
             * Return: the balancing state of the parent of this node, in the
             *         case a node in this state is the grandchild node involved
             *         in LEFT-RIGHT rotation.
             */
            protected abstract BalancingState getLRparentBalancing();
            
            /**
             * Return: the balancing state of the grandparent of this node, in
             *         the case a node in this state is the grandchild node
             *         involved in LEFT-RIGHT rotation.
             */
            protected abstract BalancingState getLRgrandparentBalancing();
            
            /**
             * Return: the balancing state of the parent of this node, in the
             *         case a node in this state is the grandchild node involved
             *         in RIGHT-LEFT rotation.
             */
            protected abstract BalancingState getRLparentBalancing();
            
            /**
             * Return: the balancing state of the grandparent of this node, in
             *         the case a node in this state is the grandchild node
             *         involved in RIGHT-LEFT rotation.
             */
            protected abstract BalancingState getRLgrandparentBalancing();
        }
    }
}

[edit] Metrics

MetricValueAcronymExplanation
LOC632Lines Of CodeTotal number of lines in the code
SCC166SemiColons CountTotal number of semicolon tokens found in the code.
NOT2412Number Of TokensComments, whitespace and text which cannot be made into a token not included.
VCC14220Visible Characters CountThe total number of non-white (i.e., not space, tab, newline, carriage return, form feed) characters.
CCC7888Code Characters CountTotal number of non-white characters in tokens. White space characters in string and character literals are not counted.
UIC82Unique Identifiers CountThe number of different identifiers found in the code
WHC8Weighted Horizontal ComplexityA heuritistic on horizontal complexity

[edit] Statistics

StatiticValue
Average token length 3.3
Tokens/line 3.8
Visible characters/line 23
Code characters/line 12
Semicolons/tokens6%
Comment text percentage44%

[edit] Tokens by Kind

Token KindOccurrences
KEYWORD330
OPERATOR329
LITERAL20
ID886
PUNCTUATION847
COMMENT49
OTHER1151
Retrieved from "http://ssdl-wiki.cs.technion.ac.il/wiki/index.php/Class_AVLTree"
Personal tools