最近小看了下hsqldb的源码，发现它的索引时用AVLTree实现的，为了更深刻理解AVLTree,自己模仿hsqldb的AVLTree写了一个小平衡二叉树。目前不支持并发，好像java的map 里面有个树形结构实现。
public class AVLNode {
public AVLNode left=null;
public AVLNode right=null;
public AVLNode parent=null;
public Comparable key;
public Object value;
public int balance=0;
public AVLNode(Comparable key,Object value)
{
this.key=key;
this.value=value;
}
public boolean isFromLeft()
{
return this.parent.left==this;
}
public void childAs(boolean isLeft,AVLNode newParent)
{
this.parent=newParent;
if(isLeft)
newParent.left=this;
else
newParent.right=this;
}
public AVLNode getSmallest()
{
AVLNode node=this;
AVLNode tmpNode=this;
while(tmpNode!=null)
{
node=tmpNode;
tmpNode=tmpNode.left;
}
return node;
}
public AVLNode getLargest()
{
AVLNode node=this;
AVLNode tmpNode=this;
while(tmpNode!=null)
{
node=tmpNode;
tmpNode=tmpNode.right;
}
return node;
}
}
import java.util.Iterator;
public class AVLTree {
private AVLNode root=null;
public AVLNode getRoot() {
return root;
}
public void insert(AVLNode toInsert)
{
//whether to check this node's child
if(toInsert.left!=null||toInsert.right!=null)
;
if(root==null)
root=toInsert;
//locate this node's position
AVLNode tmpNode=root;
AVLNode insertParent=null;<script type="text/javascript"><!--mce:0--></script>
while(tmpNode!=null)
{
int compare=toInsert.key.compareTo(tmpNode.key);
if(compare==0)
return;
else if(compare==-1)
{
insertParent=tmpNode;
tmpNode=tmpNode.left;
}
else
{
insertParent=tmpNode;
tmpNode=tmpNode.right;
}
}
//get the left or right
boolean isLeft=toInsert.key.compareTo(insertParent.key)==-1?true:false;
toInsert.childAs(isLeft, insertParent);
AVLNode toBalance=traceBackRefreshBalanceInsert(toInsert);
if(toBalance!=null)
balance(toBalance);
}
//trace back to refresh the balances and find where need to rotate
private AVLNode traceBackRefreshBalanceInsert(AVLNode traceNode)
{
int childFlag;//from left or right -1 left 1 right
while(traceNode!=root)
{
childFlag=traceNode.isFromLeft()?-1:1;
traceNode.parent.balance+=childFlag;//refresh
switch(Math.abs(traceNode.parent.balance))
{
case 0://this subTree is balanced
return null;
case 1://continue refresh
break;
case 2://subTree traceNode.parent.balance is not balance!
return traceNode.parent;
}
traceNode=traceNode.parent;
}
return null;
}
private AVLNode traceBackRefreshBalanceDelete(AVLNode traceNode)
{
AVLNode tmpNode=traceNode;
int isFromLeft;
while(tmpNode!=root)
{
isFromLeft=tmpNode.isFromLeft()?-1:1;
tmpNode.parent.balance-=isFromLeft;
switch(Math.abs(tmpNode.parent.balance))
{
case 0:
break;
case 1:
return null;
case 2:
return tmpNode.parent;
}
}
return null;
}
//balance the tree
private void balance(AVLNode toBalance)
{
if(toBalance.balance<0)
{
if(toBalance.left.balance<=0)//LL right rotate
{
AVLNode toBalanceLeftChild=toBalance.left;
AVLNode toBalanceNewLeftChild=toBalance.left.right;
toBalance.balance=0;
toBalance.left.balance=0;
if(toBalance.parent==null)
{
root=toBalanceLeftChild;
toBalanceLeftChild.parent=null;
}
else
toBalanceLeftChild.childAs(toBalance.isFromLeft(), toBalance.parent);
toBalance.childAs(false, toBalanceLeftChild);
if(toBalanceNewLeftChild!=null)
toBalanceNewLeftChild.childAs(true, toBalance);
}
else//LR left-right rotate
{
AVLNode newLeftChild=toBalance.left;
AVLNode newRoot=toBalance.left.right;
AVLNode newLeftChildRight=toBalance.left.right.left;
AVLNode newRightChildLeft=toBalance.left.right.right;
newLeftChild.balance=0;
newRoot.balance=0;
if(toBalance.parent==null)
{
root=newRoot;
newRoot.parent=null;
}
else
newRoot.childAs(toBalance.isFromLeft(), toBalance.parent);
newLeftChild.childAs(true, newRoot);
toBalance.childAs(false, newRoot);
if(newLeftChildRight!=null)
newLeftChildRight.childAs(false, newLeftChild);
if(newRightChildLeft!=null)
newRightChildLeft.childAs(true, toBalance);
}
}
else
{
if(toBalance.right.balance>=0)//RR left rotate
{
AVLNode toBalanceRightChild=toBalance.right;
AVLNode toBalanceNewRightChild=toBalance.right.left;
toBalance.balance=0;
toBalance.right.balance=0;
if(toBalance.parent==null)
{
toBalanceRightChild.parent=null;
root=toBalanceRightChild;
}
else
toBalanceRightChild.childAs(toBalance.isFromLeft(), toBalance.parent);
toBalance.childAs(true, toBalanceRightChild);
if(toBalanceNewRightChild!=null)
toBalanceNewRightChild.childAs(false, toBalance);
}
else//RL right-left rotate
{
AVLNode newRightChild=toBalance.right;
AVLNode newRoot=toBalance.right.left;
AVLNode newLeftChildRight=toBalance.right.left.left;
AVLNode newRightChildLeft=toBalance.right.left.right;
newRightChild.balance=0;
newRoot.balance=0;
if(toBalance.parent==null)
{
root=newRoot;
newRoot.parent=null;
}
else
newRoot.childAs(toBalance.isFromLeft(), toBalance.parent);
newRightChild.childAs(false, newRoot);
toBalance.childAs(true, newRoot);
if(newLeftChildRight!=null)
newLeftChildRight.childAs(false, toBalance);
if(newRightChildLeft!=null)
newRightChildLeft.childAs(true, newRightChild);
}
}
}
public AVLNode delete(Comparable key)
{
AVLNode toDelete=getAVLNodeByKey(key);
if(toDelete==null)
return null;
if(toDelete==root&&toDelete.left==null&&toDelete.right==null)
{
root=null;
return root;
}
//begin replace to delete node with a node
//this node is the deeper subTree's smallest node of the right subTree
//or the largest node of the left subTree
AVLNode toReplace;
AVLNode toBalance;
int compare=toDelete.balance;
if(compare<=0)
{
toReplace=toDelete.left.getLargest();
toBalance=traceBackRefreshBalanceDelete(toReplace);
if(toReplace.left!=null)
toReplace.left.childAs(false, toReplace.parent);
}
else
{
toReplace=toDelete.right.getSmallest();
toBalance=traceBackRefreshBalanceDelete(toReplace);
if(toReplace.right!=null)
toReplace.right.childAs(true, toReplace.parent);
}
if(toDelete.left!=null)
toDelete.left.childAs(true, toReplace);
if(toDelete.right!=null)
toDelete.right.childAs(false, toReplace);
toReplace.balance=toDelete.balance;
//set new root if toDelete is the root
if(toDelete.parent==null)
{
toReplace.parent=null;
root=toReplace;
}
else
{
toReplace.childAs(toDelete.isFromLeft(), toDelete.parent);
}
//balance
if(toBalance!=null)
balance(toBalance);
//refresh balance again
AVLNode tmpNode=toBalance;
while(tmpNode.parent!=null)
{
int isFromLeft;
isFromLeft=tmpNode.isFromLeft()?-1:1;
tmpNode.parent.balance-=isFromLeft;
tmpNode=tmpNode.parent;
}
//clear this node
toDelete.left=toDelete.right=toDelete.parent=null;
return toDelete;
}
public AVLNode getAVLNodeByKey(Comparable key)
{
AVLNode tmpNode=root;
while(tmpNode!=null)
{
switch(key.compareTo(tmpNode.key))
{
case 0:
return tmpNode;
case -1:
tmpNode=tmpNode.left;
break;
case 1:
tmpNode=tmpNode.right;
break;
}
}
return null;
}
}
import junit.framework.TestCase;
public class TestAVLTree extends TestCase{
AVLTree tree=new AVLTree();
public void testInsertRR()
{
tree=new AVLTree();
tree.insert(new AVLNode(1,1));
assertEquals(1, tree.getRoot().value);
tree.insert(new AVLNode(2,2));
assertEquals(1, tree.getRoot().value);
assertEquals(2, tree.getRoot().right.value);
assertEquals(1, tree.getRoot().balance);
assertEquals(0, tree.getRoot().right.balance);
tree.insert(new AVLNode(3,3));
assertEquals(2, tree.getRoot().value);
assertEquals(3, tree.getRoot().right.value);
assertEquals(1, tree.getRoot().left.value);
assertEquals(0, tree.getRoot().balance);
assertEquals(0, tree.getRoot().left.balance);
assertEquals(0, tree.getRoot().right.balance);
}
public void testInsertLL()
{
tree=new AVLTree();
tree.insert(new AVLNode(3,3));
assertEquals(3, tree.getRoot().value);
tree.insert(new AVLNode(2,2));
assertEquals(3, tree.getRoot().value);
assertEquals(2, tree.getRoot().left.value);
assertEquals(-1, tree.getRoot().balance);
assertEquals(0, tree.getRoot().left.balance);
tree.insert(new AVLNode(1,1));
assertEquals(2, tree.getRoot().value);
assertEquals(3, tree.getRoot().right.value);
assertEquals(1, tree.getRoot().left.value);
assertEquals(0, tree.getRoot().balance);
assertEquals(0, tree.getRoot().left.balance);
assertEquals(0, tree.getRoot().right.balance);
}
public void testInsertRL()
{
tree=new AVLTree();
tree.insert(new AVLNode(2,2));
assertEquals(2, tree.getRoot().value);
tree.insert(new AVLNode(3,3));
assertEquals(2, tree.getRoot().value);
assertEquals(3, tree.getRoot().right.value);
assertEquals(1, tree.getRoot().balance);
assertEquals(0, tree.getRoot().right.balance);
tree.insert(new AVLNode(1,1));
assertEquals(2, tree.getRoot().value);
assertEquals(3, tree.getRoot().right.value);
assertEquals(1, tree.getRoot().left.value);
assertEquals(0, tree.getRoot().balance);
assertEquals(0, tree.getRoot().left.balance);
assertEquals(0, tree.getRoot().right.balance);
}
public void testInsertLR()
{
tree=new AVLTree();
tree.insert(new AVLNode(2,2));
assertEquals(2, tree.getRoot().value);
tree.insert(new AVLNode(1,1));
assertEquals(2, tree.getRoot().value);
assertEquals(1, tree.getRoot().left.value);
assertEquals(-1, tree.getRoot().balance);
assertEquals(0, tree.getRoot().left.balance);
tree.insert(new AVLNode(3,3));
assertEquals(2, tree.getRoot().value);
assertEquals(3, tree.getRoot().right.value);
assertEquals(1, tree.getRoot().left.value);
assertEquals(0, tree.getRoot().balance);
assertEquals(0, tree.getRoot().left.balance);
assertEquals(0, tree.getRoot().right.balance);
}
public void testGetNode()
{
tree=newTree();
assertEquals(6,tree.getAVLNodeByKey(6).value);
}
public void testHeadAndTail()
{
tree=newTree();
assertEquals(11,tree.getRoot().getLargest().value);
assertEquals(1,tree.getRoot().getSmallest().value);
}
public void testDeleteRL()
{
tree=newTree();
assertEquals(4,tree.getRoot().key);
assertNull(tree.getRoot().parent);
assertEquals(5,tree.getRoot().right.getSmallest().key);
assertEquals(1,tree.getRoot().balance);
tree.delete(tree.getRoot().key);
assertEquals(5,tree.getRoot().key);
assertEquals(0,tree.getRoot().balance);
}
private AVLTree newTree()
{
tree=new AVLTree();
tree.insert(new AVLNode(2,2));
tree.insert(new AVLNode(1,1));
tree.insert(new AVLNode(3,3));
tree.insert(new AVLNode(4,4));
tree.insert(new AVLNode(5,5));
tree.insert(new AVLNode(6,6));
tree.insert(new AVLNode(7,7));
tree.insert(new AVLNode(11,11));
return tree;
}
}
目前只做了简单的测试。。。
分享到：
相关推荐
avl tree 中的各种旋转
使用C++实现的AVLTree自平衡二叉树，支持动态插入与删除操作，供C++数据结构课程学习与交流使用。
本设计实现了AVLTree的所有的实现功能，也包括BinSTree与AVLTree的转换
一个avltree的简单实现，便于了解avltree的结构及应用
这是一个用C实现的AVL tree，带MFC的测试程序。 在我的机器上(P4 T2050 Duo, 1G memory)列C盘所有文件并组织成AVL tree，一共是70000多个文件和目录，耗时大约是5-7秒
AVL Tree source code
4. `avltree_test`：这个可能是编译后的可执行文件，当运行这个文件时，它会执行`avltree_test.c`中的测试代码，展示AVL树的运作情况。 关于AVL树的实现，主要涉及以下几个核心概念： - **节点定义**：每个节点...
An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is...
AVL tree using node from data structure and algorithm java class, create a minimum AVL tree with minimum number of nodes at given high
`AVL_tree.ncb`、`AVL_tree.sln`、`AVL_tree.suo`和`AVL_tree`可能是Visual Studio项目文件，包含了实现AVL树数据结构的源代码。`ncb`文件是Visual Studio的非编译缓存，`sln`是解决方案文件，`suo`存储用户特定的...
在"www.pudn.com.txt"和"AVLTree"这两个文件中，可能包含了关于AVL树的更多详细信息，如实现代码、示例或进一步的解释。学习AVL树不仅能够理解其基本概念和操作，还能深入理解数据结构的设计和优化，这对于理解和...
AVLTree.java文件应该包含了AVL树的实现，包括节点类的定义、插入、删除、旋转等核心功能。通过阅读和理解这个源代码，你可以深入学习AVL树的原理和操作，这对于理解和使用自平衡二叉查找树是非常有价值的。在实际...
综上所述，"AVLtree_c_avl_平衡二叉树_avltree_"这个项目可能是用C语言实现了一个AVL树的数据结构，并提供了对树的增删改查操作，同时具备用户友好的交互界面。这个项目对于理解和实践AVL树的概念、操作和性能优化...
自己写的平衡树的构建及相关操作
4. **代码实现**：`PAT 1066 Root of AVL Tree.cpp` 文件可能包含了实现AVL树的基本数据结构、插入、删除和平衡调整的函数。在实际编程中，通常会定义一个AVL树节点结构体，包含键值、子节点指针、以及平衡因子。...
在"03平衡二叉树_AVLTree.c"这个文件中，应该包含了C语言实现AVL树的代码，包括节点结构定义、插入、删除和查找等基本操作，以及相应的旋转函数。通过阅读和理解这段代码，可以深入学习AVL树的内部工作原理和操作...
AVL树是一种自平衡的二叉搜索树，由G. M. Adelson-Velsky和E. M. Landis在1962年提出，因此得名AVL树。它的主要特点是任何节点的两个子树的高度差不超过1，这使得AVL树具有较高的查找效率。在AVL树中，平均查找长度...
AVL树是一种自平衡二叉查找树（Binary Search Tree, BST），由Georgy Adelson-Velsky和Emanuel Landis于1962年提出，因此得名AVL树，其中A、V、L分别是他们姓氏的首字母。在AVL树中，每个节点的两个子树的高度差最多...
在二叉树的基础上，二叉查找树（Binary Search Tree，BST）是一种特殊的二叉树，其每个节点的值都大于其左子树中的任何节点的值，并小于其右子树中的任何节点的值。这种性质使得二叉查找树在查找特定值时具有较高的...
AVL tree的源码实现。该AVL tree为模板容器，可以在其中放入任何东西。被放入的对象需要实现拷贝构造函数与赋值构造函数。该程序能够在linux下面顺利通过编译。平时随意开发，如有不足之处，还请见谅！！！