学步园

AA树 - 红黑树的变种

作者：ljs 2011-06-15

AA树是Arne Andersson教授在他的论文"Balanced search trees made simple"中介绍的一个红黑树变种，设计的目的是减少RB树考虑的cases。AA树是一颗红黑树，但是规定红色结点不能作为任何结点的左孩子，也就是说红色结点只能作为右孩子。这样本质上跟2-3树类似（虽然后者属于B树）。另外AA树为实现方便，不再使用红黑两种颜色，而是用level标记结点。level实际上就相当于RB树中的black height，叶子结点的level等于1（反过来，level等于1的不一定是叶子结点，因为等于1的结点可能有一个红色的右孩子），红色结点使用它的父结点的level，黑色结点比它的父结点的level小1。另外，下面两种情况是禁止出现的：

1）连续两个水平方向链（horizontal link），所谓horizontal link是指一个结点跟它的右孩子结点的level相同（左孩子结点永远比它的父结点level小1）。这个规定其实相当于RB树中不能出现两个连续的红色结点。

2）向左的水平方向链（left horizontal link），也就是说一个结点最多只能出现一次向右的水平方向链。这是因为left horizontal link相当于左孩子能为红色结点，这在AA树的定义中是不允许的。

在插入和删除操作中，可能会出现上面两个禁止发生的情况，这时候就需要通过树的旋转操作来纠正。AA树中只有两个基本操作：skew和split。前者用于纠正出现向左的水平方向链，后者用于纠正出现连续两个水平方向链的情况。skew就是一个右旋转，split是一个左旋转，但两者不是互逆的。skew操作之后可能引起1）的发生（当skew之前已经有一个右孩子的level跟当前结点的level相同），这时需要配合使用split操作。split操作的特点是新的子树的根节点level增加1, 从而会在它的父结点中出现1）(当它作为父结点的左孩子)或者在它的父结点中出现2）（当它作为父结点的右孩子而且父结点跟祖父结点的level相同），这时需要通过skew和split操作纠正这两种情况。

由于split引起的新问题发生在parent一级局部结点，而skew引起的新问题只发生在当前局部结点，所以在实现时需要先skew，再split。

在下面的插入操作中使用递归，删除操作没有使用递归。新插入的结点level等于1。

因为AA树也是平衡BST，它的时间复杂度跟RB树一样，即O(logn)，但是旋转次数相对多一些（RB树插入操作最多旋转两次，而且旋转完毕即结束rebalancing；删除操作最多旋转三次，也是旋转完毕即结束rebalancing）。

实现： （性能测试代码和结果在本段代码后面）

