home | career | drupal | java | mac | mysql | perl | scala | uml | unix  

Java example source code file (AVLTree.java)

This example Java source code file (AVLTree.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

avltree, balanced, comparable, deprecated, left_high, node, right_high, skew

The AVLTree.java Java example source code

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.math3.geometry.partitioning.utilities;

/** This class implements AVL trees.
 *
 * <p>The purpose of this class is to sort elements while allowing
 * duplicate elements (i.e. such that {@code a.equals(b)} is
 * true). The {@code SortedSet} interface does not allow this, so
 * a specific class is needed. Null elements are not allowed.</p>
 *
 * <p>Since the {@code equals} method is not sufficient to
 * differentiate elements, the {@link #delete delete} method is
 * implemented using the equality operator.</p>
 *
 * <p>In order to clearly mark the methods provided here do not have
 * the same semantics as the ones specified in the
 * {@code SortedSet} interface, different names are used
 * ({@code add} has been replaced by {@link #insert insert} and
 * {@code remove} has been replaced by {@link #delete
 * delete}).</p>
 *
 * <p>This class is based on the C implementation Georg Kraml has put
 * in the public domain. Unfortunately, his <a
 * href="www.purists.org/georg/avltree/index.html">page</a> seems not
 * to exist any more.</p>
 *
 * @param <T> the type of the elements
 *
 * @since 3.0
 * @deprecated as of 3.4, this class is not used anymore and considered
 * to be out of scope of Apache Commons Math
 */
@Deprecated
public class AVLTree<T extends Comparable {

    /** Top level node. */
    private Node top;

    /** Build an empty tree.
     */
    public AVLTree() {
        top = null;
    }

    /** Insert an element in the tree.
     * @param element element to insert (silently ignored if null)
     */
    public void insert(final T element) {
        if (element != null) {
            if (top == null) {
                top = new Node(element, null);
            } else {
                top.insert(element);
            }
        }
    }

    /** Delete an element from the tree.
     * <p>The element is deleted only if there is a node {@code n}
     * containing exactly the element instance specified, i.e. for which
     * {@code n.getElement() == element}. This is purposely
     * <em>different from the specification of the
     * {@code java.util.Set} {@code remove} method (in fact,
     * this is the reason why a specific class has been developed).</p>
     * @param element element to delete (silently ignored if null)
     * @return true if the element was deleted from the tree
     */
    public boolean delete(final T element) {
        if (element != null) {
            for (Node node = getNotSmaller(element); node != null; node = node.getNext()) {
                // loop over all elements neither smaller nor larger
                // than the specified one
                if (node.element == element) {
                    node.delete();
                    return true;
                } else if (node.element.compareTo(element) > 0) {
                    // all the remaining elements are known to be larger,
                    // the element is not in the tree
                    return false;
                }
            }
        }
        return false;
    }

    /** Check if the tree is empty.
     * @return true if the tree is empty
     */
    public boolean isEmpty() {
        return top == null;
    }


    /** Get the number of elements of the tree.
     * @return number of elements contained in the tree
     */
    public int size() {
        return (top == null) ? 0 : top.size();
    }

    /** Get the node whose element is the smallest one in the tree.
     * @return the tree node containing the smallest element in the tree
     * or null if the tree is empty
     * @see #getLargest
     * @see #getNotSmaller
     * @see #getNotLarger
     * @see Node#getPrevious
     * @see Node#getNext
     */
    public Node getSmallest() {
        return (top == null) ? null : top.getSmallest();
    }

    /** Get the node whose element is the largest one in the tree.
     * @return the tree node containing the largest element in the tree
     * or null if the tree is empty
     * @see #getSmallest
     * @see #getNotSmaller
     * @see #getNotLarger
     * @see Node#getPrevious
     * @see Node#getNext
     */
    public Node getLargest() {
        return (top == null) ? null : top.getLargest();
    }

    /** Get the node whose element is not smaller than the reference object.
     * @param reference reference object (may not be in the tree)
     * @return the tree node containing the smallest element not smaller
     * than the reference object or null if either the tree is empty or
     * all its elements are smaller than the reference object
     * @see #getSmallest
     * @see #getLargest
     * @see #getNotLarger
     * @see Node#getPrevious
     * @see Node#getNext
     */
    public Node getNotSmaller(final T reference) {
        Node candidate = null;
        for (Node node = top; node != null;) {
            if (node.element.compareTo(reference) < 0) {
                if (node.right == null) {
                    return candidate;
                }
                node = node.right;
            } else {
                candidate = node;
                if (node.left == null) {
                    return candidate;
                }
                node = node.left;
            }
        }
        return null;
    }

    /** Get the node whose element is not larger than the reference object.
     * @param reference reference object (may not be in the tree)
     * @return the tree node containing the largest element not larger
     * than the reference object (in which case the node is guaranteed
     * not to be empty) or null if either the tree is empty or all its
     * elements are larger than the reference object
     * @see #getSmallest
     * @see #getLargest
     * @see #getNotSmaller
     * @see Node#getPrevious
     * @see Node#getNext
     */
    public Node getNotLarger(final T reference) {
        Node candidate = null;
        for (Node node = top; node != null;) {
            if (node.element.compareTo(reference) > 0) {
                if (node.left == null) {
                    return candidate;
                }
                node = node.left;
            } else {
                candidate = node;
                if (node.right == null) {
                    return candidate;
                }
                node = node.right;
            }
        }
        return null;
    }

    /** Enum for tree skew factor. */
    private enum Skew {
        /** Code for left high trees. */
        LEFT_HIGH,

        /** Code for right high trees. */
        RIGHT_HIGH,

        /** Code for Skew.BALANCED trees. */
        BALANCED;
    }

    /** This class implements AVL trees nodes.
     * <p>AVL tree nodes implement all the logical structure of the
     * tree. Nodes are created by the {@link AVLTree AVLTree} class.</p>
     * <p>The nodes are not independant from each other but must obey
     * specific balancing constraints and the tree structure is
     * rearranged as elements are inserted or deleted from the tree. The
     * creation, modification and tree-related navigation methods have
     * therefore restricted access. Only the order-related navigation,
     * reading and delete methods are public.</p>
     * @see AVLTree
     */
    public class Node {

        /** Element contained in the current node. */
        private T element;

        /** Left sub-tree. */
        private Node left;

        /** Right sub-tree. */
        private Node right;

        /** Parent tree. */
        private Node parent;

        /** Skew factor. */
        private Skew skew;

        /** Build a node for a specified element.
         * @param element element
         * @param parent parent node
         */
        Node(final T element, final Node parent) {
            this.element = element;
            left         = null;
            right        = null;
            this.parent  = parent;
            skew         = Skew.BALANCED;
        }

        /** Get the contained element.
         * @return element contained in the node
         */
        public T getElement() {
            return element;
        }

        /** Get the number of elements of the tree rooted at this node.
         * @return number of elements contained in the tree rooted at this node
         */
        int size() {
            return 1 + ((left  == null) ? 0 : left.size()) + ((right == null) ? 0 : right.size());
        }

        /** Get the node whose element is the smallest one in the tree
         * rooted at this node.
         * @return the tree node containing the smallest element in the
         * tree rooted at this node or null if the tree is empty
         * @see #getLargest
         */
        Node getSmallest() {
            Node node = this;
            while (node.left != null) {
                node = node.left;
            }
            return node;
        }

        /** Get the node whose element is the largest one in the tree
         * rooted at this node.
         * @return the tree node containing the largest element in the
         * tree rooted at this node or null if the tree is empty
         * @see #getSmallest
         */
        Node getLargest() {
            Node node = this;
            while (node.right != null) {
                node = node.right;
            }
            return node;
        }

        /** Get the node containing the next smaller or equal element.
         * @return node containing the next smaller or equal element or
         * null if there is no smaller or equal element in the tree
         * @see #getNext
         */
        public Node getPrevious() {

            if (left != null) {
                final Node node = left.getLargest();
                if (node != null) {
                    return node;
                }
            }

            for (Node node = this; node.parent != null; node = node.parent) {
                if (node != node.parent.left) {
                    return node.parent;
                }
            }

            return null;

        }

        /** Get the node containing the next larger or equal element.
         * @return node containing the next larger or equal element (in
         * which case the node is guaranteed not to be empty) or null if
         * there is no larger or equal element in the tree
         * @see #getPrevious
         */
        public Node getNext() {

            if (right != null) {
                final Node node = right.getSmallest();
                if (node != null) {
                    return node;
                }
            }

            for (Node node = this; node.parent != null; node = node.parent) {
                if (node != node.parent.right) {
                    return node.parent;
                }
            }

            return null;

        }

        /** Insert an element in a sub-tree.
         * @param newElement element to insert
         * @return true if the parent tree should be re-Skew.BALANCED
         */
        boolean insert(final T newElement) {
            if (newElement.compareTo(this.element) < 0) {
                // the inserted element is smaller than the node
                if (left == null) {
                    left = new Node(newElement, this);
                    return rebalanceLeftGrown();
                }
                return left.insert(newElement) ? rebalanceLeftGrown() : false;
            }

            // the inserted element is equal to or greater than the node
            if (right == null) {
                right = new Node(newElement, this);
                return rebalanceRightGrown();
            }
            return right.insert(newElement) ? rebalanceRightGrown() : false;

        }

        /** Delete the node from the tree.
         */
        public void delete() {
            if ((parent == null) && (left == null) && (right == null)) {
                // this was the last node, the tree is now empty
                element = null;
                top     = null;
            } else {

                Node node;
                Node child;
                boolean leftShrunk;
                if ((left == null) && (right == null)) {
                    node       = this;
                    element    = null;
                    leftShrunk = node == node.parent.left;
                    child      = null;
                } else {
                    node       = (left != null) ? left.getLargest() : right.getSmallest();
                    element    = node.element;
                    leftShrunk = node == node.parent.left;
                    child      = (node.left != null) ? node.left : node.right;
                }

                node = node.parent;
                if (leftShrunk) {
                    node.left = child;
                } else {
                    node.right = child;
                }
                if (child != null) {
                    child.parent = node;
                }

                while (leftShrunk ? node.rebalanceLeftShrunk() : node.rebalanceRightShrunk()) {
                    if (node.parent == null) {
                        return;
                    }
                    leftShrunk = node == node.parent.left;
                    node = node.parent;
                }

            }
        }

        /** Re-balance the instance as left sub-tree has grown.
         * @return true if the parent tree should be reSkew.BALANCED too
         */
        private boolean rebalanceLeftGrown() {
            switch (skew) {
            case LEFT_HIGH:
                if (left.skew == Skew.LEFT_HIGH) {
                    rotateCW();
                    skew       = Skew.BALANCED;
                    right.skew = Skew.BALANCED;
                } else {
                    final Skew s = left.right.skew;
                    left.rotateCCW();
                    rotateCW();
                    switch(s) {
                    case LEFT_HIGH:
                        left.skew  = Skew.BALANCED;
                        right.skew = Skew.RIGHT_HIGH;
                        break;
                    case RIGHT_HIGH:
                        left.skew  = Skew.LEFT_HIGH;
                        right.skew = Skew.BALANCED;
                        break;
                    default:
                        left.skew  = Skew.BALANCED;
                        right.skew = Skew.BALANCED;
                    }
                    skew = Skew.BALANCED;
                }
                return false;
            case RIGHT_HIGH:
                skew = Skew.BALANCED;
                return false;
            default:
                skew = Skew.LEFT_HIGH;
                return true;
            }
        }

        /** Re-balance the instance as right sub-tree has grown.
         * @return true if the parent tree should be reSkew.BALANCED too
         */
        private boolean rebalanceRightGrown() {
            switch (skew) {
            case LEFT_HIGH:
                skew = Skew.BALANCED;
                return false;
            case RIGHT_HIGH:
                if (right.skew == Skew.RIGHT_HIGH) {
                    rotateCCW();
                    skew      = Skew.BALANCED;
                    left.skew = Skew.BALANCED;
                } else {
                    final Skew s = right.left.skew;
                    right.rotateCW();
                    rotateCCW();
                    switch (s) {
                    case LEFT_HIGH:
                        left.skew  = Skew.BALANCED;
                        right.skew = Skew.RIGHT_HIGH;
                        break;
                    case RIGHT_HIGH:
                        left.skew  = Skew.LEFT_HIGH;
                        right.skew = Skew.BALANCED;
                        break;
                    default:
                        left.skew  = Skew.BALANCED;
                        right.skew = Skew.BALANCED;
                    }
                    skew = Skew.BALANCED;
                }
                return false;
            default:
                skew = Skew.RIGHT_HIGH;
                return true;
            }
        }

        /** Re-balance the instance as left sub-tree has shrunk.
         * @return true if the parent tree should be reSkew.BALANCED too
         */
        private boolean rebalanceLeftShrunk() {
            switch (skew) {
            case LEFT_HIGH:
                skew = Skew.BALANCED;
                return true;
            case RIGHT_HIGH:
                if (right.skew == Skew.RIGHT_HIGH) {
                    rotateCCW();
                    skew      = Skew.BALANCED;
                    left.skew = Skew.BALANCED;
                    return true;
                } else if (right.skew == Skew.BALANCED) {
                    rotateCCW();
                    skew      = Skew.LEFT_HIGH;
                    left.skew = Skew.RIGHT_HIGH;
                    return false;
                } else {
                    final Skew s = right.left.skew;
                    right.rotateCW();
                    rotateCCW();
                    switch (s) {
                    case LEFT_HIGH:
                        left.skew  = Skew.BALANCED;
                        right.skew = Skew.RIGHT_HIGH;
                        break;
                    case RIGHT_HIGH:
                        left.skew  = Skew.LEFT_HIGH;
                        right.skew = Skew.BALANCED;
                        break;
                    default:
                        left.skew  = Skew.BALANCED;
                        right.skew = Skew.BALANCED;
                    }
                    skew = Skew.BALANCED;
                    return true;
                }
            default:
                skew = Skew.RIGHT_HIGH;
                return false;
            }
        }

        /** Re-balance the instance as right sub-tree has shrunk.
         * @return true if the parent tree should be reSkew.BALANCED too
         */
        private boolean rebalanceRightShrunk() {
            switch (skew) {
            case RIGHT_HIGH:
                skew = Skew.BALANCED;
                return true;
            case LEFT_HIGH:
                if (left.skew == Skew.LEFT_HIGH) {
                    rotateCW();
                    skew       = Skew.BALANCED;
                    right.skew = Skew.BALANCED;
                    return true;
                } else if (left.skew == Skew.BALANCED) {
                    rotateCW();
                    skew       = Skew.RIGHT_HIGH;
                    right.skew = Skew.LEFT_HIGH;
                    return false;
                } else {
                    final Skew s = left.right.skew;
                    left.rotateCCW();
                    rotateCW();
                    switch (s) {
                    case LEFT_HIGH:
                        left.skew  = Skew.BALANCED;
                        right.skew = Skew.RIGHT_HIGH;
                        break;
                    case RIGHT_HIGH:
                        left.skew  = Skew.LEFT_HIGH;
                        right.skew = Skew.BALANCED;
                        break;
                    default:
                        left.skew  = Skew.BALANCED;
                        right.skew = Skew.BALANCED;
                    }
                    skew = Skew.BALANCED;
                    return true;
                }
            default:
                skew = Skew.LEFT_HIGH;
                return false;
            }
        }

        /** Perform a clockwise rotation rooted at the instance.
         * <p>The skew factor are not updated by this method, they
         * <em>must be updated by the caller

*/ private void rotateCW() { final T tmpElt = element; element = left.element; left.element = tmpElt; final Node tmpNode = left; left = tmpNode.left; tmpNode.left = tmpNode.right; tmpNode.right = right; right = tmpNode; if (left != null) { left.parent = this; } if (right.right != null) { right.right.parent = right; } } /** Perform a counter-clockwise rotation rooted at the instance. * <p>The skew factor are not updated by this method, they * <em>must be updated by the caller

*/ private void rotateCCW() { final T tmpElt = element; element = right.element; right.element = tmpElt; final Node tmpNode = right; right = tmpNode.right; tmpNode.right = tmpNode.left; tmpNode.left = left; left = tmpNode; if (right != null) { right.parent = this; } if (left.left != null) { left.left.parent = left; } } } }

Other Java examples (source code examples)

Here is a short list of links related to this Java AVLTree.java source code file:



my book on functional programming

 

new blog posts

 

Copyright 1998-2019 Alvin Alexander, alvinalexander.com
All Rights Reserved.

A percentage of advertising revenue from
pages under the /java/jwarehouse URI on this website is
paid back to open source projects.