恐怖的AVL树
2024-10-20 03:12:32
学习参考：http://www.cnblogs.com/Camilo/p/3917041.html
今天闲来无事打算学习AVL树，并以AVL树的插入作为切入点。
不知不觉，我就在电脑前编了4个小时……不知道是Java的引用有问题，还有C的指针也有同样的操作。比如node是递归函数中操作的一个结点，但是node是null，是他的父对象所指的。如果对node进行了赋值，但是node的父对象所指的还是null。
这个问题很复杂，从始至终都反映在我的代码中。
下面贴出调试了N遍的插入代码：
// 当前节点 父节点
void AVLinsert(BTNode node,BTNode parent,boolean isLeft,String data){
int dataV=Integer.valueOf(data).intValue();
int nodeV=0;
if(node!=null) nodeV=Integer.valueOf(node.data).intValue();
if(node==null){
BTNode newNode=new BTNode();
newNode.data=data;
if(isLeft) parent.lChild=newNode;
else parent.rChild=newNode;
} else if(dataV<nodeV){//向左插入
AVLinsert(node.lChild,node,true,data);
node.height=Math.max(getHeight(node.lChild), getHeight(node.rChild))+1;//递归增加树的高度 System.out.println("sub="+(getHeight(node.lChild)-getHeight(node.rChild)));
System.out.println("node="+node.data); if(getHeight(node.lChild)-getHeight(node.rChild)==2){
System.out.println("L变形前\n"+this);
if(getHeight(node.lChild.lChild)>getHeight(node.lChild.rChild)){
System.out.println("LL");
boolean flag=false;
if(root.data.equals(node.data)) flag=true;
if(!flag){
if(isLeft) parent.lChild=LLRotate(node);
else parent.rChild=LLRotate(node);
}else node=LLRotate(node);
if(flag) root=node;
}else{
System.out.println("LR");
boolean flag=false;
if(root.data.equals(node.data)) flag=true;
if(!flag){
if(isLeft) parent.lChild=LRRotate(node);
else parent.rChild=LRRotate(node);
}else node=LRRotate(node);
if(flag) root=node;
}
System.out.println("变形后\n"+this);
}
System.out.println(this); }else{
AVLinsert(node.rChild,node,false,data);
node.height=Math.max(getHeight(node.lChild), getHeight(node.rChild))+1;//递归增加树的高度 System.out.println("sub="+(getHeight(node.lChild)-getHeight(node.rChild)));
System.out.println("node="+node.data); if(getHeight(node.lChild)-getHeight(node.rChild)==-2){
System.out.println("R变形前\n"+this);
if(getHeight(node.rChild.lChild)>getHeight(node.rChild.rChild)){
System.out.println("RL");
boolean flag=false;
if(root.data.equals(node.data)) flag=true;
if(!flag){
if(isLeft) parent.lChild=RLRotate(node);
else parent.rChild=RLRotate(node);
}else node=RLRotate(node);
if(flag) root=node;
}else{
System.out.println("RR");
boolean flag=false;
if(root.data.equals(node.data)) flag=true;
if(!flag){
if(isLeft) parent.lChild=RRRotate(node);
else parent.rChild=RRRotate(node);
}else node=RRRotate(node);
if(flag) root=node;
}
System.out.println("变形后\n"+this);
}
System.out.println(this);
}
}
可以看出我都要炸了。写的很乱，但是能跑起来了，以后再优化。
AVL树平衡旋转函数：
BTNode LLRotate(BTNode node){//左子树.高度-右子树.高度==2 【向右旋转】
/*
* 根节点的左孩子 为新的根节点。
* 老根节点成为新根节点的右孩子
* 根节点的左孩子 的右子树作为 老根节点的左子树
*/
BTNode pre=node;
node=node.lChild;//根节点的左孩子 为新的根节点。
//从此之后node就是【根节点的左孩子】
pre.lChild=node.rChild;//根节点的左孩子(node) 的右子树作为 老根节点(pre)的左子树
node.rChild=pre;
//pre: 老根节点
pre.height=Math.max(getHeight(pre.lChild), getHeight(pre.rChild))+1;//递归增加树的高度
node.height=Math.max(getHeight(node.lChild), getHeight(node.rChild))+1;//递归增加树的高度
return node;//返回根节点
}
BTNode RRRotate(BTNode node){//左子树.高度-右子树.高度==-2 【向左旋转】
/*
* 根节点的左孩子 为新的根节点。
* 老根节点成为新根节点的右孩子
* 根节点的左孩子 的右子树作为 老根节点的左子树
*/
BTNode pre=node;
node=node.rChild;//根节点的右孩子 为新的根节点。
//从此之后node就是【根节点的左孩子】
pre.rChild=node.lChild;//根节点的左孩子(node) 的右子树作为 老根节点(pre)的左子树
node.lChild=pre;
//pre: 老根节点
pre.height=Math.max(getHeight(pre.lChild), getHeight(pre.rChild))+1;//递归增加树的高度
node.height=Math.max(getHeight(node.lChild), getHeight(node.rChild))+1;//递归增加树的高度
return node;
}
BTNode LRRotate(BTNode node){//左子树.高度-右子树.高度==2 【向右旋转】
node.lChild=RRRotate(node.lChild);
node=LLRotate(node);
return node;
}
BTNode RLRotate(BTNode node){//左子树.高度-右子树.高度==2 【向右旋转】
node.rChild=LLRotate(node.rChild);
node=RRRotate(node);
return node;
}
int getHeight(BTNode node){
if(node!=null){
return node.height;
}else{
return 0;
}
}
完整代码：
import java.util.*;
public class demo {
public static void main(String args[]){
BTtree tree=new BTtree(3);
tree.InOrderTraversal();
System.out.print(tree);
BThrTree thrTree=new BThrTree(tree);
thrTree.InOrderTraversal();
thrTree.InThreadingFabric();
thrTree.InOrderTraversal_Thr();
int []nums={45,12,53,3,37,24,100,61,90,78};
AVLTree avl=new AVLTree(nums);
avl.test();
// System.out.println(avl);
// System.out.println(avl.root.height);
// thrTree.InOrderTraversal_Thr();
}
}
class BTtree{//二叉树类
class BTNode{//节点类
String data=new String("0");
BTNode lChild=null;
BTNode rChild=null;
boolean LTag=false;//=0 : 指向左孩子。 =1 : 指向前驱
boolean RTag=false;//=0 : 指向右孩子。 =1 : 指向后继
int height=1; //用于AVL树
BTNode(){}
BTNode(String data){this.data=data;}
BTNode(int num){this.data=Integer.toString(num);};
}
protected BTNode root=new BTNode();
BTtree(){
}
BTtree(int layer){
//用队列的方式构造n层树
List<BTNode> queue=new ArrayList<BTNode>();
int front=0;
int rear=0;//队尾插入
queue.add(root);//初始化入队
rear++;
int i , k=0 , j;
for(j=0;j<layer;j++){
int nowRear=rear;
for(i=front;i<nowRear;i++){
//出队，生两个孩子
BTNode parent=queue.get(front++);
BTNode lChild=new BTNode();
lChild.data=Integer.toString(++k);
BTNode rChild=new BTNode();
rChild.data=Integer.toString(++k);
parent.lChild=lChild;
parent.rChild=rChild;
queue.add(lChild);
rear++;
queue.add(rChild);
rear++;
}
}
}
BTtree(String express){//通过中缀表达式进行构造
//1.对表达式进行括号补全。
}
public String toString(){//重写打印函数
List<BTNode> queue=new ArrayList<BTNode>();
List<String[]> PrintList=new ArrayList<String[]>();
int front=0;
int rear=0;//队尾插入
queue.add(root);//初始化入队
rear++;
int i , k=0 , j;
String emptySignal=new String("");//空信号
String str[]=new String[1];
str[0]=root.data;
PrintList.add(str);//打印数据结构初始化
int layer=1;//下一层字符串的数目是2^1=2。
int pos=0;
boolean flag=true;
ok:
while(flag){
pos=0;//pos初始化
String tmp[]=new String[(int)Math.pow((int)2, (int)(layer++))];//length=2^layer
flag=false; //循环标志初始化
int nowRear=rear;
int nowFront=front;
for(i=front;i<nowRear;i++){
String nowStr=new String();
BTNode parent=queue.get(front++);
if(parent==null) break ok; //跳出两重循环
if(parent.data.equals(emptySignal)){//如果是空的，派生出两个空孩子
for(int t=0;t<2;t++){
tmp[pos++]="*";
BTNode empty=new BTNode();
empty.data=emptySignal;
queue.add(empty);rear++;
}
}else{
if(parent.lChild!=null){
flag=true; //只要这一层存在孩子，就可以继续循环下去。
queue.add(parent.lChild);
tmp[pos++]=parent.lChild.data;
rear++;
}else{
tmp[pos++]="*";
BTNode empty=new BTNode();
empty.data=emptySignal;
queue.add(empty);
rear++;
}
if(parent.rChild!=null){
flag=true;
queue.add(parent.rChild);
tmp[pos++]=parent.rChild.data;
rear++;
}else{
tmp[pos++]="*";
BTNode empty=new BTNode();
empty.data=emptySignal;
queue.add(empty);
rear++;
}
}
} // end of for
PrintList.add(tmp);
} // end of while
/*
for(i=0;i<PrintList.size();i++){
for(j=0;j<PrintList.get(i).length;j++) System.out.print(PrintList.get(i)[j]+" ");
System.out.println();
}*/
//后处理
String[] PrintListLine=new String[PrintList.size()-1];
for(i=PrintListLine.length-1;i>=0;i--){//循环构造
//首先进行构造
String tmp=new String();
for(j=0;j<PrintList.get(i).length;j++){
tmp+=PrintList.get(i)[j];
if(j!=PrintList.get(i).length-1) tmp+=" ";
}
PrintListLine[i]=tmp;
}
for(i=PrintListLine.length-2;i>=0;i--){//居中操作
int spaceNum=(PrintListLine[i+1].length()-PrintListLine[i].length())/2;
String space=new String();
for(int t=0;t<spaceNum;t++) space+=" ";
PrintListLine[i]=space+PrintListLine[i]+space;
}
String outStr=new String();
for(i=0;i<PrintListLine.length;i++){//最后构造一个字符串
outStr+=PrintListLine[i]+"\n";
}
return outStr;
}
void PreOrderTraversal(){
PreOrder(root);
System.out.println();
}
void PreOrder(BTNode obj){
if(obj!=null){
System.out.print(obj.data+",");
PreOrder(obj.lChild);
PreOrder(obj.rChild);
}
}
void InOrderTraversal(){
InOrder(root);
System.out.println();
}
void InOrder(BTNode obj){
if(obj!=null){
InOrder(obj.lChild);
System.out.print(obj.data+",");
InOrder(obj.rChild);
}
}
}
//线索二叉树
class BThrTree extends BTtree{
BThrTree(BTtree obj){//由父类构造而来
//首先拷贝根节点
BTNode tmp=new BTNode();
tmp.data=obj.root.data;
copy(root,obj.root);
}
void copy(BTNode node1,BTNode node2){
if(node2.lChild!=null){//左树递归
BTNode l=new BTNode();
l.data=node2.lChild.data;//拷贝左树
node1.lChild=l;//左树赋值
copy(node1.lChild,node2.lChild);
}
if(node2.rChild!=null){//右树递归
BTNode r=new BTNode();
r.data=node2.rChild.data;//拷贝右树
node1.rChild=r;//右树赋值
copy(node1.rChild,node2.rChild);
}
}
public void InThreadingFabric(){//中序线索化构造
BTNode now=root;
InThreading(now);
pre.RTag=true;//【最后一个后继为null】
pre.rChild=null;
}
private BTNode pre=null;//前驱指针
private void InThreading(BTNode node){//中序线索化递归
if(node!=null){//保证节点非空
InThreading(node.lChild);//左子树线索化
if(node.lChild==null){//如果左子树不存在
node.LTag=true;//线索化
node.lChild=pre;//前驱 【第一个前驱为null】
}
if(pre!=null && pre.rChild==null){//后继
pre.RTag=true;
pre.rChild=node;
}
pre=node;//保持pre指向node的前驱。
InThreading(node.rChild);//左子树线索化
}
}
void InOrderTraversal_Thr(){//线索化遍历
BTNode now=root;
//遍历前驱
while(now.lChild!=null){//要么有左子树。
now=now.lChild;
}
while(now!=null){//要么有左子树。
System.out.print(now.data+",");
if(now.RTag){now=now.rChild;}//如果是后继，就继续后继。
else{
now=now.rChild;//如果不是，则令右子树的最左节点为后继
while(!now.LTag) now=now.lChild;
}
}
System.out.println();
}
}
class SearchBST extends BTtree{//二叉查找树
SearchBST(int[] nums){//由二维数组构造
root.data=String.valueOf(nums[0]);//构造根节点
for(int i=1;i<nums.length;i++){//对其他元素进行构造
BTNode node=new BTNode();
node.data=String.valueOf(nums[i]);//构造叶子节点
BTNode parent=root;
int nodeV=nums[i];
while(parent!=null){
int parentV=Integer.valueOf(parent.data).intValue();//当前根节点的值
if(nodeV<parentV){//左叶子
if(parent.lChild==null){//当前根节点的左叶子非空
parent.lChild=node;//挂入节点
break; //如果这里没有加【break】，就会死循环。待解决☆☆☆
}
parent=parent.lChild;//如果这里空了，跳出循环
}else{
if(parent.rChild==null){
parent.rChild=node;//挂入节点
break; //☆☆☆
}
parent=parent.rChild;//如果这里空了，跳出循环
}
}
}
}
SearchBST(){}
}
class AVLTree extends BTtree{ //平衡二叉树
AVLTree(int[] nums){//由二维数组构造
root.data=String.valueOf(nums[0]);
for(int i=1;i<nums.length;i++) AVLinsert(root,null,true,String.valueOf(nums[i]));
}
BTNode LLRotate(BTNode node){//左子树.高度-右子树.高度==2 【向右旋转】
/*
* 根节点的左孩子 为新的根节点。
* 老根节点成为新根节点的右孩子
* 根节点的左孩子 的右子树作为 老根节点的左子树
*/
BTNode pre=node;
node=node.lChild;//根节点的左孩子 为新的根节点。
//从此之后node就是【根节点的左孩子】
pre.lChild=node.rChild;//根节点的左孩子(node) 的右子树作为 老根节点(pre)的左子树
node.rChild=pre;
//pre: 老根节点
pre.height=Math.max(getHeight(pre.lChild), getHeight(pre.rChild))+1;//递归增加树的高度
node.height=Math.max(getHeight(node.lChild), getHeight(node.rChild))+1;//递归增加树的高度
return node;//返回根节点
}
BTNode RRRotate(BTNode node){//左子树.高度-右子树.高度==-2 【向左旋转】
/*
* 根节点的左孩子 为新的根节点。
* 老根节点成为新根节点的右孩子
* 根节点的左孩子 的右子树作为 老根节点的左子树
*/
BTNode pre=node;
node=node.rChild;//根节点的右孩子 为新的根节点。
//从此之后node就是【根节点的左孩子】
pre.rChild=node.lChild;//根节点的左孩子(node) 的右子树作为 老根节点(pre)的左子树
node.lChild=pre;
//pre: 老根节点
pre.height=Math.max(getHeight(pre.lChild), getHeight(pre.rChild))+1;//递归增加树的高度
node.height=Math.max(getHeight(node.lChild), getHeight(node.rChild))+1;//递归增加树的高度
return node;
}
BTNode LRRotate(BTNode node){//左子树.高度-右子树.高度==2 【向右旋转】
node.lChild=RRRotate(node.lChild);
node=LLRotate(node);
return node;
}
BTNode RLRotate(BTNode node){//左子树.高度-右子树.高度==2 【向右旋转】
node.rChild=LLRotate(node.rChild);
node=RRRotate(node);
return node;
}
// 当前节点 父节点
void AVLinsert(BTNode node,BTNode parent,boolean isLeft,String data){
int dataV=Integer.valueOf(data).intValue();
int nodeV=0;
if(node!=null) nodeV=Integer.valueOf(node.data).intValue();
if(node==null){
BTNode newNode=new BTNode();
newNode.data=data;
if(isLeft) parent.lChild=newNode;
else parent.rChild=newNode;
}
else if(dataV<nodeV){//向左插入
AVLinsert(node.lChild,node,true,data);
node.height=Math.max(getHeight(node.lChild), getHeight(node.rChild))+1;//递归增加树的高度
System.out.println("sub="+(getHeight(node.lChild)-getHeight(node.rChild)));
System.out.println("node="+node.data);
if(getHeight(node.lChild)-getHeight(node.rChild)==2){
System.out.println("L变形前\n"+this);
if(getHeight(node.lChild.lChild)>getHeight(node.lChild.rChild)){
System.out.println("LL");
boolean flag=false;
if(root.data.equals(node.data)) flag=true;
if(!flag){
if(isLeft) parent.lChild=LLRotate(node);
else parent.rChild=LLRotate(node);
}else node=LLRotate(node);
if(flag) root=node;
}else{
System.out.println("LR");
boolean flag=false;
if(root.data.equals(node.data)) flag=true;
if(!flag){
if(isLeft) parent.lChild=LRRotate(node);
else parent.rChild=LRRotate(node);
}else node=LRRotate(node);
if(flag) root=node;
}
System.out.println("变形后\n"+this);
}
System.out.println(this);
}else{
AVLinsert(node.rChild,node,false,data);
node.height=Math.max(getHeight(node.lChild), getHeight(node.rChild))+1;//递归增加树的高度
System.out.println("sub="+(getHeight(node.lChild)-getHeight(node.rChild)));
System.out.println("node="+node.data);
if(getHeight(node.lChild)-getHeight(node.rChild)==-2){
System.out.println("R变形前\n"+this);
if(getHeight(node.rChild.lChild)>getHeight(node.rChild.rChild)){
System.out.println("RL");
boolean flag=false;
if(root.data.equals(node.data)) flag=true;
if(!flag){
if(isLeft) parent.lChild=RLRotate(node);
else parent.rChild=RLRotate(node);
}else node=RLRotate(node);
if(flag) root=node;
}else{
System.out.println("RR");
boolean flag=false;
if(root.data.equals(node.data)) flag=true;
if(!flag){
if(isLeft) parent.lChild=RRRotate(node);
else parent.rChild=RRRotate(node);
}else node=RRRotate(node);
if(flag) root=node;
}
System.out.println("变形后\n"+this);
}
System.out.println(this);
}
}
int getHeight(BTNode node){
if(node!=null){
return node.height;
}else{
return 0;
}
}
void test(){
root=new BTNode(0);
BTNode node[]=new BTNode[3];
for(int i=0;i<3;i++) node[i]=new BTNode(i+1);
root.lChild=node[0];
root.lChild.rChild=node[1];
root.lChild.lChild=node[2];
System.out.println(this);
root=LRRotate(root);
System.out.println(this);
System.out.println(root.height);
System.out.println(root.lChild.height);
System.out.println(root.rChild.height);
}
AVLTree(){}
}
程序输入：45,12,53,3,37,24,100,61,90,78
构造的树形结构：
最新文章
- U3D学习笔记1: HelloWorld
- SQL中循环和条件语句
- 在浏览器地址栏按回车、F5、Ctrl+F5刷新网页的区别
- Hadoop 基准测试与example
- View绘制--onMeasure() 、onLayout()
- 【SQL 代码】Sql分页（自用）
- Runner站立会议之个人会议（冲刺二）
- Sorting It All Out
- identifier not found error on function call
- （转载）获取当前运行的PHP版本信息
- 10.8 noip模拟试题
- SharePoint 2013 弹窗效果之URL打开方式(一)
- Android清单文件具体解释(三)----应用程序的根节点&lt;application&gt;
- api 跳转规则
- python--socket粘包
- PGM：无向图模型：马尔可夫网
- ide phpStorm更换主题
- POJ 3414 pots （未解决）
- JQuery中jsCharts图表插件（十）
- 爬取小说 spider