java - 数据结构- 平衡二叉树（AVL树）
平衡二叉树（Balanced Binary Tree）， 一般也叫做AVL树
AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis（我才知道。。。）
平衡二叉树是一种特殊的二叉排序树，它的任意节点的左子树和右子树的深度之差不超过1.
以此防止左右深度差距过大，导致的查询困难。 （变成平衡二叉树后查询起来就类似于二分查询了）
而其中的难点主要是左旋，右旋，和双旋
首先推荐一个超级好用的数据结构网站= =
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
可以动态演示各种数据结构
再添加完节点后，判断（写在添加方法中，所以会从新节点往上递归对每一个经过的节点进行检查）节点情况
1. 如果一个节点A的左子树高度 - 右子树高度 > 1, A的左子树的右子树高度 > A 的左子树的左子树高度
先对A的左子树左旋，然后对A右旋
2. 如果一个节点A的左子树高度 - 右子树高度 > 1， 且不满足上面那种情况
只对A右旋
3.如果一个节点A的右子树高度 - 左子树高度 > 1, A的右子树的左子树高度 > A的右子树的右子树高度
先对A的右子树右旋，然后对A左旋
4.如果一个节点A的右子树高度 - 左子树高度 > 1， 且不满足上面那种情况
只对A左旋
怎么说呢= =|||反正我从来不看别人的代码，看着都头晕。。。真想搞明白还是自己敲一遍练练吧。。。
package tree;public class AVLTree {
Node root;
public static void main(String args[]){
//左旋
// AVLTree avlTree1 = new AVLTree();
// avlTree1.addNode(2);
// avlTree1.addNode(1);
// avlTree1.addNode(4);
// avlTree1.addNode(3);
// avlTree1.addNode(5);
// avlTree1.addNode(6);
// avlTree1.show();
// System.out.println();
// System.out.println(avlTree1.root.nodeHeight());
// System.out.println(avlTree1.root.left.nodeHeight());
// System.out.println(avlTree1.root.right.nodeHeight());
//右旋
// AVLTree avlTree2 = new AVLTree();
// avlTree2.addNode(5);
// avlTree2.addNode(3);
// avlTree2.addNode(6);
// avlTree2.addNode(2);
// avlTree2.addNode(4);
// avlTree2.addNode(1);
// avlTree2.show();
// System.out.println();
// System.out.println(avlTree2.root.nodeHeight());
// System.out.println(avlTree2.root.left.nodeHeight());
// System.out.println(avlTree2.root.right.nodeHeight());
//右边高度 - 左边高度 > 1
//左孩子的右孩子 > 左边的左孩子
//先左子树左旋转，然后本节点右旋转
// AVLTree avlTree3 = new AVLTree();
// avlTree3.addNode(5);
// avlTree3.addNode(2);
// avlTree3.addNode(6);
// avlTree3.addNode(1);
// avlTree3.addNode(3);
// avlTree3.addNode(4);
//
// avlTree3.show();
// System.out.println();
// System.out.println("此时根节点为：" + avlTree3.root.value);
// System.out.println("此时根节点左孩子为：" + avlTree3.root.left.value);
// System.out.println("此时根节点右孩子为：" + avlTree3.root.right.value);
//
// System.out.println(avlTree3.root.nodeHeight());
// System.out.println(avlTree3.root.left.nodeHeight());
// System.out.println(avlTree3.root.right.nodeHeight());
//左边高度 - 右边高度 > 1
//右孩子的左孩子 > 右边的右孩子
//先右子树右旋转，然后本节点左旋转
AVLTree avlTree4 = new AVLTree();
avlTree4.addNode(5);
avlTree4.addNode(2);
avlTree4.addNode(8);
avlTree4.addNode(7);
avlTree4.addNode(9);
avlTree4.addNode(6);
avlTree4.show();
System.out.println();
System.out.println("此时根节点为：" + avlTree4.root.value);
System.out.println("此时根节点左孩子为：" + avlTree4.root.left.value);
System.out.println("此时根节点右孩子为：" + avlTree4.root.right.value);
System.out.println(avlTree4.root.nodeHeight());
System.out.println(avlTree4.root.left.nodeHeight());
System.out.println(avlTree4.root.right.nodeHeight());
}
public AVLTree(){
this.root = null;
}
//添加节点
public void addNode(int num){
if(root == null){
root = new Node(num);
}
else{
this.root.addNode(num);
}
}
//中序遍历 （按顺序从小到大）
public void show(){
if(root == null){
System.out.println("树为空");
}
else{
root.show();
}
}
public class Node{
public int value;
public Node left;
public Node right;
public Node(int num){
this.value = num;
}
//添加节点
public void addNode(int num){
if(num < this.value){
if(this.left == null) {
this.left = new Node(num);
}
else{
this.left.addNode(num);
};
}
else if(num >= this.value){
if(this.right == null) {
this.right = new Node(num);
}
else{
this.right.addNode(num);
};
}
//判断是否需要旋转 ,这样递归的时候就可以从底向上依次判断左右高度
int leftHeight = this.left == null ? 0 : this.left.nodeHeight();
int rightHeight = this.right == null ? 0 : this.right.nodeHeight();
if(rightHeight - leftHeight > 1){
//此时分两种情况
//如果当前节点右孩子的左孩子高度 > 右孩子的右孩子高度，需要先左旋转，然后右旋转。
//否则只左旋转
int rightLeftHeight = this.right.left == null ? 0 : this.right.left.nodeHeight();
int rightRightHeight = this.right.right == null ? 0 : this.right.right.nodeHeight();
if(rightLeftHeight > rightRightHeight ){
System.out.println("新加节点" + num + "后需要先对右子树右旋转然后左旋转");
this.right.rightRotate();
this.leftRotate();
}
else{
System.out.println("新加节点" + num + "后需要左旋转");
this.leftRotate();
}
}
if(leftHeight - rightHeight > 1){
//此时分两种情况
//如果当前节点的左子树的右子树高度 > 左子树的左子树高度，需要先右转然后左转
//否则只需要右转
int leftLeftHeight = this.left.left == null ? 0 : this.left.left.nodeHeight();
int leftRightHeight = this.left.right == null ? 0 : this.left.right.nodeHeight();
if(leftRightHeight > leftLeftHeight){
System.out.println("新加节点" + num + "后需要先对左子树左旋转然后右旋转");
this.left.leftRotate();
this.rightRotate();
}
else {
System.out.println("新加节点" + num + "后需要右旋转");
this.rightRotate();
}
}
}
//中序遍历
public void show(){
if(this.left != null){
this.left.show();
}
System.out.print(this.value + " ");
if(this.right != null){
this.right.show();
}
}
//添加节点
//1.先把节点挂在对应位置，然后判断根节点左右两边的最大深度。
//所以先咬写判断深度的算法。
//返回左子树高度
public int nodeHeight(){
// if(this.left != null && this.right == null){
// return this.left.nodeHeight() + 1;
// }
// else if(this.left == null && this.right != null){
// return this.right.nodeHeight() + 1;
// }
// else if(this.left == null && this.right == null){
// return 1;
// }
// else {
// return Math.max(this.left.nodeHeight(), this.right.nodeHeight()) + 1;
// }
return Math.max(
this.left == null ? 0 : left.nodeHeight(), //当left == null时， 左边深度为0， 不等于0时， 左边深度为 left.nodeHeight()
this.right == null ? 0 : this.right.nodeHeight() //当right == null时， 左边深度为0， 不等于0时， 左边深度为 right.nodeHeight()
) + 1;
}
//以当前节点为基准左旋 （当前节点左边和右边高度不一样）
public void leftRotate(){
//对 A 左旋时
// 1.创建一个新节点,.把 A 的值赋给 新节点
// 2.把A的左子树设为新节点的左子树，把新节点放在A的左子树,
// 3.把A的右子树的左子树设为A的右子树
// 4. 把A的右子树的值赋给A，把A的右子树的右子树给A作为新的右子树
//这样避免了找父亲的过程。
// 2 2 4 4
// 1 4 -> 2 4 -> 2 4 -> 2 5
// 3 5 1 3 5 1 3 5 1 3 6
// 6 6 6
Node newNode = new Node(this.value);
newNode.left = this.left;
this.left = newNode;
newNode.right = this.right.left;
this.value = this.right.value;
this.right =this.right.right;
}
//以当前节点为基准右旋 （当前节点左边和右边高度不一样）
public void rightRotate(){
//对 A 右旋时
// 1.创建一个新节点,.把 A 的值赋给 新节点
// 2.把A的右子树设为新节点的右子树，把新节点放在A的右子树,
// 3.把A的左子树的右子树设为新节点的左子树
// 4. 把A的左子树的值赋给A，把A的左子树的左子树给A作为新的左子树
//和左旋正好镜像，把所有的左右互换就可以了-。-
// 5 5 5 3
// 3 6 -> 3 5 -> 3 5 -> 2 5
// 2 4 2 4 6 2 4 6 1 4 6
// 1 1 1
Node newNode = new Node(this.value);
newNode.right = this.right;
this.right = newNode;
newNode.left = this.left.right;
this.value = this.left.value;
this.left = this.left.left;
}
}
}
以上是 java - 数据结构- 平衡二叉树（AVL树） 的全部内容， 来源链接： utcz.com/z/389623.html
