[Geom4j-developer] SF.net SVN: geom4j:[19] trunk/src/net/sourceforge/geom4j/util
Status: Pre-Alpha
Brought to you by:
skhenkin
Menu
▾
▴
[Geom4j-developer] SF.net SVN: geom4j:[19] trunk/src/net/sourceforge/geom4j/util
|
From: <skh...@us...> - 2009-12-14 22:57:56
|
Revision: 19
http://geom4j.svn.sourceforge.net/geom4j/?rev=19&view=rev
Author: skhenkin
Date: 2009-12-14 22:57:47 +0000 (Mon, 14 Dec 2009)
Log Message:
-----------
AVL tree implementation completed
Modified Paths:
--------------
trunk/src/net/sourceforge/geom4j/util/AVLTree.java
trunk/src/net/sourceforge/geom4j/util/AVLTreeTest.java
trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java
trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTestBase.java
trunk/src/net/sourceforge/geom4j/util/SearchTree.java
Modified: trunk/src/net/sourceforge/geom4j/util/AVLTree.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/AVLTree.java 2009-12-10 21:16:10 UTC (rev 18)
+++ trunk/src/net/sourceforge/geom4j/util/AVLTree.java 2009-12-14 22:57:47 UTC (rev 19)
@@ -41,6 +41,21 @@
* Contains balance factor for each node.
*/
protected class AVLNode extends Node {
+
+ public int height = 1;
+
+ public AVLNode(E value, AVLNode parent) {
+ super(value, parent);
+ }
+
+ public final int getLeftHeight() {
+ return left == null ? 0 : getLeft().height;
+ }
+
+ public final int getRightHeight() {
+ return right == null ? 0 : getRight().height;
+ }
+
/**
* Each node can have one of the following balance factors
*
@@ -58,12 +73,34 @@
* was lost from the right sub-tree) it will require re-balancing.
* This is achieved by performing a rotation about this node.
*/
- public int balanceFactor = 0;
-
- public AVLNode(E value, Node parent) {
- super(value, parent);
+ public final int getBalanceFactor() {
+ return getRightHeight() - getLeftHeight();
}
-
+
+ @Override
+ public AVLNode getLeft() {
+ return (AVLNode) super.getLeft();
+ }
+
+ @Override
+ public AVLNode getParent() {
+ return (AVLNode) super.getParent();
+ }
+
+ @Override
+ public AVLNode getRight() {
+ return (AVLNode) super.getRight();
+ }
+
+ public boolean isUnbalanced() {
+ int balanceFactor = getBalanceFactor();
+ return balanceFactor < -1 || balanceFactor > 1;
+ }
+
+ /** Recalculate height for the node */
+ public void recalculateHeight() {
+ height = Math.max(getLeftHeight(), getRightHeight()) + 1;
+ }
}
/** Create an empty tree of comparable elements */
@@ -77,15 +114,139 @@
}
@Override
- protected Node insertNode(E e, Node parent) {
- // TODO add code for balancing
- return super.insertNode(e, parent);
+ protected AVLNode insertChildNode(E e, Node parent, int c) {
+ AVLNode insertedNode = (AVLNode) super.insertChildNode(e, parent, c);
+ updateBalance(insertedNode);
+ return insertedNode;
}
@Override
- protected void removeNode(Node node) {
- // TODO add code for balancing
- super.removeNode(node);
+ protected AVLNode createNode(E e, Node parent) {
+ return new AVLNode(e, (AVLNode) parent);
}
+ /** Update balance node and all nodes above it */
+ private void updateBalance(AVLNode node) {
+ while (node != null) {
+ node.recalculateHeight();
+ AVLNode parentNode = node.getParent();
+ if (node.isUnbalanced()) {
+ balanceNode(node);
+ }
+ node = parentNode;
+ }
+ }
+
+ private void balanceNode(AVLNode node) {
+ int balanceFactor = node.getBalanceFactor();
+ assert balanceFactor == -2 || balanceFactor == 2 : balanceFactor;
+ if (balanceFactor < 0) {
+ assert balanceFactor == -2 : balanceFactor;
+ AVLNode leftNode = node.getLeft();
+ if (leftNode.getBalanceFactor() <= 0) { // LL rotation
+ rotateLL(node, leftNode);
+ } else { // LR rotation
+ assert leftNode.getBalanceFactor() == 1 : leftNode.getBalanceFactor();
+ rotateLR(node, leftNode, leftNode.getRight());
+ }
+ } else {
+ assert balanceFactor == 2 : balanceFactor;
+ AVLNode rightNode = node.getRight();
+ if (rightNode.getBalanceFactor() >= 0) { // RR rotation
+ rotateRR(node, rightNode);
+ } else { // RL rotation
+ assert rightNode.getBalanceFactor() == -1 : rightNode.getBalanceFactor();
+ rotateRL(node, rightNode, rightNode.getLeft());
+ }
+ }
+ }
+
+ /** LL-rotation */
+ private void rotateLL(AVLNode node, AVLNode leftNode) {
+ node.left = leftNode.right;
+ if (node.left != null) {
+ node.left.parent = node;
+ }
+ node.recalculateHeight();
+ updateParent(leftNode, node);
+ leftNode.right = node;
+ node.parent = leftNode;
+ leftNode.recalculateHeight();
+ }
+
+ /** RR-rotation */
+ private void rotateRR(AVLNode node, AVLNode rightNode) {
+ node.right = rightNode.left;
+ if (node.right != null) {
+ node.right.parent = node;
+ }
+ node.recalculateHeight();
+ updateParent(rightNode, node);
+ rightNode.left = node;
+ node.parent = rightNode;
+ rightNode.recalculateHeight();
+ }
+
+ /** LR-rotation */
+ private void rotateLR(AVLNode node, AVLNode leftNode, AVLNode rightLeftNode) {
+ node.left = rightLeftNode.right;
+ if (node.left != null) {
+ node.left.parent = node;
+ }
+ node.recalculateHeight();
+ leftNode.right = rightLeftNode.left;
+ if (leftNode.right != null) {
+ leftNode.right.parent = leftNode;
+ }
+ leftNode.recalculateHeight();
+ updateParent(rightLeftNode, node);
+ rightLeftNode.left = leftNode;
+ leftNode.parent = rightLeftNode;
+ rightLeftNode.right = node;
+ node.parent = rightLeftNode;
+ rightLeftNode.recalculateHeight();
+ }
+
+ /** RL-rotation */
+ private void rotateRL(AVLNode node, AVLNode rightNode, AVLNode leftRightNode) {
+ node.right = leftRightNode.left;
+ if (node.right != null) {
+ node.right.parent = node;
+ }
+ node.recalculateHeight();
+ rightNode.left = leftRightNode.right;
+ if (rightNode.left != null) {
+ rightNode.left.parent = rightNode;
+ }
+ rightNode.recalculateHeight();
+ updateParent(leftRightNode, node);
+ leftRightNode.right = rightNode;
+ rightNode.parent = leftRightNode;
+ leftRightNode.left = node;
+ node.parent = leftRightNode;
+ leftRightNode.recalculateHeight();
+ }
+
+ /** Update two-way parent-child reference to a new child */
+ private void updateParent(AVLNode newChild, AVLNode oldChild) {
+ newChild.parent = oldChild.parent;
+ if (oldChild.parent != null) {
+ if (oldChild.parent.left == oldChild) {
+ oldChild.parent.left = newChild;
+ } else {
+ oldChild.parent.right = newChild;
+ }
+ } else {
+ root = newChild;
+ }
+ }
+
+ @Override
+ protected AVLNode removeNode(Node node) {
+ AVLNode removedNode = (AVLNode) super.removeNode(node);
+ updateBalance(removedNode.getParent());
+ return removedNode;
+ }
+
+
}
Modified: trunk/src/net/sourceforge/geom4j/util/AVLTreeTest.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/AVLTreeTest.java 2009-12-10 21:16:10 UTC (rev 18)
+++ trunk/src/net/sourceforge/geom4j/util/AVLTreeTest.java 2009-12-14 22:57:47 UTC (rev 19)
@@ -16,7 +16,10 @@
package net.sourceforge.geom4j.util;
import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+import java.util.Random;
+
import org.junit.Before;
import org.junit.Test;
@@ -31,7 +34,6 @@
return new AVLTree<Integer>();
}
-
@Test
public void testHeight() {
SearchTree<Integer> t = createBinaryTree(
@@ -39,10 +41,70 @@
assertEquals(4, t.height());
t = createBinaryTree(
+ new Integer[] {1, 2, 3});
+ assertEquals(2, t.height());
+
+ t = createBinaryTree(
new Integer[] {7, 11, 17, 23, 15, 35});
assertEquals(3, t.height());
t = createEmptyBinaryTree();
assertEquals(0, t.height());
}
+
+ @Test
+ public void testRandomTreeInBalance() {
+ Integer[] values = createRandomUniqueArray(3000, 10000);
+ AVLTree<Integer> t = (AVLTree<Integer>) createBinaryTree(values);
+ assertTrue(t.isBalanced());
+ }
+
+ @Test
+ public void testRandomTreeHeight() {
+ Integer[] values = createRandomUniqueArray(3000, 10000);
+ SearchTree<Integer> simple = new BinarySearchTree<Integer>();
+ SearchTree<Integer> balanced = new AVLTree<Integer>();
+ populateTree(simple, values);
+ populateTree(balanced, values);
+ assertTrue(balanced.height() < simple.height());
+ }
+
+ @Test
+ public void testRemoval() {
+ SearchTree<Integer> t = createBinaryTree(
+ new Integer[] {8,
+ 4, 12,
+ 2, 6, 10, 14,
+ 1, 3, 5, 7, 9, 11, 13, 15});
+ for (Integer i: new Integer[] {6, 5, 7, 1, 2, 4, 3, 13,
+ 15, 14, 9, 8, 11, 10, 12}) {
+ t.remove(i);
+ assertTrue("Became unbalanced after removing " + i, t.isBalanced());
+ }
+ assertEquals(0, t.size());
+ assertEquals(0, t.height());
+ }
+
+ @Test
+ public void testBalanceInvariantOnRandomOperations() {
+ int maxN = 1000; // values picked from [0..maxN) interval
+ int n = 10000; // number of insertions/deletions
+ int k = 100; // bulk size
+ SearchTree<Integer> t = createEmptyBinaryTree();
+ Random r = new Random();
+ for (int i = 0; i < n/k; i++) {
+ if (r.nextBoolean()) {
+ for (int j = 0; j < k; j++) {
+ t.insert(r.nextInt(maxN));
+ assertTrue(t.isBalanced());
+ }
+ } else {
+ for (int j = 0; j < k; j++) {
+ t.remove(r.nextInt(maxN));
+ assertTrue(t.isBalanced());
+ }
+ }
+ //System.out.println(t.size() + ", " + t.height());
+ }
+ }
}
Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-12-10 21:16:10 UTC (rev 18)
+++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTree.java 2009-12-14 22:57:47 UTC (rev 19)
@@ -51,6 +51,39 @@
this.value = value;
this.parent = parent;
}
+
+ public E getValue() {
+ return value;
+ }
+
+ public void setValue(E value) {
+ this.value = value;
+ }
+
+ public Node getLeft() {
+ return left;
+ }
+
+ public void setLeft(Node left) {
+ this.left = left;
+ }
+
+ public Node getRight() {
+ return right;
+ }
+
+ public void setRight(Node right) {
+ this.right = right;
+ }
+
+ public Node getParent() {
+ return parent;
+ }
+
+ public void setParent(Node parent) {
+ this.parent = parent;
+ }
+
}
/** Root of the tree */
@@ -98,7 +131,7 @@
*/
public boolean insert(E e) {
if (root == null) {
- root = new Node(e, null);
+ root = createNode(e, null);
return true;
}
Node node = root;
@@ -115,15 +148,21 @@
node = node.right;
}
} while (node != null);
+ insertChildNode(e, parent, c);
+ return true;
+ }
+
+ protected Node insertChildNode(E e, Node parent, int c) {
+ Node childNode = createNode(e, parent);
if (c < 0) {
- parent.left = insertNode(e, parent);
+ parent.left = childNode;
} else {
- parent.right = insertNode(e, parent);
+ parent.right = childNode;
}
- return true;
+ return childNode;
}
- protected Node insertNode(E e, Node parent) {
+ protected Node createNode(E e, Node parent) {
return new Node(e, parent);
}
@@ -151,14 +190,10 @@
return false;
}
- protected void removeNode(Node node) {
- if (node.left == null && node.right == null) { // remove node
- updateNodeReferences(node, null);
- } else if (node.left == null){ // replace node with its single right child
- updateNodeReferences(node, node.right);
- } else if (node.right == null){ // replace node with its single left child
- updateNodeReferences(node, node.left);
- } else {
+ /** Return the node which was actually removed */
+ protected Node removeNode(Node node) {
+ Node removed = removeNodeInPlace(node);
+ if (removed == null) {
/* We can either replace the node with the biggest element of its
* left subtree or with the smallest element of its right subtree.
* We randomize the selection of this element to prevent tree
@@ -170,17 +205,33 @@
Node predecessor = previousNode(node);
node.value = predecessor.value;
// remove predecessor (it can have at most one child)
- removeNode(predecessor);
+ removed = removeNodeInPlace(predecessor);
} else {
// replace node value with its in-order successor's value
Node successor = nextNode(node);
node.value = successor.value;
// remove successor (it can have at most one child)
- removeNode(successor);
+ removed = removeNodeInPlace(successor);
}
}
+ return removed;
}
+ /** Tries to remove the node specified if it doesn't have one of the children */
+ protected Node removeNodeInPlace(Node node) {
+ if (node.left != null && node.right != null) {
+ return null;
+ }
+ if (node.left == null && node.right == null) { // remove node
+ updateNodeReferences(node, null);
+ } else if (node.left == null){ // replace node with its single right child
+ updateNodeReferences(node, node.right);
+ } else if (node.right == null){ // replace node with its single left child
+ updateNodeReferences(node, node.left);
+ }
+ return node;
+ }
+
private void updateNodeReferences(Node node, Node replacement) {
if (node.parent == null) { // node == root
root = replacement;
@@ -374,4 +425,22 @@
public boolean isEmpty() {
return root == null;
}
+
+ /**
+ * Check if the tree is balanced,
+ * i.e. balance factor of each node is between -1 and +1.
+ */
+ @Override
+ public boolean isBalanced() {
+ return isNodeBalanced(root);
+ }
+
+ private boolean isNodeBalanced(Node node) {
+ if (node == null) {
+ return true;
+ }
+ return isNodeBalanced(node.left) && isNodeBalanced(node.right)
+ && Math.abs(heightNode(node.left) - heightNode(node.right)) <= 1;
+ }
+
}
Modified: trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTestBase.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTestBase.java 2009-12-10 21:16:10 UTC (rev 18)
+++ trunk/src/net/sourceforge/geom4j/util/BinarySearchTreeTestBase.java 2009-12-14 22:57:47 UTC (rev 19)
@@ -17,7 +17,9 @@
import static org.junit.Assert.*;
+import java.util.ArrayList;
import java.util.Arrays;
+import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
@@ -74,13 +76,33 @@
}
@Test
- public void testRandomTree() {
+ public void testRandomTreeInsertion() {
Integer[] values = createRandomUniqueArray(3000, 10000);
SearchTree<Integer> t = createBinaryTree(values);
Arrays.sort(values);
assertTrue(listsEqual(values, t.toList()));
assertEquals(values.length, t.size());
}
+
+ @Test
+ public void testRandomTreeRemoval() {
+ int maxN = 10000; // values inserted from [0..maxN) interval
+ int n = 3000; // number of insertions
+ int k = 2500; // number of deletions
+ Integer[] ints = createRandomUniqueArray(n, maxN);
+ SearchTree<Integer> t = createBinaryTree(ints);
+ ArrayList<Integer> values = new ArrayList<Integer>(ints.length);
+ Collections.addAll(values, ints);
+ Collections.sort(values);
+ Random r = new Random();
+ for (int i = 0; i < k; i++) {
+ int j = r.nextInt(values.size());
+ t.remove(values.get(j));
+ values.remove(j);
+ }
+ assertTrue(listsEqual(values.toArray(new Integer[0]), t.toList()));
+ assertEquals(values.size(), t.size());
+ }
@Test
public void testSize() {
@@ -131,7 +153,7 @@
return true;
}
- private Integer[] createRandomUniqueArray(int size, int maxValue) {
+ protected Integer[] createRandomUniqueArray(int size, int maxValue) {
Random r = new Random();
Set<Integer> used = new HashSet<Integer>();
Integer[] values = new Integer[size];
@@ -158,7 +180,7 @@
*/
protected abstract SearchTree<Integer> createEmptyBinaryTree();
- private void populateTree(SearchTree<Integer> tree, Integer[] values) {
+ protected void populateTree(SearchTree<Integer> tree, Integer[] values) {
for (int i: values) {
tree.insert(i);
}
Modified: trunk/src/net/sourceforge/geom4j/util/SearchTree.java
===================================================================
--- trunk/src/net/sourceforge/geom4j/util/SearchTree.java 2009-12-10 21:16:10 UTC (rev 18)
+++ trunk/src/net/sourceforge/geom4j/util/SearchTree.java 2009-12-14 22:57:47 UTC (rev 19)
@@ -68,4 +68,7 @@
/** Check if tree contains elements */
boolean isEmpty();
+
+ /** Check if the tree is balanced */
+ boolean isBalanced();
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
