什么是平衡二叉树？
平衡二叉树 ：（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：
它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。
在讲解平衡二叉树之前我们先了解以下树的高度以及层的概念
（图片引用于网络）
查询树的高度
思路：
通过递归实现查询当前节点的左右子树的最大高度，然后再 + 1（加上节点本身），此时就是树的最大高度
//查询树的高度 public int height(){ return Math.max(left == null ? 0:left.height(),right == null ? 0:right.height()) + 1; }
查询左右子树的高度
//查询左子树的高度 public int leftHeight(){ if(left == null){ return 0; } return left.height(); } //查询右子树的高度 public int rightHeight(){ if(right == null){ return 0; } return right.height(); }
平衡二叉树实现
左旋转
节点的左子树的高度即h(左) 和 右子树即h(右)的差值大于1 。
具体来说就是 h(右) - h(左) > 1
当满足这个情况时我们就需要进行左旋转
思路
- new 一个新的节点newNode ，value 为当前节点的value
- 设置newNode的left节点 为当前节点的left
- 设置newNode 的right节点 为当前节点的right的left节点
- 将当前节点的value设置为 当前节点的right的value
- 把当前节点的right 设置为 当前节点的right 的right
- 把当前节点的left设置为 newNode
//左旋转 public void leftRotate(){ //new 一个新的节点，值为当前节点的val Node newNode = new Node(this.val); //将当前节点的left节点 设置为newNode的left newNode.left = this.left; //把当前节点this的right的left节点 设置为newNode的right newNode.right = this.right.left; //把当前节点的val修改成 当前节点的right的val this.val = this.right.val; //把当前节点的left设置为 newNode this.left = newNode; //把当前节点的right设置为 当前节点的right的right this.right = this.right.right; }
右旋转
当前节点的左子树的高度，即h(左) 和 右子树即h(右)的差值大于1 。
具体来说就是 h(左) - h(右) > 1
当满足这个情况时我们就需要进行右旋转
思路
- new 一个新的节点newNode ，value 为当前节点的value
- 设置newNode的right节点 为当前节点的right
- 设置newNode 的left节点 为当前节点的left的right节点
- 将当前节点的value设置为 当前节点的left的value
- 把当前节点的left设置为 当前节点的left 的left
- 把当前节点的right设置为 newNode
public void rightRotate(){ //new新的节点 ，值为this.val Node newNode = new Node(this.val); //newNode 的right节点为当前节点的right节点 newNode.right = this.right; //newNode 的left节点 为当前节点的left的right节点 newNode.left = this.left.right; //修改当前节点的val为 当前节点的left 的val this.val = this.left.val; //修改当前节点的left 为 当前节点的left 的 left this.left = this.left.left; //修改当前节点的right 为newNode this.right = newNode; }
双旋转
双旋转出现的原因
以数组【10，11，7，6，8，9】为例
如下图可以看到，以节点8为根节点的right树高度 - left树的高度 > 1
这样如果我们还是按照之前的做法势必无法得到平衡二叉树。所以我们就需要先将以节点8 为根节点的二叉树进行左旋转使它成为平衡二叉树之后，再对整棵树进行右旋转， 这样我们才能使整棵树都是平衡二叉树
(图片引用于csdn博主菜鸟要翱翔)
解决思路
如果当前树需要进行左旋转（即(rightHeight() - leftHeight() > 1)）
那么就需要判断右节点的rightHeight 是否 < rightHeight
如果满足， 那么就先将以right节点为根节点的树进行右旋转 ，然后再将整个树进行左旋转
同理
当前树需要进行右旋转（即(leftHeight() - rightHeight() > 1)）
那么就需要判断左节点的rightHeight 是否 > leftHeight
如果满足， 那么就先将以left节点为根节点的树进行左旋转 ，然后再将整个树进行右旋转
if (rightHeight() - leftHeight() > 1){ //当前节点的右子树的右子树高度 < 当前节点的右子树的左子树高度 if (right != null && right.rightHeight() < right.leftHeight()){ //先将右子树进行右旋转 ，然后再将所有的树进行左旋转 right.rightRotate(); leftRotate(); }else { leftRotate(); } } else if (leftHeight() - rightHeight() > 1){ //当前节点的左子树的右子树高度 > 当前节点的左子树的左子树高度 if (left != null && left.leftHeight() < left.rightHeight()){ //先将左子树进行左旋转 ，然后再将整棵树进行右旋转 left.leftRotate(); rightRotate(); }else { rightRotate(); } } }
代码实现
public class Node { public int val; public Node right; public Node left; //左旋转 public void leftRotate(){ //new 一个新的节点，值为当前节点的val Node newNode = new Node(this.val); //将当前节点的left节点 设置为newNode的left newNode.left = this.left; //把当前节点this的right的left节点 设置为newNode的right newNode.right = this.right.left; //把当前节点的val修改成 当前节点的right的val this.val = this.right.val; //把当前节点的left设置为 newNode this.left = newNode; //把当前节点的right设置为 当前节点的right的right this.right = this.right.right; } public void rightRotate(){ //new新的节点 ，值为this.val Node newNode = new Node(this.val); //newNode 的right节点为当前节点的right节点 newNode.right = this.right; //newNode 的left节点 为当前节点的left的right节点 newNode.left = this.left.right; //修改当前节点的val为 当前节点的left 的val this.val = this.left.val; //修改当前节点的left 为 当前节点的left 的 left this.left = this.left.left; //修改当前节点的right 为newNode this.right = newNode; } //添加树 public void add(Node node){ if(node == null){ return; } if(node.val < this.val){ if(this.left == null){ this.left = node; }else{ this.left.add(node); } }else{ //node.val >= this.val if(this.right == null){ this.right = node; }else{ this.right.add(node); } } if (rightHeight() - leftHeight() > 1){ //当前节点的右子树的右子树高度 < 当前节点的右子树的左子树高度 if (right != null && right.rightHeight() < right.leftHeight()){ //先将右子树进行右旋转 ，然后再将所有的树进行左旋转 right.rightRotate(); leftRotate(); }else { leftRotate(); } } else if (leftHeight() - rightHeight() > 1){ //当前节点的左子树的右子树高度 > 当前节点的左子树的左子树高度 if (left != null && left.leftHeight() < left.rightHeight()){ //先将左子树进行左旋转 ，然后再将整棵树进行右旋转 left.leftRotate(); rightRotate(); }else { rightRotate(); } } } //查询左子树的高度 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; } //中序遍历二叉树 public void infix(){ if(this.left != null){ this.left.infix(); } System.out.println(this); if (this.right != null){ this.right.infix(); } } public Node(int val) { this.val = val; } @Override public String toString() { return "Node[" + "val=" + val + ']'; } }
public class AVLTree { public Node root; public static void main(String[] args) { //int[] arr = {4,3,6,5,7,8}; // int[] arr = {10,12,8,9,7,6}; int[] arr = {10,11,7,6,8,9,12,33,14,1,22,0,3,33,23,44,55,54,34}; AVLTree avl = new AVLTree(); for (int i=0;i<arr.length;i++){ avl.add(new Node(arr[i])); } avl.root.infix(); System.out.println("树的高度 :" + avl.root.height()); System.out.println("树的左子树高度 :" + avl.root.leftHeight()); System.out.println("树的右子树高度 :" + avl.root.rightHeight()); }
public void add(Node node){
if (root == null){
root = node;
}else{
root.add(node);
}
}
}
运行结果
Node[val=0]
Node[val=1]
Node[val=3]
Node[val=6]
Node[val=7]
Node[val=8]
Node[val=9]
Node[val=10]
Node[val=11]
Node[val=12]
Node[val=14]
Node[val=22]
Node[val=23]
Node[val=33]
Node[val=33]
Node[val=34]
Node[val=44]
Node[val=54]
Node[val=55]
树的高度 :5
树的左子树高度 :3
树的右子树高度 :4
进程已结束,退出代码0
