乐趣区

JavaScript数据结构与算法十自平衡树

jiezi

前面介绍了二叉树和二叉树搜索树的创建和使用，接下来我们继续学习关于树的更多知识。
BST 存在一个问题，就是当我们多次添加节点数，有可能造成一种情况，树的一条边可能会非常深，有非常多的层，而另一条分支却只有几层。当我们需要进行添加、移除和搜索某一节点时，可能会引起一些性能问题。为了解决这类问题，我们进行自平衡树的学习。自平衡树常见有两种：AVL 树和红黑树。

自平衡树

准备知识

节点的高度和平衡因子

节点高度 ：从节点到任意子节点的彼岸的最大值。这个相对来说容易理解。那么获得节点高度的代码实现如下：

getNodeHeight(node) {if (node == null) {return -1;}
    return Math.max(this.getNodeHeight(node.left), this.getNodeHeight(node.right)) + 1;
  }

平衡因子 ：每个节点左子树高度和右子树高度的差值。该值为 0、-1、1 时则为正常值，说明该二叉树已经平衡。若果该值不是这三个值之一，则需要平衡该树。遵循计算一个节点的平衡因子并返回其值的代码如下：

const BalanceFactor = {
  UNBALANCED_RIGHT: 1,
  SLIGHTLY_UNBALANCED_RIGHT: 2,
  BALANCED: 3,
  SLIGHTLY_UNBALANCED_LEFT: 4,
  UNBALANCED_LEFT: 5
};
getBalanceFactor(node) {const heightDifference = this.getNodeHeight(node.left) - this.getNodeHeight(node.right);
    switch (heightDifference) {
      case -2:
        return BalanceFactor.UNBALANCED_RIGHT;
      case -1:
        return BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT;
      case 1:
        return BalanceFactor.SLIGHTLY_UNBALANCED_LEFT;
      case 2:
        return BalanceFactor.UNBALANCED_LEFT;
      default:
        return BalanceFactor.BALANCED;
    }
  }

AVL 树

AVL 树是一种自平衡树，添加或移除节点时，AVL 会尝试保持自平衡，也就是会可能尝试转换为完全树。接下来介绍平衡树进行自平衡的操作，AVL 旋转

AVL 旋转

在对 AVL 进行添加或者移除节点后，我们需要计算节点的高度并验证是否需要进行平衡。旋转操作分为单旋转和双旋转两种。

左 - 左 LL（向右的单旋转）
/**
   * Left left case: rotate right
   *
   *       b                           a
   *      / \                         / \
   *     a   e -> rotationLL(b) ->   c   b
   *    / \                             / \
   *   c   d                           d   e
   *
   * @param node Node<T>
   */
rotationLL(node){
    const tmp = node.right;
    node.left = tmp.right;
    tmp.right = node;
    return tmp;
}
右 - 右 RR（向左的单旋转）
/**
   * Right right case: rotate left
   *
   *     a                              b
   *    / \                            / \
   *   c   b   -> rotationRR(a) ->    a   e
   *      / \                        / \
   *     d   e                      c   d
   *
   * @param node Node<T>
   */
  rotationLL(node) {
    const tmp = node.left;
    node.left = tmp.right;
    tmp.right = node;
    return tmp;
  }
左 - 右（LR）：向右的双旋转 
/**
   * Left right case: rotate left then right
   * @param node Node<T>
   */
  rotationLR(node) {node.left = this.rotationRR(node.left);
    return this.rotationLL(node);
  }
右 - 左（RL）：向左的双旋转 
/**
   * Right left case: rotate right then left
   * @param node Node<T>
   */
  rotationRL(node) {node.right = this.rotationLL(node.right);
    return this.rotationRR(node);
  }

完成平衡操作（旋转）的学习后，我们接下来完善一下 AVL 树添加或者移除节点的操作

添加节点 

insert(key) {this.root = this.insertNode(this.root, key);
  }

  insertNode(node, key) {if (node == null) {return new Node(key);
    } if (this.compareFn(key, node.key) === Compare.LESS_THAN) {node.left = this.insertNode(node.left, key);
    } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {node.right = this.insertNode(node.right, key);
    } else {return node; // duplicated key}
    // verify if tree is balanced
    const balanceFactor = this.getBalanceFactor(node);
    if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {if (this.compareFn(key, node.left.key) === Compare.LESS_THAN) {
        // Left left case
        node = this.rotationLL(node);
      } else {
        // Left right case
        return this.rotationLR(node);
      }
    }
    if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {if (this.compareFn(key, node.right.key) === Compare.BIGGER_THAN) {
        // Right right case
        node = this.rotationRR(node);
      } else {
        // Right left case
        return this.rotationRL(node);
      }
    }
    return node;
  }

移除节点 

 removeNode(node, key) {node = super.removeNode(node, key); // {1}
    if (node == null) {return node;}
    // verify if tree is balanced
    const balanceFactor = this.getBalanceFactor(node);
    if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
      // Left left case
      if (this.getBalanceFactor(node.left) === BalanceFactor.BALANCED
        || this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT
      ) {return this.rotationLL(node);
      }
      // Left right case
      if (this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {return this.rotationLR(node.left);
      }
    }
    if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
      // Right right case
      if (this.getBalanceFactor(node.right) === BalanceFactor.BALANCED
        || this.getBalanceFactor(node.right) === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT
      ) {return this.rotationRR(node);
      }
      // Right left case
      if (this.getBalanceFactor(node.right) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {return this.rotationRL(node.right);
      }
    }
    return node;
  }
}

