首页文章资源工具教程 栏目

在线工具_工作生活好帮手

打造各种简单、易用、便捷的在线工具，网友无需注册和下载安装即可使用

点击查看

Js算法之自平衡树

更新日期: 2019-07-24阅读: 2.5k标签: 树

准备知识

节点的高度和平衡因子

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

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);
    }
  };

链接: https://www.fly63.com/article/detial/4898

上一页:  在Vue项目中使用Eslint+Prettier+Stylelint下一页:  值得关注的十大高效PHP开发工具

JavaScript实现二叉排序树

Js二叉树排序实现：1初始化二叉树，2二叉树的遍历，3查找最小值，4查找最大值，5删除节点

js “指针”：数组转树

当变量指向一个对象的时候，实际指向的是存储地址，数组转树的方式：第一次遍历将数组转节点对象，存储到新的对象里，id为键值方便索引，第二次遍历根据索引插入子节点

Js实现二叉搜索树

计算机科学中最常用和讨论最多的数据结构之一是二叉搜索树。这通常是引入的第一个具有非线性插入算法的数据结构。二叉搜索树类似于双链表，每个节点包含一些数据，以及两个指向其他节点的指针；它们在这些节点彼此相关联的方式上有所不同

js 实现 list转换成tree（数组到树）

JS 将有父子关系的平行数组转换成树形数据:方法一：双重遍历，一次遍历parentId,一次遍历id == parendId;该方法应该能很容易被想到，实现起来也一步一步可以摸索出来；

vue递归组件：树形控件

在编写树形组件时遇到的问题：组件如何才能递归调用？递归组件点击事件如何传递？组件目录及数据结构；在组件模板内调用自身必须明确定义组件的name属性，并且递归调用时组件名称就是name属性

js中的AST

在计算机科学中，抽象语法树（Abstract Syntax Tree，AST），或简称语法树（Syntax tree），是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构

Js二叉树的遍历

二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

js将扁平结构数据转换为树形结构

最近项目又频繁需要对扁平结构进行树形转换，这个算法从我最早接触的时候使用了递归，到现在的单次循环完成，简单记录一下算法的演变，算是对树形算法的一个简单记录，这种类型的算法在项目中的使用挺多的

快速实现一个简单可复用可扩展的Vue树组件

大概因为平时工作项目的原因，写了很多次树形组件，越写越觉得可以写得更简单并且更具有复用性、扩展性。树组件的应用场景很多，比如一篇文章的目录、一个公司部门组织情况、思维导图等，其实都可以用树形结构来描述

JS树结构操作:查找、遍历、树结构和列表结构相互转换

经常有同学问树结构的相关操作，也写了很多次，在这里总结一下JS树形结构一些操作的实现思路，并给出了简洁易懂的代码实现。本文内容结构大概如下：

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!