4 平衡二叉树

引言

因为按照不同的插入顺序，将会导致不同深度，和不同的平均查找长度ASL

定义

1. 平衡因子（Balance Factor）:BF(T) = hL - hR
2. 平衡二叉树（Balanced Binary Tree）（AVL树）
   任一节点的左右子树高度的绝对值不超过1， |BF(T)|<=1

平衡二叉树的调整

1. RR旋转
   麻烦节点在发现者右子树的右子树，需要进行RR旋转
2. LL旋转
   麻烦节点在发现者左子树的左子树，需要进行LL旋转
3. LR旋转
   麻烦节点在发现者左子树的右子树，需要进行LR旋转
4. RL旋转
   麻烦节点在发现者右子树的左子树，需要进行RL旋转

我的思考

需要如下几个函数来支撑实现平衡二叉树的插入元素

1. 求当前节点的左右子树的高度，通过左右高度值计算平衡因子。
2. 确定平衡因子> 1对应的节点，判别需要采用的旋转调整方式
3. 按照对应的旋转方式重新排列二叉树