X16数据结构部分09
平衡二叉树概述以及左旋转实现思路
/*
平衡二叉树(AVL树)概述
解决了二叉排序树的一些问题
举一个栗子
给你1个数列{1,2,3,4,5,6}
让你构造1棵二叉排序树
根据左小右大原则
你就会构造出来只有1直向右子树延申的
所有节点最多只有1棵节点的二叉树
也就是左子树全部为空
此时你会发现
你所构造的二叉排序树更像是1棵单链表
这样的话，插入和删除速度不会受影响
但查询速度会很慢
甚至比单链表还要慢
因为在查询的时候
还需要判断左子树是否有节点
解决方案
平衡二叉树
特点
前提是二叉排序树
是1棵空树或2棵子树的高度差绝对值不超过1
并且左右2子树都是1棵平衡二叉树
常见的实现方法有红黑树，替罪羊树，AVL算法，伸展树等；
需求
给你1个数列，要求创建1棵平衡二叉树
{4,3,6,5,7,8}
左旋转思路分析
一旦右子树的高度 - 左子树的高度 > 1
就采用左旋转
降低右子树的高度
如何进行左旋转
1. 创建1个新节点，value等于当前根节点的值，创建1个当前指针，指向根节点
2. 把新节点((NODE)value = 4)的左子树设置为当前节点((ROOT)value = 4)的左子树
3. 把新节点的右子树设置为当前节点的右子树的左子树，如果没有指向null就行了
4. 把当前节点的值换成右子节点的值((ROOT)value = 6)，注意只是换，还没开始移动呢
5. 把当前节点的右子树设置为当前节点右子树的右子树((ROOT)value = 6).rightNode = ROOT.r.r
6. 当前节点的左子树指向新节点((NODE)value = 4)
左旋转过后
明显地发现原先根节点指向的右子树
这条线已经断掉了
实际上原来的右子树已经被销毁了
新出现相同的节点只是副本而已
想想有一种悲伤的感觉
代码实现的话
我会复用之前的Node1节点类
*/
树的高度求解
// 将以下方法写进Node类，创建AVLT平衡二叉树类，将原先的二叉排序树类复制进class AVLT，这里就不展示源码了
/**
* 返回左子树的高度
* 递归出口
*
* @return 左子树的高度
*/
public int leftTreeHeight() {
if (leftNode == null) {
return 0;
}
return leftNode.maximumHeightOfTree();
}
/**
* 返回右子树的高度
* 递归出口
*
* @return 右子树的高度
*/
public int rightTreeHeight() {
if (rightNode == null) {
return 0;
}
return rightNode.maximumHeightOfTree();
}
/**
* 树的最大高度
*
* @return 当前二叉树的最大高度
*/
public int maximumHeightOfTree() {
/*
程序进入方法体
递归左子树和右子树
再取最大值
还要+1的原因是当前自己
也要加上
*/
return Math.max(leftNode == null ? 0 : leftNode.maximumHeightOfTree(),
rightNode == null ? 0 : rightNode.maximumHeightOfTree()) + 1;
}
左右旋转的方法
/**
* 左旋转方法
*/
public void rotateLeft() {
/*
程序开始进行左旋转操作
1. 创建1个新节点，value等于当前根节点的值，创建1个当前指针，指向根节点
2. 把新节点((NODE)value = 4)的左子树设置为当前节点((ROOT)value = 4)的左子树
3. 把新节点的右子树设置为当前节点的右子树的左子树，如果没有指向null就行了
4. 把当前节点的值换成右子节点的值((ROOT)value = 6)，注意只是换，还没开始移动呢
5. 把当前节点的右子树设置为当前节点右子树的右子树((ROOT)value = 6).rightNode = ROOT.r.r
6. 当前节点的左子树指向新节点((NODE)value = 4)
此时
默认value是根节点
leftNode是根节点的左子树
*/
Node1 newNode = new Node1(value);
newNode.leftNode = leftNode;
newNode.rightNode = rightNode.leftNode;
value = rightNode.value;
rightNode = rightNode.rightNode;
leftNode = newNode;
}
/**
* 右旋转方法
*/
public void rotateRight() {
/*
右旋转实现思路
1. 创建1个新节点，为当前根节点的值((NEW_NODE)value = 10)
2. 新节点的右子树((NEW_NODE).r)设置为当前节点的右子树((ROOT).r)
3. 新节点的左子树((NEW_NODE).l)设置为当前节点左子树的右子树((ROOT).l.r)
4. 把当前根节点的值((ROOT).value)换成左子树节点的值((ROOT).l.value)
5. 当前节点的左子树设置为当前节点左子树的左子树
6. 把当前节点的右子树设置为新节点
此时根节点的左子树节点已经被销毁了
因为没有任何引用指向该节点
*/
Node1 newNode = new Node1(value);
newNode.rightNode = rightNode;
newNode.leftNode = leftNode.rightNode;
value = leftNode.value;
leftNode = leftNode.leftNode;
rightNode = newNode;
}
/**
* 插入节点的方法
*
* @param node 需要插入的节点
*/
public void insertNode(Node1 node) {
if (node == null) {
return;
}
/*
程序运行到此处
此时可以判断插入的节点和根节点的关系
this.value表示根节点的值
*/
if (node.value < this.value) {
if (this.leftNode == null) {
/*
程序运行到此处
说明当前插入的节点比根节点的值小
并且根节点的左子树位空
直接插入即可
*/
this.leftNode = node;
} else {
this.leftNode.insertNode(node);
}
} else {
/*
程序运行到此处
说明当前节点比根节点大
需要插入到右子树
*/
if (this.rightNode == null) {
this.rightNode = node;
} else {
this.rightNode.insertNode(node);
}
}
/*
程序运行到此处
应该判断左子树和右子树的高度
如果右子树的高度 - 左子树的高度 > 1
应该左旋转
如果左子树的高度 - 右子树的高度 > 1
应该右旋转
*/
if (rightTreeHeight() - leftTreeHeight() > 1) {
/*
程序运行到此处
先不考虑那么多
直接左旋转
*/
rotateLeft();
}
if (leftTreeHeight() - rightTreeHeight() > 1) {
rotateRight();
}
}
实现双旋转
/*
这里分析几个特殊的情况比如给你1个数组
{10,11,7,6,8,9}
构造完二叉排序树
此时满足右旋转的条件
但进行右旋转过后
仍然不是1棵平衡二叉树
双旋转思路分析和条件
1. 满足右旋转的条件
2. 左子树的右子树高度 > 右子树高度
3. 先对当前这个节点的左节点进行左旋转
4. 再对当前根节点进行右旋转即可
*/
/**
* 插入节点的方法
*
* @param node 需要插入的节点
*/
public void insertNode(Node1 node) {
if (node == null) {
return;
}
/*
程序运行到此处
此时可以判断插入的节点和根节点的关系
this.value表示根节点的值
*/
if (node.value < this.value) {
if (this.leftNode == null) {
/*
程序运行到此处
说明当前插入的节点比根节点的值小
并且根节点的左子树位空
直接插入即可
*/
this.leftNode = node;
} else {
this.leftNode.insertNode(node);
}
} else {
/*
程序运行到此处
说明当前节点比根节点大
需要插入到右子树
*/
if (this.rightNode == null) {
this.rightNode = node;
} else {
this.rightNode.insertNode(node);
}
}
/*
程序运行到此处
应该判断左子树和右子树的高度
如果右子树的高度 - 左子树的高度 > 1
应该左旋转
如果左子树的高度 - 右子树的高度 > 1
应该右旋转
注意这里需要判断是否满足双旋转的条件
*/
if (rightTreeHeight() - leftTreeHeight() > 1) {
if (rightNode != null && rightNode.leftTreeHeight() > rightNode.rightTreeHeight()) {
rightNode.rotateRight();
rotateLeft();
}else {
rotateLeft();
}
return;
}
if (leftTreeHeight() - rightTreeHeight() > 1) {
if (leftNode != null && leftNode.rightTreeHeight() > leftNode.leftTreeHeight()) {
leftNode.rotateLeft();
rotateRight();
}else {
rotateRight();
}
}
}