什么是平衡二叉树?
平衡二叉树 :(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:
它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题,把插入,查找,删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间,不过相对二叉查找树来说,时间上稳定了很多。
在讲解平衡二叉树之前我们先了解以下树的高度以及层的概念
(图片引用于网络)
查询树的高度
思路:
通过递归实现查询当前节点的左右子树的最大高度,然后再 + 1(加上节点本身),此时就是树的最大高度
1 2 3 4
| public int height(){ return Math.max(left == null ? 0:left.height(),right == null ? 0:right.height()) + 1; }
|
查询左右子树的高度
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| public void leftRotate(){ Node newNode = new Node(this.val); newNode.left = this.left; newNode.right = this.right.left; this.val = this.right.val; this.left = newNode; 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| public void rightRotate(){ Node newNode = new Node(this.val); newNode.right = this.right; newNode.left = this.left.right; this.val = this.left.val; this.left = this.left.left; 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节点为根节点的树进行左旋转 ,然后再将整个树进行右旋转
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| 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(); } } }
|
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118
| public class Node { public int val; public Node right; public Node left;
public void leftRotate(){ Node newNode = new Node(this.val); newNode.left = this.left; newNode.right = this.right.left; this.val = this.right.val; this.left = newNode; this.right = this.right.right; }
public void rightRotate(){ Node newNode = new Node(this.val); newNode.right = this.right; newNode.left = this.left.right; this.val = this.left.val; this.left = this.left.left; 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{ 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 + ']'; } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| public class AVLTree { public Node root; public static void main(String[] args) { 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