数据结构 平衡树

[sailei1]

平衡树 平衡因子 该节点的左子树的深度减去它的右子树深度。 （平衡二叉树上所有节点的平衡因子可能是-1,0和1） 如果不是说明该调整

计算最重要的理解是节点深度

 var heightNode = function(node) {
       if (node === null) {
      return -1; 
  } else {
    return Math.max(heightNode(node.left),
    heightNode(node.right)) + 1;  
} 
}; 

左节点深度（层数）-右节点深度(层数) 调节平衡

右-右 向左的单旋转 需要动3个节点 Y 表示 平衡因子绝对值大于1的 X 表示 Y的右节点 Z 表示X的 右节点

1 讲节点X 代替Y的位置
2X的右节点保持不变 3 Y的右节点设置为X的左节点 4 X的左节点设置为Y

左-左 向右的单旋转

需要动3个节点 Y 表示 平衡因子绝对值大于1的 X 表示 Y的左节点 Z 表示X的 左节点

1 讲节点X 代替Y的位置
2X的左节点保持不变 3 Y的左节点设置为X的右节点 4 X的右节点设置为Y

左-右 向右的双旋转

需要动3个节点 Y 表示 平衡因子绝对值大于1的 Z 表示 Y的左节点 X 表示 Z的右节点

1 将节点X代替Y的位置 2 将Y的左节点设置为X的右节点 3将Z的右节点设置为X的左节点 4将X的右节点设置为Y 5 将X的左节点设置为Z

思路先做一次向左旋转 再做一次向右旋转

右左的 向左的旋转

需要动3个节点 Y 表示 平衡因子绝对值大于1的 Z 表示 Y的右节点 X 表示 Z的左节点 1 将节点X代替Y的位置 2 将Z的左节点设置为X的右节点 3将Y的右节点设置为X的左节点 4将X的右节点设置为Y 5 将X的左节点设置为Z

确认树需要平衡后，就需要对每种情况分别应用正确的旋转。

 //向左子树插入新节点，且节点的值小于其左子节点时，应进行LL旋转。否则，进行LR旋转。 该过程的代码如下:

if ((heightNode(node.left) - heightNode(node.right)) > 1){
if (element < node.left.key){
        node = rotationLL(node);
      } else {
        node = rotationLR(node);
      }
}
// 向右子树插入新节点，且节点的值大于其右子节点时，应进行RR旋转。否则，进行RL旋转。
if ((heightNode(node.right) - heightNode(node.left)) > 1){
if (element > node.right.key){
        node = rotationRR(node);
      } else {
        node = rotationRL(node);
      }
}