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

msup 发布于2019-08-26 10:58 / 1552人阅读

摘要：为了解决这类问题，我们进行自平衡树的学习。自平衡树常见有两种树和红黑树。自平衡树准备知识节点的高度和平衡因子节点高度从节点到任意子节点的彼岸的最大值。

前面介绍了二叉树和二叉树搜索树的创建和使用，接下来我们继续学习关于树的更多知识。
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
   */
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
   */
  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
   */
  rotationLR(node) {
    node.left = this.rotationRR(node.left);
    return this.rotationLL(node);
  }

右-左（RL）：向左的双旋转

/**
   * Right left case: rotate right then left
   * @param node Node
   */
  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树，但可以包含多次插入和删除。在红黑树中，每个节点都遵循以下规则：

顾名思义，每个节点不是红的就是黑的；

树的根节点就是黑的；

所有叶节点都是黑的；

如果一个节点是红的，那么他的两个子节点都是黑的

不能有两个相邻的红节点，一个红节点不能有红的父节点或子节点；

从给定的节点到他的后代节点（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);
    }
  };

GPU云服务器云服务器平衡树 python 平衡树平衡二叉树课程设计数据仓库与数据挖掘决策树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/106920.html

学习JavaScript数据结构与算法 — AVL树

摘要：可以看到，一次左单旋将右侧子树的高度减小了，而左侧子树的高度增加了。如图，对进行右单旋，需要左子树的右子树的高度小于等于左子树的高度，否则不能达到平衡的效果，只是把不平衡性从左边转移到了右边。 AVL树普通二叉搜索树可能出现一条分支有多层，而其他分支却只有几层的情况，如图1所示，这会导致添加、移除和搜索树具有性能问题。因此提出了自平衡二叉树的概念，AVL树（阿德尔森-维尔斯和兰迪斯树...

impig33 2019-08-21 11:31 评论0 收藏0
《学习JavaScript数据结构与算法》（第8章）（平衡二叉树代码实现）

摘要：平衡二叉树代码实现根节点插入节点树为空树不为空比较小于往左走大于往右走空树树非空自平衡树插入新节点向左走向左子树拆入新节点，且节点的值小于其左子节点时，应该进行旋转。平衡二叉树JS代码实现 var Tree = function() { var Node = function(value) { this.value = value; this....

isLishude 2019-08-26 10:37 评论0 收藏0
数据结构与算法——常用高级数据结构及其Java实现

摘要：前文数据结构与算法常用数据结构及其实现总结了基本的数据结构，类似的，本文准备总结一下一些常见的高级的数据结构及其常见算法和对应的实现以及应用场景，务求理论与实践一步到位。前文数据结构与算法——常用数据结构及其Java实现总结了基本的数据结构，类似的，本文准备总结一下一些常见的高级的数据结构及其常见算法和对应的Java实现以及应用场景，务求理论与实践一步到位。跳跃表跳跃列表是对...

itvincent 2019-08-15 14:33 评论0 收藏0
数据结构与算法:二叉树算法

摘要：因此，根据题目给出的先序遍历和中序遍历，可以画出二叉树选参考数据结构与算法描述实现二叉树算法浅谈数据结构二叉树慕课网实现二叉树算法前端树控件腾讯软件开发面试题内容衔接上一章数据结构与算法:常见排序算法内容提要什么是树　　- 为什么使用树二叉树二叉查找树红黑树Ｂ、Ｂ＋树堆伸展树树可以点击链接感受下笔者用d3.js画的tree https://codepen...

Little_XM 2019-08-22 11:09 评论0 收藏0
PHP面试：说说你理解的二叉树吧

摘要：每个节点都必须满足这个属性，这就是二叉搜索树。自平衡二叉树自平衡二叉搜索树或高度平衡二叉搜索树是一种特殊类型的二叉搜索树，它试图通过自动调整来尽量保持树的高度或层次尽可能小。自平衡或高度平衡二叉搜索树有不同的实现。理解和实现树迄今为止，我们对数据结构的探索仅触及线性部分。无论我们使用数组、链表、栈还是队列，都是线性数据结构。我们已经看到了线性数据结构操作的复杂性，大多数时候，插入和...

leejan97 2019-07-01 10:20 评论0 收藏0