以上就是关于 AVL 树基础知识的学习，接下来我们介绍另一种平衡树——红黑树。
和 AVL 树一样，红黑树也是一个自平衡二叉树。红黑树本质上也是 AVL 树，但可以包含多次插入和删除。在红黑树中，每个节点都遵循以下规则：

  1. 顾名思义，每个节点不是红的就是黑的；
  2. 树的根节点就是黑的；
  3. 所有叶节点都是黑的；
  4. 如果一个节点是红的，那么他的两个子节点都是黑的
  5. 不能有两个相邻的红节点，一个红节点不能有红的父节点或子节点；
  6. 从给定的节点到他的后代节点（NULL 叶节点）的所有路径包含相同数量的黑色节点。

红黑树

创建红黑树的骨架 

const BalanceFactor = {
  UNBALANCED_RIGHT: 1,
  SLIGHTLY_UNBALANCED_RIGHT: 2,
  BALANCED: 3,
  SLIGHTLY_UNBALANCED_LEFT: 4,
  UNBALANCED_LEFT: 5
};
// 定义颜色类
const Colors = {
  RED:'red',
  BLACK:'black'
};
// 创建红黑树的节点类型
class RedBlackNode extends Node{constructor(key){super(key);
    this.key = key;
    this.color = Colors.RED;
    this.parent = null;
  }
  isRed(){return this.color === Colors.RED;}
};
class RedBlackTree extends BinarySearchTree{constructor(compareFn = defaultCompare){super(compareFn);
    this.compareFn = compareFn;
    this.root = null;
  };
}

旋转操作

向右单旋转 
 //rotationLL
  static rotationLL(node){
    const tmp = node.left;
    node.left = tmp.right;
    if(tmp.right && tmp.right.key){tmp.right.parent = node;}
    tmp.right.parent = node.parent;
    if (!node.parent){this.root = tmp;}else{if(node === node.parent.left){node.parent.left = tmp;}else{node.parent.right = tmp;}
      tmp.right = node;
      node.parent = tmp;
    }
  };
向左单旋转 
//rotationRR
  static rotationRR(node){
    const tmp = node.right;
    node.right = tmp.left;
    if (tmp.left && tmp.left.key){tmp.left.parent = node;}
    tmp.parent = node.parent;
    if (!node.parent){this.root = tmp;}else{if(node === node.parent.left){node.parent.left = tmp;}else{node.parent.right = tmp;}
    }
    tmp.left = node;
    node.parent = tmp;
  }

验证节点颜色属性 

 // 插入节点后验证红黑树的属性
  static fixTreeProperties(node){while (node && node.parent && node.parent.color.isRed() && node.color !== Colors.BLACK){
      let parent = node.parent;
      const grandParent = parent.parent;
      //case A: 父节点是左侧子节点
      if (grandParent && grandParent.left === parent){
        const uncle = grandParent.right;
        //case 1A：叔节点也是红色——只需要重新填色
        if (uncle && uncle.color === Colors.RED){
          grandParent.color = Colors.RED;
          parent.color  = Colors.BLACK;
          uncle.color = Colors.BLACK;
          node = grandParent;
        }else{
          // case 2A: 节点是右侧子节点——右旋转
          if (node === parent.left){RedBlackTree.rotationRR(parent);
            node = parent;
            parent = node.parent;
          }
          //case 3A: 子节点是左侧子节点——左旋转
          else if(node === parent.right){RedBlackTree.rotationRR(grandParent);
            parent.color = Colors.BLACK;
            grandParent.color = Colors.RED;
            node = parent;
          }
        }
      }
      //case B: 父节点是右侧子节点
      else{
        const uncle = grandParent.left;
        //case1B: 叔节点是红色——只需要重新填色
        if(uncle && uncle.color === Colors.RED){
          grandParent.color = Colors.RED;
          parent.color = Colors.BLACK;
          uncle.color = Colors.BLACK;
          node = grandParent;
        }
        //case2B: 节点是左侧子节点—右旋转
        if (node === parent.left){RedBlackTree.rotationLL(parent);
          node = parent;
          parent = node.parent;
        }
        //case3B: 节点是右侧子节点——左旋转
        else if(node === parent.right){RedBlackTree.rotationRR(grandParent);
          parent.color = Colors.BLACK;
          grandParent.color = Colors.RED;
          node = parent;
        }
      }
      this.root.color = Colors.BLACK;
    }
  }

添加新节点 

 // 向红黑树插入新节点
  insertNode(node,key){if(this.compareFn(key,node.key) === Compare.LESS_THAN){if(node.left === null){node.left = new RedBlackNode(key);
        node.left.parent = node;
        return node.left;
      }
      else{return this.insertNode(node.left,key);
      }
    }
    else if(node.right === null){node.right = new RedBlackNode(key);
      node.right.parent = node;
      return node.right;
    }
  };
  insert(key) {if (this.root === null){this.root = new RedBlackNode(key);
      this.root.color = Colors.BLACK;
    }else{const newNode = this.insertNode(this.root, key);
      RedBlackTree.fixTreeProperties(newNode);
    }
  };
退出移动版