AVL的基本概念和特征都是了解的，但真正动手coding的时候，发现很多细节问题是之前了解不深或没注意到的，总结一下吧。
0. 说明
这过程中找了一些文章和博客，其中对我帮助最大的一篇文章就是【参考文档】中列的“平衡二叉树的实现原理”。
因为基本原理，图例在这篇文章中都有很好的解释，我指写我的一些理解和误区，详细内容我就不做搬运工了，感兴趣的可以移步：【平衡二叉树的实现原理】
1. 了解概念
了解以下几个概念：树，二叉树，排序二叉树，平衡二叉树。
平衡二叉树旨在解决排序二叉树查询复杂度不可控的问题，即排序二叉树可能退化为链表的问题，因此平衡二叉树也叫自平衡二叉查找树。
平衡二叉树的递归定义：平衡二叉树是一棵二叉树，其可以为空，或满足如下2个性质：①左右子树深度之差的绝对值不大于1。②左右子树都是平衡二叉树。
平衡因子的概念：结点的平衡因子 = 结点的左子树深度 — 结点的右子树深度。
最低不平衡结点的概念：用A表示最低不平衡结点，则A的祖先结点可能有不平衡的，但其所有后代结点都是平衡的。 【1】
2. 自平衡实现
我们知道只在两种情况下需要对排序二叉树进行平衡化:
- 插入节点；
- 删除节点；
但本质上，都是在树发生变化时，找到最低不平衡节点，然后对以最低不平衡节点为根的子树进行适当的操作，使其平衡，从而实现整棵树的平衡。
这里有个问题，如果以最低不平衡节点为根的子树转为平衡树，那么整棵树是否就是平衡的？
这其实很好想明白的，因为我们的操作前提是：节点插入/删除，即每次只有一个节点发生改变（很重要的前提），那么平衡因子最大只能是2或者-2。当最低不平衡节点再平衡时，其平衡因子会变为1或者-1，那对于最低不平衡节点的父亲节点，也可以如此推演。
3. 部分代码
- 节点定义
public class BNode{
public int value;
public BNode left;
public BNode right;
public BNode parent;
// 省略构造函数
// 属性设置为public只是为了方便
}
- 插入节点
public void insert(int value){
BNode tNode = root;
if(tNode == null){
root = new BNode(value);
size = 1;
return;
}
BNode parent = null;
while(tNode!= null){
parent = tNode;
if(value > tNode.value){
tNode = tNode.right;
}else if(value < tNode.value){
tNode = tNode.left;
}else{
return;
}
}
// 通过简单的判断，可以过滤掉一部分不必要的平衡因子计算
// 判断依据就是，插入节点不影响树高
boolean needReblance = true;
BNode newNode = new BNode(value,parent);
//
if(value > parent.value){
parent.right = newNode;
if(parent.left != null){
needReblance = false;
}
}else{
parent.left = newNode;
if(parent.right != null){
needReblance = false;
}
}
// 对二叉树进行平衡操作
if(needReblance){
reblance(newNode);
}
size++;
}
- 平衡判断
private void reblance(BNode node){
BNode t = node;
while(t != null){
int factor = balanceFactor(t); // 计算平衡因子
if(Math.abs(factor) > 1){
// 细节：旋转操作会改变树的根，因此需要重新设置树的根节点
boolean resetRoot = t.value == root.value;
if(node.value < t.value && node.value < t.left.value){
// LL
roateRight(t);
}else if(node.value > t.value && node.value > t.right.value){
// RR
roateLeft(t);
}else if(node.value < t.value && node.value > t.left.value){
// LR
roateLeft(t.left);
roateRight(t);
}else{
// RL
roateRight(t.right);
roateLeft(t);
}
// 重新设置root节点
if(resetRoot) {
while (t.parent != null) {
t = t.parent;
}
root = t;
}
break;
}
t = t.parent;
}
}
- 中序遍历
// 中序遍历输出的即为有序元素
public List<BNode> midOrder(){
BNode node = root;
if(node == null){
return new ArrayList<>(0);
}
List<BNode> list = new ArrayList<>(size);
Stack<BNode> stack = new Stack<>();
stack.push(node);
while(stack.size()>0){
while(node != null){
if(node.left != null){
stack.push(node.left);
}
node = node.left;
}
// 写的时候写了两种，觉得下面的更好，就把这种写法注掉了。
// a: while (stack.size() > 0) {
// BNode t = stack.pop();
// list.add(t);
// if(t.right != null){
// node = t.right;
// stack.push(t.right);
// break a;
// }
// }
////
if(stack.size()!=0){
BNode t = stack.pop();
list.add(t);
if(t.right != null){
node = t.right;
stack.push(t.right);
}
}
}
return list ;
}
- 简单测试
public void test() {
BalanceTree bt = new BalanceTree();
// 这组数据，覆盖了LL,RR,RL,LR等四种case
int[] arr = new int[]{4, 3, 2, 0, 1, 5, 6, 7, 8, 11, 10, 9};
for (int i : arr) {
bt.insert(i);
}
System.out.println("finish init ..............");
List<BalanceTree.BNode> list = bt.midOrder();
for(BalanceTree.BNode n: list){
System.out.println(n.value);
}
}
4. 总结
以前常犯眼高手低的病，觉得原理清楚了就算掌握了。其实coding是一项工程性很强的事情，会有很多细节需要处理和考虑。
最近尝试把数据库/数仓相关的数据结构知识补上，后续会继续写B树，红黑树，LSM等。
【参考】
网友评论