平衡二叉树（AVL）详解
说明
-
平衡二叉树又称平衡二叉排序树，是二叉排序树的一种特殊类型
-
平衡二叉树主要为了解决二叉搜索树出现的一些问题，比如如果二叉搜索树的各个节点的值是按照顺序的，那么二叉排序树的形式会形如单链表，但是它的查找速度会比单链表慢，因为二叉排序树在遍历时还要考虑左子树或者右子树，即使他们都是空的，因此引入平衡二叉树
-
平衡二叉树要求左右子树的高度差的绝对值小于等于1，因此它是一颗平衡树
-
平衡二叉树在创建时，会不停的判断左子树和右子树的高度关系，一旦左子树与右子树的高度差大于1，就需要左旋或者右旋甚至双旋转进行矫正
-
左旋是指右子树的高度-左子树的高度>1的情况，具体思路如下：
-
创建一个新节点，将当前节点的值指向新节点
-
然后新节点的左子树指向当前节点的左子树
-
新节点的右子树指向当前节点右子树的左子树
-
当前节点的值用当前节点右子树的值替换
-
当前节点的右子树指向右子树的右子树
-
当前节点的左子树指向新节点
-
-
右旋是左子树的高度 - 右子树的高度 > 1的情况，思路如同左旋，方向改变即可
-
双旋转是指当前节点的左子树高度>右子树的高度，需要右旋，但是当前节点左子树的右子树高度>左子树的高度，如果不对左子树进行处理直接右旋的话，会发现旋转后的树依旧不平衡，会出现右子树的高度大于左子树的高度，右需要左旋，但是依旧不成功，因此需要对当前节点的左子树进行处理，先将左子树进行左旋，再将当前树进行右旋
-
另一种情况，及右子树的高度>左子树的高度，但右子树的左子树的高度大于右子树的高度，这种情况也雷同，因此需要先对当前节点的右子树进行右旋，再对当前节点进行左旋
-
源码及思路见下
源码及分析
左旋右旋
//右旋转,思路和左旋转类似
public void rightRotate() {
Node newNode = new Node(this.value);
newNode.right = this.right;
newNode.left = this.left.right;
this.value = this.left.value;
this.left = this.left.left;
this.right = newNode;
}
//左旋转
public void leftRotate() {
//创建新树的根节点
Node newNode = new Node(this.value);
//新树左子树连接当前树的左子树
newNode.left = this.left;
//新树的右子树连接当前树的右子树的左子树
newNode.right = this.right.left;
//当前根节点的值用右节点的值替换
this.value = this.right.value;
//当前树的右子树连接右子树的右子树
this.right = this.right.right;
//将新树作为当前树的左子树
this.left = newNode;
}
//左子树高度
public int leftHeight() {
if (left == null) {
return 0;
}
return left.height();
}
//右子树高度
public int rightHeight() {
if (right == null) {
return 0;
}
return right.height();
}
//返回以当前节点为根节点的树的高度
public int height() {
return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}
平衡二叉树代码实现
package algorithm.tree.avl;
/**
* @author AIMX_INFO
* @version 1.0
*/
public class AVLTree {
public static void main(String[] args) {
AVL avl = new AVL();
//int[] arr = {4, 3, 6, 5, 7, 8};
//int[] arr = {10, 12, 8, 9, 7, 6};
int[] arr = {10, 11, 7, 6, 8, 9};
for (int i = 0; i < arr.length; i++) {
avl.add(new Node(arr[i]));
}
//中序遍历
avl.infixOrder();
//树的高度
System.out.println("树高度: " + avl.getRoot().height());
System.out.println("左子树高度: " + avl.getRoot().leftHeight());
System.out.println("右子树高度: " + avl.getRoot().rightHeight());
}
}
//二叉排序树
class AVL {
private Node root;
//中序遍历
public void infixOrder() {
if (root != null) {
root.infixOrder();
} else {
System.out.println("树是空的");
}
}
public Node getRoot() {
return root;
}
//添加节点
public void add(Node node) {
if (root == null) {
root = node;
} else {
root.add(node);
}
}
//查找某一节点
public Node search(int value) {
if (root == null) {
return null;
} else {
return root.search(value);
}
}
//查找某一节点的父节点
public Node searchParent(int value) {
if (root == null) {
return null;
} else {
return root.searchParent(value);
}
}
//删除节点
public void delNode(int value) {
//先判断是否为空树
if (root == null) {
return;
} else {
//如果树不为空，再判断树是否只有一个空节点
if (root.left == null && root.right == null && root.value == value) {
root = null;
return;
}
//否则先查找要删除的节点
Node target = search(value);
//判断要删除节点是否存在
if (target == null) {
return;
}
//如果存在则再找到要删除节点的父节点
Node parent = searchParent(value);
//然后根据要删除的节点分情况删除
//如果要删除的节点是叶子节点
if (target.left == null && target.right == null) {
//判断target是父节点的左子节点还是右子节点
//如果是左子节点
if (parent.left != null && parent.left.value == value) {
parent.left = null;
}
//如果是左子节点
if (parent.right != null && parent.right.value == value) {
parent.right = null;
}
//如果要删除的节点有两个子节点
} else if (target.left != null && target.right != null) {
int minVal = delRightNodeMin(target.right);
target.value = minVal;
//否则要删除的节点只有一个子节点
} else {
//判断要删除的节点有左子节点还是右子节点
//target的左子节点不为空
if (target.left != null) {
//判断target是父节点的左子树还是右子树
//左子树
if (parent != null) {
if (parent.left.value == value) {
parent.left = target.left;
} else {
//右子树
parent.right = target.left;
}
} else {
root = target.left;
}
//target的右子节点不为空
} else {
//同理
if (parent != null) {
if (parent.left.value == value) {
parent.left = target.right;
} else {
parent.right = target.right;
}
} else {
root = target.right;
}
}
}
}
}
/**
* 查找当前二叉排序树的最小节点并删除
*
* @param node 当前二叉排序树
* @return 返回最小节点的值
*/
public int delRightNodeMin(Node node) {
//辅助变量用于遍历二叉排序树
Node target = node;
//循环查找最小节点
while (target.left != null) {
target = target.left;
}
//循环结束时已经找到
//删除当前节点
delNode(target.value);
//返回当前节点的值
return target.value;
}
}
//节点
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
//右旋转,思路和左旋转类似
public void rightRotate() {
Node newNode = new Node(this.value);
newNode.right = this.right;
newNode.left = this.left.right;
this.value = this.left.value;
this.left = this.left.left;
this.right = newNode;
}
//左旋转
public void leftRotate() {
//创建新树的根节点
Node newNode = new Node(this.value);
//新树左子树连接当前树的左子树
newNode.left = this.left;
//新树的右子树连接当前树的右子树的左子树
newNode.right = this.right.left;
//当前根节点的值用右节点的值替换
this.value = this.right.value;
//当前树的右子树连接右子树的右子树
this.right = this.right.right;
//将新树作为当前树的左子树
this.left = newNode;
}
//左子树高度
public int leftHeight() {
if (left == null) {
return 0;
}
return left.height();
}
//右子树高度
public int rightHeight() {
if (right == null) {
return 0;
}
return right.height();
}
//返回以当前节点为根节点的树的高度
public int height() {
return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}
//查找某一节点
/**
* @param value 要查找的节点的值
* @return 返回查找的结果
*/
public Node search(int value) {
//如果要查找的节点就是当前节点，直接返回
if (value == this.value) {
return this;
}
//判断要查找的节点的value与当前节点的value的大小关系
//向左递归查找
if (value < this.value) {
//判断左子树是否为空
if (this.left == null) {
return null;
}
return this.left.search(value);
} else {
//向右递归查找
//判断右子树是否为空
if (this.right == null) {
return null;
}
return this.right.search(value);
}
}
//查找要删除节点的父节点
/**
* @param value 要删除的节点的值
* @return 返回查找的结果
*/
public Node searchParent(int value) {
//判断当前节点是不是要查找节点的父节点
if ((this.left != null && this.left.value == value) ||
(this.right != null && this.right.value == value)) {
return this;
} else {
//如果不是则向左向右递归查找
//向左递归
if (value < this.value && this.left != null) {
return this.left.searchParent(value);
//向右递归
} else if (value >= this.value && this.right != null) {
return this.right.searchParent(value);
} else {
//否则没有找到
return null;
}
}
}
//递归添加节点的方法
public void add(Node node) {
//数据校验
if (node == null) {
return;
}
//根据要添加的节点的值和当前节点值的大小判断节点要添加的位置
if (node.value < this.value) {
//如果当前左子节点为空，则直接添加
if (this.left == null) {
this.left = node;
} else {
//否则递归添加
this.left.add(node);
}
} else {
//同理
if (this.right == null) {
this.right = node;
} else {
this.right.add(node);
}
}
//添加完节点后，如果 (右子树的高度 - 左子树的高度 ) > 1,则左旋
if (rightHeight() - leftHeight() > 1) {
//如果当前右子树的左子树高度大于右子树高度，则先对当前右子树右旋
//再对当前数左旋
if (right != null && right.leftHeight() > right.rightHeight()) {
right.rightRotate();
leftRotate();
} else {
//否则直接左旋
leftRotate();
}
//开始下一次添加节点
return;
}
//添加完节点后，如果 (左子树的高度 - 右子树的高度 ) > 1,则右旋
if (leftHeight() - rightHeight() > 1) {
//如果当前左子树的右子树高度大于左子树高度，则先对左子树进行左旋，
//再对当前树右旋
if (left != null && left.rightHeight() > left.leftHeight()) {
left.leftRotate();
rightRotate();
} else {
//否则直接右旋
rightRotate();
}
}
}
//中序遍历
public void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.infixOrder();
}
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
}