二叉树算法大盘点( 四 ) _二叉树算法

在插入结点时，沿插入的路径更新结点的高度值
在删除结点时（delete），沿删除的路径更新结点的高度值

我们重新定义了节点之后，有了高度属性，计算平衡因子的操作就得以很简单的实现，也就是某个节点的平衡因子=左节点高度-右节点高度。
当平衡因子的绝对值大于 1 时，就会触发树的修正，或者说是再平衡操作。
树的平衡化操作
二叉树的平衡化有两大基础操作：左旋和右旋。左旋，即是逆时针旋转；右旋，即是顺时针旋转。这种旋转在整个平衡化过程中可能进行一次或多次，这两种操作都是从失去平衡的最小子树根结点开始的(即离插入结点最近且平衡因子超过1的祖结点) 。其中，右旋操作示意图如下

文章插图
所谓右旋操作，就是把上图中的 B 节点和 C 节点进行所谓“父子交换” 。在仅有这三个节点时候，是十分简单的。但是当 B 节点处存在右孩子时，事情就变得有点复杂了。我们通常的操作是：抛弃右孩子，将之和旋转后的节点 C 相连，成为节点 C 的左孩子。这样，对应的代码如下。
TreeNode treeRotateRight(TreeNode root) {TreeNode left = root.left;root.left = left.right; // 将将要被抛弃的节点连接为旋转后的 root 的左孩子left.right = root; // 调换父子关系left.height = Math.max(treeHeight(left.left), treeHeight(left.right))+1;right.height = Math.max(treeHeight(right.left), treeHeight(right.right))+1;return left;}而左旋操作示意图如下

文章插图
左旋操作和右旋操作十分类似，唯一不同的就是需要将左右互换下。我们可以认为这两种操作是对称的。代码如下：
TreeNode treeRotateLeft(TreeNode root) {TreeNode right = root.ight;root.right = right.left;right.left = root;left.height = Math.max(treeHeight(left.left), treeHeight(left.right))+1;right->height = Math.max(treeHeight(right.left), treeHeight(right.right))+1;return right;}需要平衡的四种情况

LL 型

所谓 LL 型就是上图左边那种情况，即因为在根节点的左孩子的左子树添加了新节点，导致根节点的平衡因子变为 +2，二叉树失去平衡。对于这种情况，对节点 n 右旋一次即可。

文章插图

RR 型

RR 型的情况和 LL 型完全对称。只需要对节点 n 进行一次左旋即可修正。

LR 型

文章插图
LR 就是将新的节点插入到了 n 的左孩子的右子树上导致的不平衡的情况。这时我们需要的是先对 i 进行一次左旋再对 n 进行一次右旋。

RL 型

RL 就是将新的节点插入到了 n 的右孩子的左子树上导致的不平衡的情况。这时我们需要的是先对 i 进行一次右旋再对 n 进行一次左旋。
这四种情况的判断很简单。我们根据破坏树的平衡性（平衡因子的绝对值大于 1）的节点以及其子节点的平衡因子来判断平衡化类型。
平衡化操作的实现如下：
int treeGetBalanceFactor(TreeNode root) {if(root == )return 0;elsereturn x.left.height - x.right.height;}TreeNode treeRebalance(TreeNode root) {int factor = treeGetBalanceFactor(root);if(factor > 1 && treeGetBalanceFactor(root.left) > 0) // LLreturn treeRotateRight(root);else if(factor > 1 && treeGetBalanceFactor(root.left) <= 0) { //LRroot.left = treeRotateLeft(root.left);return treeRotateRight(temp);} else if(factor < -1 && treeGetBalanceFactor(root.right) <= 0) // RRreturn treeRotateLeft(root);else if((factor < -1 && treeGetBalanceFactor(root.right) > 0) { // RLroot.right = treeRotateRight(root.right);return treeRotateLeft(root);} else { // Nothing happened.return root;}}这里推荐一个AVL树动态化的网站，可以通过动态可视化的方式理解AVL：
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
原文链接：
https://blog.csdn.net/DBC_121/article/details/104584060