import java.util.ArrayList;<br /> import java.util.LinkedList;<br /> import java.util.List;<br /> import java.util.Stack;<br /> /**<br /> *<br /> * @author ljs<br /> * 2011-06-15<br /> * 版权说明：可以复制，但须标明出处<br /> *<br /> */<br /> public class AATree<T extends Comparable<T>> {<br /> private AANode<T> nil;<br /> private AANode<T> root;</p> <p> public static class AANode<E extends Comparable<E>>{<br /> E key;<br /> AANode<E> left;<br /> AANode<E> right;<br /> int level;</p> <p> public AANode(E key,AANode<E> left,AANode<E> right){<br /> this.key = key;<br /> this.left = left;<br /> this.right = right;</p> <p> this.level = 1;<br /> }<br /> public AANode(){ </p> <p> }</p> <p> public String toString(){<br /> return String.valueOf(key + ":" + level);<br /> }<br /> public E getKey(){<br /> return this.key;<br /> }<br /> public E getLeftChild(){<br /> return this.left.key;<br /> }<br /> public E getRightChild(){<br /> return this.right.key;<br /> }<br /> public AANode<E> getLeft() {<br /> return left;<br /> }<br /> public AANode<E> getRight() {<br /> return right;<br /> }<br /> }<br /> public AATree(){<br /> //sentinel node<br /> nil = new AANode<T>();<br /> nil.left = nil;<br /> nil.right = nil;<br /> nil.level = 0;</p> <p> root = nil;<br /> }</p> <p> public AANode<T> getRoot(){<br /> return root;<br /> }</p> <p> private AANode<T> rotateLeftChild(AANode<T> t){<br /> AANode<T> x = t.left;<br /> t.left = x.right;<br /> x.right = t;</p> <p> return x;<br /> }</p> <p> private AANode<T> rotateRightChild(AANode<T> t){<br /> AANode<T> x = t.right;<br /> t.right = x.left;<br /> x.left = t;</p> <p> return x;<br /> }</p> <p> private AANode<T> skew(AANode<T> t){<br /> if(t != nil && t.left.level == t.level)<br /> t=rotateLeftChild(t);<br /> return t;<br /> }</p> <p> private AANode<T> split(AANode<T> t){<br /> if(t != nil && t.right.right.level == t.level){<br /> t = rotateRightChild(t);<br /> t.level++;<br /> }<br /> return t;<br /> }</p> <p> //single insert<br /> public void insert(T x) throws Exception{<br /> root = insert(x,root);<br /> }<br /> //batch insert<br /> public void insert(T[] keys) throws Exception{<br /> for(T x:keys){<br /> insert(x);<br /> }<br /> }</p> <p> //x: the AANode to insert<br /> //t: the root of the subtree<br /> //return: the new root<br /> private AANode<T> insert(T x,AANode<T> t) throws Exception{<br /> if(t==nil){<br /> t = new AANode<T>(x,nil,nil);<br /> }else if(x.compareTo(t.key)<0){<br /> //search the left subtree<br /> AANode<T> left = insert(x,t.left);<br /> t.left = left;<br /> }else if(x.compareTo(t.key)>0){<br /> //search the right subtree<br /> AANode<T> right = insert(x,t.right);<br /> t.right = right;<br /> }else{<br /> //duplicate key found!<br /> throw new Exception("Duplicate key is found!");<br /> }<br /> t = skew(t);<br /> t = split(t);</p> <p> return t;<br /> }<br /> //single delete<br /> public void delete(T x) throws Exception{<br /> delete(x,this.root);<br /> }<br /> //batch delete<br /> public void delete(T[] keys) throws Exception{<br /> for(T x:keys){<br /> delete(x);<br /> }<br /> }<br /> //x: the AANode to delete<br /> //t: the root of the subtree<br /> //return: the new root<br /> private void delete(T x,AANode<T> t) throws Exception{<br /> //delete using BST method<br /> AANode<T> deleteNode = null;</p> <p> Stack<AANode<T>> nodes = new Stack<AANode<T>>();<br /> nodes.push(nil); //sentinel<br /> while(t != nil){<br /> nodes.push(t); </p> <p> if(x.compareTo(t.key)==0){<br /> deleteNode = t;<br /> t = t.left; //find predecessor<br /> }else if(x.compareTo(t.key)<0){<br /> //search the left subtree<br /> t = t.left;<br /> }else {<br /> //search the right subtree<br /> t = t.right;<br /> }<br /> }</p> <p> if(deleteNode == null){<br /> throw new Exception("No key is found!");<br /> }</p> <p> //the top element in the stack is the predecessor of the deleted node or the deleted node itself<br /> t = nodes.pop();<br /> if(deleteNode != t){<br /> //t is the predecessor of the deleteNode<br /> deleteNode.key = t.key; //normal BST operation<br /> }//otherwise: t is a single black leaf node (level=1)</p> <p> //remove the node<br /> if(t.right != nil){<br /> //there is a red right child (which has same level with t)<br /> AANode<T> parent = nodes.pop();<br /> if(parent == nil){<br /> this.root = t.right;<br /> }else{<br /> if(parent.left == t)<br /> parent.left = t.right;<br /> else<br /> parent.right = t.right;<br /> }<br /> //return this.root;<br /> }else{<br /> AANode<T> parent = nodes.pop();<br /> if(parent == nil){<br /> //now return an empty tree<br /> //return nil;<br /> this.root = nil;<br /> }else{<br /> if(parent.left == t){<br /> parent.left = nil;<br /> }else{<br /> parent.right = nil;<br /> }<br /> t=parent;<br /> AANode<T> rootNode = null; </p> <p> //rebalance<br /> boolean deleteFromRight = false;<br /> while(!nodes.isEmpty() && t != nil){<br /> parent = nodes.peek(); </p> <p> boolean doSkewOrSplit = false;<br /> int currLevel = t.level;<br /> if(t.left.level < currLevel - 1){<br /> if(parent != nil && parent.right == t) {<br /> deleteFromRight = true;<br /> } </p> <p> t.level--;<br /> if(t.right.level == currLevel) {<br /> t.right.level--;<br /> }<br /> doSkewOrSplit = true;<br /> }else if(t.right.level<currLevel - 1<br /> || (deleteFromRight && currLevel-1==t.right.level)){<br /> if(parent != nil && parent.right == t) {<br /> deleteFromRight = true;<br /> } </p> <p> t.level--;</p> <p> doSkewOrSplit = true;<br /> }<br /> if(doSkewOrSplit){<br /> t = skew(t);<br /> t.right = skew(t.right);<br /> t.right.right = skew(t.right.right);</p> <p> t = split(t);<br /> t.right = split(t.right);</p> <p> //set the parent<br /> if(parent != nil) {<br /> if(deleteFromRight)<br /> parent.right = t;<br /> else<br /> parent.left = t;<br /> }<br /> }else{ //no rotation<br /> rootNode = this.root;<br /> break;<br /> }<br /> rootNode = t;<br /> t = nodes.pop();<br /> }<br /> //return rootNode;<br /> this.root = rootNode;<br /> }<br /> }<br /> }<br /> public static void testCases() throws Exception{</p> <p> AATree<Integer> aaT = new AATree<Integer>();<br /> try{<br /> aaT.delete(0); //throw exception<br /> System.out.println("***Exception Test WRONG");<br /> }catch(Exception e){<br /> if(e.getMessage().startsWith("No key is found!")){<br /> System.out.println("Exception Test OK");<br /> }else{<br /> System.out.println("***Exception Test WRONG");<br /> }<br /> }</p> <p> System.out.println("*************************");<br /> aaT = new AATree<Integer>();<br /> Integer[] A = new Integer[]{0,1,2,3,4,5,6};<br /> aaT.insert(A);<br /> System.out.println("After Insert:");<br /> AATree.print(aaT);</p> <p> System.out.println("*************************");<br /> aaT = new AATree<Integer>();<br /> A = new Integer[]{6,5,4,3,2};<br /> aaT.insert(A);<br /> System.out.println("After Insert:");<br /> AATree.print(aaT);</p> <p> System.out.println("*************************");<br /> aaT = new AATree<Integer>();<br /> aaT.insert(1);<br /> System.out.println("Before Delete:");<br /> AATree.print(aaT);<br /> aaT.delete(1); //become an empty tree<br /> System.out.println("After Delete 1:");<br /> AATree.print(aaT);<br /> if(aaT.isEmptyTree()){<br /> System.out.println("Empty Tree Test OK");<br /> }else{<br /> System.out.println("***Empty Tree Test WRONG");<br /> }</p> <p> System.out.println("*************************");<br /> aaT = new AATree<Integer>();<br /> aaT.insert(1);<br /> aaT.insert(2);<br /> System.out.println("Before Delete:");<br /> AATree.print(aaT);<br /> aaT.delete(2); //delete right node (red)<br /> System.out.println("After Delete 2:");<br /> AATree.print(aaT);<br /> if(aaT.getRoot().getKey() == 1){<br /> System.out.println("Delete Red Leaf OK");<br /> }else{<br /> System.out.println("***Delete Red Leaf WRONG");<br /> }</p> <p> System.out.println("*************************");<br /> aaT = new AATree<Integer>();<br /> aaT.insert(1);<br /> aaT.insert(2);<br /> System.out.println("Before Delete:");<br /> AATree.print(aaT);<br /> aaT.delete(1); //delete 1<br /> System.out.println("After Delete 1:");<br /> AATree.print(aaT);<br /> if(aaT.getRoot().getKey() == 2){<br /> System.out.println("Delete Root OK");<br /> }else{<br /> System.out.println("***Delete Root WRONG");<br /> }</p> <p> System.out.println("*************************");<br /> aaT = new AATree<Integer>();<br /> A = new Integer[]{0,1,2,3,4,6,7};<br /> aaT.insert(A);<br /> aaT.insert(5);<br /> System.out.println("Before Delete:");<br /> AATree.print(aaT);<br /> //tree:<br /> /*<br /> 3,3<br /> / /<br /> 1,2 6,2<br /> / / / /<br /> 0,1 2,1 4,1 7,1<br /> /<br /> 5,1<br /> */<br /> aaT.delete(5);<br /> System.out.println("After Delete 5:");<br /> AATree.print(aaT);<br /> AANode<Integer> node = aaT.findNode(4);<br /> if(aaT.isLeaf(node)){<br /> System.out.println("Leaf Test OK");<br /> }else{<br /> System.out.println("***Leaf Test WRONG");<br /> }</p> <p> System.out.println("*************************");<br /> aaT = new AATree<Integer>();<br /> A = new Integer[]{0,1,2,3,4,6,7};<br /> aaT.insert(A);<br /> aaT.insert(5);<br /> System.out.println("Before Delete:");<br /> AATree.print(aaT);<br /> //tree:<br /> /*<br /> 3,3<br /> / /<br /> 1,2 6,2<br /> / / / /<br /> 0,1 2,1 4,1 7,1<br /> /<br /> 5,1<br /> */<br /> aaT.delete(3);<br /> System.out.println("After Delete 3:");<br /> AATree.print(aaT);<br /> node = aaT.findNode(0);<br /> if(node.getRightChild()==1){<br /> System.out.println("Right Child OK");<br /> }else{<br /> System.out.println("***Right Child WRONG");<br /> }<br /> if(aaT.getRoot().getKey()==2){<br /> System.out.println("Root Key OK");<br /> }else{<br /> System.out.println("***Root Key WRONG");<br /> }</p> <p> System.out.println("*************************");<br /> aaT = new AATree<Integer>();<br /> A = new Integer[]{0,1,2,3,4,6,7};<br /> aaT.insert(A);<br /> aaT.insert(5);<br /> System.out.println("Before Delete:");<br /> AATree.print(aaT);<br /> //tree:<br /> /*<br /> 3,3<br /> / /<br /> 1,2 6,2<br /> / / / /<br /> 0,1 2,1 4,1 7,1<br /> /<br /> 5,1<br /> */<br /> aaT.delete(4);<br /> System.out.println("After Delete 4:");<br /> AATree.print(aaT);<br /> if(aaT.findNode(5).level==1){<br /> System.out.println("Leaf Level OK");<br /> }else{<br /> System.out.println("***Leaf Level WRONG");<br /> }<br /> if(aaT.findNode(6).level==2){<br /> System.out.println("Subtree's Root Level OK");<br /> }else{<br /> System.out.println("***Subtree's Root Level WRONG");<br /> }</p> <p> System.out.println("*************************");<br /> aaT = new AATree<Integer>();<br /> A = new Integer[]{10,85,15,70,20,60,30,50,65,80,90,40,5,55,35};<br /> aaT.insert(A);<br /> System.out.println("Before Insert 45:");<br /> AATree.print(aaT);<br /> aaT.insert(45);<br /> System.out.println("After Insert 45:");<br /> AATree.print(aaT);<br /> if(aaT.getRoot().key==50 && aaT.getRoot().level == 4){<br /> System.out.println("Root(50) Level OK");<br /> }else{<br /> System.out.println("***Root Level WRONG");<br /> }</p> <p> System.out.println("*************************");<br /> aaT = new AATree<Integer>();<br /> A = new Integer[]{0,1,2,3,4,5,6};<br /> aaT.insert(A);<br /> System.out.println("Before Delete:");<br /> AATree.print(aaT);<br /> /*<br /> 3,3<br /> / /<br /> 1,2 5,2<br /> / / / /<br /> 0,1 2,1 4,1 6,1<br /> */<br /> Integer[] DEL = new Integer[]{0,3};<br /> aaT.delete(DEL); //until now nothing special<br /> System.out.println("After Delete 0 and 3:");<br /> AATree.print(aaT);<br /> aaT.delete(1);<br /> System.out.println("After Delete 1:");<br /> AATree.print(aaT);<br /> if(aaT.getRoot().key==4 && aaT.getRoot().level == 2){<br /> System.out.println("Root(4) Level OK");<br /> }else{<br /> System.out.println("***Root Level WRONG");<br /> }</p> <p> System.out.println("*************************");<br /> //make a tree<br /> aaT = new AATree<Integer>();<br /> buildTestTree1(aaT);<br /> System.out.println("Before Delete:");<br /> AATree.print(aaT);<br /> //test the tree<br /> aaT.delete(1);<br /> System.out.println("After Delete 1:");<br /> AATree.print(aaT);<br /> if(aaT.getRoot().key==3 && aaT.getRoot().level == 2){<br /> System.out.println("Root(3) Level OK");<br /> }else{<br /> System.out.println("***Root Level WRONG");<br /> }</p> <p> System.out.println("*************************");<br /> aaT = new AATree<Integer>();<br /> buildTestTree1(aaT);<br /> System.out.println("Before Delete:");<br /> AATree.print(aaT);<br /> //test the tree<br /> aaT.delete(7);<br /> System.out.println("After Delete 7:");<br /> AATree.print(aaT);<br /> aaT.delete(6);<br /> System.out.println("After Delete 6:");<br /> AATree.print(aaT);<br /> if(aaT.getRoot().key==2 && aaT.getRoot().level == 2){<br /> System.out.println("Root(2) Level OK");<br /> }else{<br /> System.out.println("***Root Level WRONG");<br /> }</p> <p> System.out.println("*************************");<br /> aaT = new AATree<Integer>();<br /> buildTestTree2(aaT);<br /> System.out.println("Before Delete:");<br /> AATree.print(aaT);<br /> //test the tree<br /> aaT.delete(7);<br /> System.out.println("After Delete 7:");<br /> AATree.print(aaT);</p> <p> System.out.println("*************************");<br /> aaT = new AATree<Integer>();<br /> buildTestTree3(aaT);<br /> System.out.println("Before Delete:");<br /> AATree.print(aaT);<br /> //test the tree<br /> aaT.delete(7);<br /> System.out.println("After Delete 7:");<br /> AATree.print(aaT);<br /> }</p> <p> private static void buildTestTree1(AATree<Integer> aaT){</p> <p> AANode<Integer> root = aaT.makeNode(2);<br /> root.level = 2;<br /> AANode<Integer> node1 = aaT.makeNode(1);<br /> node1.level = 1;<br /> AANode<Integer> node5 = aaT.makeNode(5);<br /> node5.level = 2;<br /> AATree.attachAsLeftChild(root, node1);<br /> AATree.attachAsRightChild(root, node5);</p> <p> AANode<Integer> node3 = aaT.makeNode(3);<br /> node3.level = 1;<br /> AANode<Integer> node6 = aaT.makeNode(6);<br /> node6.level = 1;<br /> AANode<Integer> node4 = aaT.makeNode(4);<br /> node4.level = 1;<br /> AANode<Integer> node7 = aaT.makeNode(7);<br /> node7.level = 1;<br /> AATree.attachAsLeftChild(node5, node3);<br /> AATree.attachAsRightChild(node5, node6);</p> <p> AATree.attachAsRightChild(node3, node4);<br /> AATree.attachAsRightChild(node6, node7);<br /> aaT.setRoot(root);<br /> }</p> <p> private static void buildTestTree2(AATree<Integer> aaT){</p> <p> AANode<Integer> root = aaT.makeNode(3);<br /> root.level = 2;<br /> AANode<Integer> node1 = aaT.makeNode(1);<br /> node1.level = 1;<br /> AANode<Integer> node6 = aaT.makeNode(6);<br /> node6.level = 2;<br /> AATree.attachAsLeftChild(root, node1);<br /> AATree.attachAsRightChild(root, node6);</p> <p> AANode<Integer> node2 = aaT.makeNode(2);<br /> node2.level = 1;<br /> AANode<Integer> node4 = aaT.makeNode(4);<br /> node4.level = 1;<br /> AANode<Integer> node7 = aaT.makeNode(7);<br /> node7.level = 1;<br /> AANode<Integer> node5 = aaT.makeNode(5);<br /> node5.level = 1;<br /> AATree.attachAsLeftChild(node6, node4);<br /> AATree.attachAsRightChild(node6, node7);</p> <p> AATree.attachAsRightChild(node4, node5);<br /> AATree.attachAsRightChild(node1, node2);<br /> aaT.setRoot(root);<br /> }</p> <p> private static void buildTestTree3(AATree<Integer> aaT){</p> <p> AANode<Integer> root = aaT.makeNode(3);<br /> root.level = 2;<br /> AANode<Integer> node1 = aaT.makeNode(1);<br /> node1.level = 1;<br /> AANode<Integer> node6 = aaT.makeNode(6);<br /> node6.level = 2;<br /> AATree.attachAsLeftChild(root, node1);<br /> AATree.attachAsRightChild(root, node6);</p> <p> AANode<Integer> node2 = aaT.makeNode(2);<br /> node2.level = 1;<br /> AANode<Integer> node7 = aaT.makeNode(7);<br /> node7.level = 1;<br /> AANode<Integer> node5 = aaT.makeNode(5);<br /> node5.level = 1;<br /> AATree.attachAsLeftChild(node6, node5);<br /> AATree.attachAsRightChild(node6, node7);</p> <p> AATree.attachAsRightChild(node1, node2);<br /> aaT.setRoot(root);<br /> }<br /> //utility method for test purpose<br /> @SuppressWarnings("rawtypes")<br /> public static void print(AATree aaTree){<br /> AANode root = aaTree.getRoot();<br /> System.out.format("%nin-order BST:%n");<br /> NODES=0;<br /> AATree.recursiveInOrderTraverse(root);</p> <p> System.out.format("%n%n%nThe tree is:");<br /> AATree.displayBinaryTree(root,NODES);</p> <p> }</p> <p> private static int NODES=0;<br /> //utility method for test purpose<br /> @SuppressWarnings("rawtypes")<br /> private static void recursiveInOrderTraverse(AANode root){<br /> if(root.key == null)return;</p> <p> recursiveInOrderTraverse(root.left);<br /> System.out.format(" (%d,%d)", root.key,root.level);<br /> NODES++;<br /> recursiveInOrderTraverse(root.right);<br /> }<br /> //utility method for test purpose<br /> //n: the nodes number of the tree<br /> @SuppressWarnings("rawtypes")<br /> private static void displayBinaryTree(AANode root,int n){<br /> if(root.key == null) return;</p> <p> LinkedList<AANode> queue = new LinkedList<AANode>();</p> <p> //all AANodes in each level<br /> List<List<AANode>> nodesList = new ArrayList<List<AANode>>();</p> <p> //the positions in a displayable tree for each level's nodes<br /> List<List<Integer>> nextPosList = new ArrayList<List<Integer>>();</p> <p> queue.add(root);<br /> //int level=0;<br /> int levelNodes = 1; </p> <p> int nextLevelNodes = 0;<br /> List<AANode> levelNodesList = new ArrayList<AANode>();<br /> List<Integer> nextLevelNodesPosList = new ArrayList<Integer>();</p> <p> int pos = 0; //the position of the current node<br /> List<Integer> levelNodesPosList = new ArrayList<Integer>();<br /> levelNodesPosList.add(0); //root position<br /> nextPosList.add(levelNodesPosList);<br /> int levelNodesTotal = 1;<br /> while(!queue.isEmpty()) {<br /> AANode node = queue.remove();</p> <p> if(levelNodes==0){<br /> nodesList.add(levelNodesList);<br /> nextPosList.add(nextLevelNodesPosList);<br /> levelNodesPosList = nextLevelNodesPosList;</p> <p> levelNodesList = new ArrayList<AANode>();<br /> nextLevelNodesPosList = new ArrayList<Integer>();</p> <p> //level++;<br /> levelNodes = nextLevelNodes;<br /> levelNodesTotal = nextLevelNodes;</p> <p> nextLevelNodes = 0;<br /> }<br /> levelNodesList.add(node); </p> <p> pos = levelNodesPosList.get(levelNodesTotal - levelNodes);<br /> if(node.left.key != null){<br /> queue.add(node.left);<br /> nextLevelNodes++;<br /> nextLevelNodesPosList.add(2*pos);<br /> }</p> <p> if(node.right.key != null) {<br /> queue.add(node.right);<br /> nextLevelNodes++; </p> <p> nextLevelNodesPosList.add(2*pos+1);<br /> }</p> <p> levelNodes--;<br /> }<br /> //save the last level's nodes list<br /> nodesList.add(levelNodesList);</p> <p> int maxLevel = nodesList.size()-1; //==level</p> <p> //use both nodesList and nextPosList to set the positions for each node</p> <p> //Note: expected max columns: 2^(level+1) - 1<br /> int cols = 1;<br /> for(int i=0;i<=maxLevel;i++){<br /> cols <<= 1;<br /> }<br /> cols--;<br /> AANode[][] tree = new AANode[maxLevel+1][cols];</p> <p> //load the tree into an array for later display<br /> for(int currLevel=0;currLevel<=maxLevel;currLevel++){<br /> levelNodesList = nodesList.get(currLevel);<br /> levelNodesPosList = nextPosList.get(currLevel);<br /> //Note: the column for this level's j-th element: 2^(maxLevel-level)*(2*j+1) - 1<br /> int tmp = maxLevel-currLevel;<br /> int coeff = 1;<br /> for(int i=0;i<tmp;i++){<br /> coeff <<= 1;<br /> }<br /> for(int k=0;k<levelNodesList.size();k++){<br /> int j = levelNodesPosList.get(k);<br /> int col = coeff*(2*j + 1) - 1;<br /> tree[currLevel][col] = levelNodesList.get(k);<br /> }<br /> }</p> <p> //display the binary search tree<br /> System.out.format("%n");<br /> for(int i=0;i<=maxLevel;i++){<br /> for(int j=0;j<cols;j++){<br /> AANode node = tree[i][j];<br /> if(node== null || node.key == null)<br /> System.out.format(" ");<br /> else<br /> System.out.format("%2d,%d",node.key,node.level);<br /> }<br /> System.out.format("%n");<br /> }<br /> }</p> <p> public void setRoot(AANode<T> root) {<br /> this.root = root;<br /> }<br /> public boolean isEmptyTree(){<br /> return this.root == nil;<br /> }</p> <p> public AANode<T> makeNode(T key){<br /> return new AANode<T>(key,nil,nil);<br /> }</p> <p> public static <T extends Comparable<T>> void attachAsLeftChild(AANode<T> parent,AANode<T> node){<br /> parent.left = node;<br /> }<br /> public static <T extends Comparable<T>> void attachAsRightChild(AANode<T> parent,AANode<T> node){<br /> parent.right = node;<br /> }</p> <p> public boolean isLeaf(AANode<T> node){<br /> return node.getLeft()==nil && node.getRight() == nil;<br /> }</p> <p> public AANode<T> findNode(T key) throws Exception{<br /> AANode<T> node = this.root;<br /> while(node != nil){<br /> if(key.compareTo(node.key)==0){<br /> break;<br /> }else if(key.compareTo(node.key)<0){<br /> node = node.left;<br /> }else if(key.compareTo(node.key)>0){<br /> node = node.right;<br /> }<br /> }<br /> if(node == nil){<br /> throw new Exception("No such key is found!");<br /> }<br /> return node;<br /> }</p> <p> public static void main(String[] args) throws Exception {<br /> testCases();<br /> }<br /> }<br />

性能测试：从磁盘读入一百万条数据到内存，然后依次查找、插入和删除各50万次。

先是性能测试代码：

其中prepareTestData(dataFilename,N)语句只需执行一次，用于写入一百万个不重复的整数到磁盘文件中：

public static void main(String[] args) throws Exception {<br /> String dataFilename = "C://tmp//aatree.txt";<br /> int N = 1000000; //the number of keys </p> <p> //******Prepare Data(only execute once for multiple tests)******<br /> prepareTestData(dataFilename,N);</p> <p> //******Begin Test******<br /> AATree<Integer> aaT = new AATree<Integer>();<br /> DataInputStream in= new DataInputStream(new FileInputStream(dataFilename));<br /> //long startTime = System.currentTimeMillis();<br /> int key = -1;<br /> int keyCount = 0;<br /> while(true){<br /> try{<br /> key = in.readInt();<br /> aaT.insert(key);<br /> keyCount++;<br /> }catch(EOFException e){<br /> break;<br /> }<br /> }<br /> in.close();<br /> //long endTime = System.currentTimeMillis();<br /> //System.out.format("file io and insert time spent: %d(ms)%n",(endTime-startTime));<br /> System.out.format("Total number of keys to begin with: %d%n",keyCount);</p> <p> long t1=0,t2=0;</p> <p> //do some operations in memory<br /> long startTime = System.currentTimeMillis();<br /> t1 = startTime;<br /> int totalSuccess = 0;<br /> int totalFailed = 0; </p> <p> System.out.format("%n***Search Operations***%n");<br /> //try to find a number of keys<br /> int rangeStart = 1100000;<br /> int rangeEnd = 1600000;<br /> for(int i=rangeStart;i<rangeEnd;i++){<br /> try{<br /> AANode<Integer> node = aaT.findNode(i);<br /> //System.out.println("found key: " + node.key);<br /> totalSuccess++;<br /> }catch(Exception e){<br /> totalFailed++;<br /> //not found<br /> //System.out.println(e.getMessage());<br /> }<br /> }<br /> t2 = System.currentTimeMillis();<br /> System.out.format("Time spent: %d(ms)%n",(t2-t1));<br /> System.out.format("The number of keys we try to find: %d%n",rangeEnd-rangeStart);<br /> System.out.format("The number of keys found: %d%n",totalSuccess);<br /> System.out.format("The number of keys not found: %d%n",totalFailed);</p> <p> //insert a number of new keys<br /> System.out.format("%n***Insertion Operations***%n");<br /> t1 = System.currentTimeMillis();<br /> totalSuccess = 0;<br /> totalFailed = 0;<br /> rangeStart = 1400000;<br /> rangeEnd = 1900000;<br /> for(int i=rangeStart;i<rangeEnd;i++){<br /> try{<br /> aaT.insert(i);<br /> //System.out.println("inserted key: " + i);<br /> totalSuccess++;<br /> }catch(Exception e){<br /> totalFailed++;<br /> //duplicate insert<br /> //System.out.println(e.getMessage());<br /> }<br /> }<br /> t2 = System.currentTimeMillis();<br /> System.out.format("Time spent: %d(ms)%n",(t2-t1));<br /> System.out.format("The number of keys we try to insert: %d%n",rangeEnd - rangeStart);<br /> System.out.format("The number of keys inserted: %d%n",totalSuccess);<br /> System.out.format("The number of keys with insertion failed due to duplicate: %d%n",totalFailed);</p> <p> //delete a number of new keys<br /> System.out.format("%n***Deletion Operations***%n");<br /> t1 = System.currentTimeMillis();<br /> totalSuccess = 0;<br /> totalFailed = 0;<br /> rangeStart = 400000;<br /> rangeEnd = 900000;<br /> for(int i=rangeStart;i<rangeEnd;i++){<br /> try{<br /> aaT.delete(i);<br /> //System.out.println("deleted key: " + i);<br /> totalSuccess++;<br /> }catch(Exception e){<br /> totalFailed++;<br /> //not found<br /> //System.out.println(e.getMessage());<br /> }<br /> }<br /> t2 = System.currentTimeMillis();<br /> System.out.format("Time spent: %d(ms)%n",(t2-t1));<br /> System.out.format("The number of keys we try to delete: %d%n",rangeEnd-rangeStart);<br /> System.out.format("The number of keys deleted: %d%n",totalSuccess);<br /> System.out.format("The number of keys with deletion failed due to non-existence: %d%n",totalFailed);</p> <p> long endTime = t2;<br /> System.out.format("%nThe above operations(search,insert,delete) total spent: %d(ms)%n",(endTime-startTime));</p> <p> }</p> <p> //write non-duplicate keys into external file for later test<br /> private static void prepareTestData(String dataFilename,int totalKeys) throws IOException{<br /> AATree<Integer> aaT = new AATree<Integer>();</p> <p> //multiply by a larger factor(here it is 10) to eliminate the duplicate insert<br /> int KEYRANGE = totalKeys*10;<br /> int i=0;<br /> while(i<totalKeys){<br /> int rand = (int)(Math.random()*KEYRANGE);<br /> try{<br /> aaT.insert(rand);<br /> i++;<br /> //System.out.format("insert: %d%n",rand);<br /> }catch(Exception e){<br /> //for duplicate insert: retry<br /> //System.out.println(e.getMessage());<br /> }<br /> }<br /> DataOutputStream out= new DataOutputStream(new FileOutputStream(dataFilename));<br /> persistKeys(aaT.getRoot(),out);<br /> out.close();<br /> }</p> <p> private static void persistKeys(AANode<Integer> root,DataOutputStream out) throws IOException{<br /> if(root.key == null)return;</p> <p> persistKeys(root.left,out);<br /> out.writeInt(root.key);<br /> persistKeys(root.right,out);<br /> }

性能测试报告(Intel Core2 T5500 1.66GHz, 2GB RAM)：

Total number of keys to begin with: 1000000

***Search Operations***
Time spent: 2172(ms)
The number of keys we try to find: 500000
The number of keys found: 49955
The number of keys not found: 450045

***Insertion Operations***
Time spent: 1984(ms)
The number of keys we try to insert: 500000
The number of keys inserted: 450090
The number of keys with insertion failed due to duplicate: 49910

***Deletion Operations***
Time spent: 3172(ms)
The number of keys we try to delete: 500000
The number of keys deleted: 7
The number of keys with deletion failed due to non-existence: 499993

The above operations(search,insert,delete) total spent: 7328(ms)