-
Notifications
You must be signed in to change notification settings - Fork 56
Class AVLTree
Ori Roth edited this page Apr 2, 2017
·
3 revisions
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>.
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>.
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>.
// 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();
}
}
}| Metric | Value | Acronym | Explanation |
|---|---|---|---|
| LOC | 632 | Lines Of Code | Total number of lines in the code |
| SCC | 166 | SemiColons Count | Total number of semicolon tokens found in the code. |
| NOT | 2412 | Number Of Tokens | Comments, whitespace and text which cannot be made into a token not included. |
| VCC | 14220 | Visible Characters Count | The total number of non-white (i.e., not space, tab, newline, carriage return, form feed) characters. |
| CCC | 7888 | Code Characters Count | Total number of non-white characters in tokens. White space characters in string and character literals are not counted. |
| UIC | 82 | Unique Identifiers Count | The number of different identifiers found in the code |
| WHC | 8 | Weighted Horizontal Complexity | A heuritistic on horizontal complexity |
| Statistic | Value |
|---|---|
| Average token length | 3.3 |
| Tokens/line | 3.8 |
| Visible characters/line | 23 |
| Code characters/line | 12 |
| Semicolons/tokens | 6% |
| Comment text percentage | 44% |
| Token Kind | Occurrences |
|---|---|
| KEYWORD | 330 |
| OPERATOR | 329 |
| LITERAL | 20 |
| ID | 886 |
| PUNCTUATION | 847 |
| COMMENT | 49 |
| OTHER | 1151 |