前言:在某些情况下二分搜索树可能会退化成为链表
例如:数字1,2,3,4,5,6的顺序添加
什么是平衡二叉树
首先满二叉树是一种平衡二叉树(满二叉树可以使得二叉树的高度达到最低的一种状态)
- 平衡二叉树的叶子节点之间的距离不会超过1
平衡二叉树和完全二叉树的对比
- 平衡二叉树:对于任意一个节点,树的左右子树的高度差不超过1的树(空树也是平衡二叉树的一种)。
- 完全二叉树:在满叉树的基础上，从最底层从右往左删去若干节点，得到的都是完全二叉树。任意一个叶子节点的差不超过1.
平衡二叉树
平衡二叉树的高度和节点数量之间的关系也是O(logn)的
二叉树平衡的判断
标注节点高度,计算平衡因子
节点高度 = 子节点最高高度 + 1
平衡因子 = 左右子树节点高度差(如果一个节点的平衡因子大于1,那么这棵二叉树就不再是平衡二叉树)
AVL树的实现
首先AVL树是一棵二分搜索树,关于二分搜索树的实现
左旋转和右旋转
当某个节点存在平衡因子大于1的时候,就需要进行相应的旋转操作
-
左旋转RR
不平衡的二分搜索树
存在关系
T1 < z < T2 < x < T3 < y < T4
变换后
进行旋转操作之后,二分搜索树又重新回到了平衡状态
代码实现
// 对节点y进行向左旋转操作，返回旋转后新的根节点x
// y x
// / \ / \
// T1 x 向左旋转 (y) y z
// / \ - - - - - - - -> / \ / \
// T2 z T1 T2 T3 T4
// / \
// T3 T4
private Node leftRotate(Node y) {
Node x = y.right;
Node T2 = x.left;
// 向左旋转过程
x.left = y;
y.right = T2;
// 更新height
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
return x;
}
-
右旋转LL
存在关系
T4 < y < T3 < x < T1 < z < T2
旋转变化后
代码实现
// 对节点y进行向右旋转操作，返回旋转后新的根节点x
// y x
// / \ / \
// x T4 向右旋转 (y) z y
// / \ - - - - - - - -> / \ / \
// z T3 T1 T2 T3 T4
// / \
// T1 T2
private Node rightRotate(Node y) {
Node x = y.left;
Node T3 = x.right;
// 向右旋转过程
x.right = y;
y.left = T3;
// 更新height
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
return x;
}
上述两种旋转都是针对于比较简单的情况,只需要简单的经过一次旋转就可完成.
但是针对以下这两种,直接进行RR或者LL操作会使得二叉树变成非二分搜索树
所以需要先转换成为RR或者是LL的情况,在进行LL右旋转
核心代码
if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
网友评论