如何使用 JavaScript 实现二叉树，二叉平衡树和红黑树

本文主要是介绍如何使用 JavaScript 实现二叉树，二叉平衡树和红黑树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

此文仅记录学习树相关的知识以及实现逻辑和代码片段。包含二叉树，二叉查找树，平衡二叉查找树（AVL树，红黑树），均已es6语法实现。查阅前默认你已经具备树相关的的基本概念，如果对某个部分感兴趣建议直接跳转到相应部分，have fun！

（图太难画了，有空补，逃 ~）

所有完整代码：Code

树的基本概念

一图胜千言，下图是一棵多叉树：

树的概念类似生活中树的树根，一生二，二...，这样子。类比月现实中的树根不会错综交织成网状，树的概念也一样。如果树的分叉相互连结，那就脱离树的范畴。如下列举后续会用到的一些概念：

节点，度 ：一个实心圆就是一个节点，向下分叉的个数就是节点的度（degree）。黑色节点表示了节点节点间的层次关系，树的旋转等操作会用到这些关系，比较重要。节点按度的个数又可以分为，叶子节点（度为0），非叶子节点（度不为零），当然一个节点的度就是该节点的一颗子树。

深度，高度，层数：这三个概念比较容易混淆，放在一起类比。深度，类比于树根从地表向下衍生的深度。高度，类比于楼房的地表绝对高度或者山峰的海拔高度。可能你也发现了，首先有一个参考标准，相对于谁的高度或深度。所以一般会计算整棵树的高度（深度），或者某个节点的高度（深度）。然后，就是计数的规则，一般情况，高度，深度都是从0开始计数，层次从1开始计数。但是，也有从层次从0计数，高度，深度从1计数的时候。

二叉树

各种二叉树：

二叉树的特点

最大度为2 ：各个节点的度最大为2，最多有两颗子树

有序树：左右子树严格有顺，即使左子树，右子树为空

二叉树的性质

非空二叉树的第 k（k>=1) 层最多有 2^(k-1) 个节点

在高为 h（h>=1)的二叉树中最多有 2^h -1 个节点

非空二叉树中，如果度为零的节点个数为 n0 ，度为 1 的节点个数为 n1 ，度为 2 的节点个数为 n2 ，则：n0 = n2 + 1

常见二叉树

真二叉树(full binary tree)：所有节点的度都为0或2

满二叉树(perfect binary tree)：最后一层节点的度都为0，其他节点的度都为2

完全二叉树(complete binary tree)：根节点到倒数第二层，是满二叉树，最后一层的叶子节点靠左对齐

完全二叉树的性质

度为1的节点只有左子树，并且要么为1要么为0

满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

节点相同的二叉树，完全二叉树的高度最小 

假设完全二叉树高度为 h (h>=1),那么至少有 2^（h -1） 个节点，至多有 2^h - 1 个节点；

若总结点数为 n , 则 2^(h-1) < n < 2^h - 1

二叉树的遍历

访问二叉树中的各个节点，一般是左右子树的访问顺序是先左子树，然后右子树；当然也可以先右子树后左子树，但是这就不是不是我们所熟知的前中后序遍历了。

前序遍历

遍历当前节点 -> 遍历当前节点的左子树 -> 遍历当前的节点的右子树

BinaryTree.prototype.preorderTraversal = function (node, printer) {
  if (node === null) return;

  printer ? printer(node.value) : this.printer(node.value);
  this.preorderTraversal(node.left, printer);
  this.preorderTraversal(node.right, printer);
};

中序遍历

遍历当前节点的左子树 -> 遍历当前节点 -> 遍历当前的节点的右子树

BinaryTree.prototype.inorderTraversal = function (node, printer) {
  if (node === null) return;

  printer ? printer(node.value) : this.inorderTraversal(node.left);
  this.printer(node.value, printer);
  this.inorderTraversal(node.right, printer);
};

后续遍历

遍历当前节点的左子树 -> 遍历当前的节点的右子树 -> 遍历当前节点

BinaryTree.prototype.postorderTraversal = function (node, printer) {
  if (node === null) return;

  this.postorderTraversal(node.left, printer);
  this.postorderTraversal(node.right, printer);
  printer ? printer(node.value) : this.printer(node.value);
};

层次遍历

从上到下，从坐到右，按层依次遍历二叉树

BinaryTree.prototype.levelOrderTraversal = function (node, printer) {
  if (node === null) return;

  const queue = [];
  queue.push(node);

  while (queue.length) {
    const currNode = queue.shift();

    printer ? printer(node.value) : this.printer(currNode.value);

    if (currNode.left) {
      queue.push(currNode.left);
    }

    if (currNode.right) {
      queue.push(currNode.right);
    }
  }
};

二叉树搜索树

二叉搜索树，又名二叉排序树，二叉查找树，故名思意可以极大的提高查找效率

特征：

任意一个节点的值，都大于左子树中所有节点的值，都小于右子树中所有节点的值

二叉搜索树中节点存储的值必须具备可比较性

实现二叉搜索树

接口设计：

export default class BinarySearchTreeNode extends BinaryTreeNode {
  /**
   * @param {*} value
   * @param {function} compareFunction
   * @return {*}
   */
  constructor(value, compareFunction) {
    super(value, compareFunction);

    this.compareFunction = compareFunction;
  }

  /**
   * @param {*} value
   * @return {BinarySearchTreeNode}
   */
  insert(value) {}

  /**
   * @param {*} value
   * @return {boolean}
   */
  find(value) {}

  /**
   * @param {*} value
   * @return {boolean | Error}
   */
  remove(value) {}

  /**
   * @param {*} value
   * @return {boolean}
   */
  contains(value) {}

  /**
   * @return {BinarySearchTreeNode}
   */
  findMin() {}
}

允许传入自定义的比较器

插入：

- 树为空，插入root节点

- 树为不为空，找到父节点，插入父节点的左边 or 右边

/**
 * @param {*} value
 * @return {BinarySearchTreeNode}
 */
insert(value) {
  // curr.node.value === null
  if (this.nodeValueComparator.equal(this.value, null)) {
    this.value = value;
    return this;
  }

  // curr.node.value < value
  if (this.nodeValueComparator.lessThan(this.value, value)) {
    // curr.node !== null
    if (this.right) {
      return this.right.insert(value);
    }

    // curr.node.right === null
    const newNode = new BinarySearchTreeNode(value, this.compareFunction);
    this.setRight(newNode);

    return newNode;
  }

  // curr.node.value > value
  if (this.nodeValueComparator.greaterThan(this.value, value)) {
    // curr.node.left !== null
    if (this.left) {
      return this.left.insert(value);
    }

    // curr.node.left === null
    const newNode = new BinarySearchTreeNode(value, this.compareFunction);
    this.setLeft(newNode);

    return newNode;
  }

  // curr.node.value === value
  return this;
}

删除：

- 删除的是叶子节点 

    -> 找到父节点，将父节点的左子树 or 右子树 设为null 
    
    -> 如果没有父节点，则是根节点，将root设置为null

- 删除的是度为1的节点 
    
    -> 找到父节点，用子树替代当前位置

    -> 如果没有父节点，则是根节点，将root指向子树

- 删除的是度为2的节点

    -> 找到父节点，找到前驱或者后继节点，替代当前节点，然后删除前驱或后继

    -> 如果没有父节点，则是根节点，特殊处理

- 以上删除的节点可能是根节点

/**
 * @param {*} value
 * @return {boolean | Error}
 */
remove(value) {
  const nodeToRemove = this.find(value)

  if (!nodeToRemove) {
    throw new Error('item not exit in this tree')
  }

  const parent = nodeToRemove.parent;

  // degree === 0 node is a leaf and has no child
  if (!nodeToRemove.left && !nodeToRemove.right) {
    if (parent) {
      parent.removeChild(nodeToRemove)
    } else {
      nodeToRemove.setValue(null)
    }
  }
  // degree === 2 has tew children
  else if (nodeToRemove.left && nodeToRemove.right) {
    const nextBiggerNode = nodeToRemove.right.findMin();

    if (!this.nodeComparator.equal(nextBiggerNode, nodeToRemove.right)) {
      this.remove(nextBiggerNode.value);
      nodeToRemove.setValue(nextBiggerNode.value)
    } else {
      nodeToRemove.setValue(nodeToRemove.right.value);
      nodeToRemove.setRight(nodeToRemove.right.right);
    }
  }
  // degree === 1 has only one child
  else {
    const childNode = nodeToRemove.left || nodeToRemove.right;

    if (parent) {
      parent.replaceChild(nodeToRemove, childNode)
      // childNode.parent = parent
    } else {
      BinaryTreeNode.coypNode(childNode, nodeToRemove)
    }
  }

  nodeToRemove.parent = null;

  return true;
}

前驱或后继是指中序遍历中当前节点的前一个或后一个节点

其他接口相对容易，不再概述

平衡二叉搜索树

二叉搜索树在极端情况下添加和删除会退化为链表。

如何平衡二叉搜索树呢？只有在添加或删除后想办法降低树的高度。

下面一起看看AVL树和红黑树是如何实现的。

AVL树

引入平衡因子（balance factor） ：某个节点的左右子树的高度差

特点：

每个节点的平衡因子只能是：1 0 -1；绝对值超过1则失衡

实现AVL树

接口设计：

export default class AvlTree extends BinarySearchTree {
  /**
   * @param {*} value
   */
  insert(value) { }

  /**
   * @param {*} value
   */
  remove(value) {}

  /**
   * @param {BinarySearchTreeNode} node
   */
  balance(node) {}

  /**
   * @param {BinarySearchTreeNode} rootNode
   */
  rotateLeftLeft(rootNode) {}

  /**
   * @param {BinarySearchTreeNode} rootNode
   */
  rotateLeftRight(rootNode) {}

  /**
   * @param {BinarySearchTreeNode} rootNode
   */
  rotateRightRight(rootNode) { }

  /**
   * @param {BinarySearchTreeNode} rootNode
   */
  rotateRightLeft(rootNode) {}
}

添加：

- 当前节点不会失衡，父节点，祖先节点可能会失衡

- 失衡会像上逐级传播

insert

/**
 * @param {*} value
 */
insert(value) {
  // BinarySearchTree.insert
  super.insert(value);

  // move up from current node to root to check balance factors
  let currentNode = this.root.find(value);
  while (currentNode) {
    this.balance(currentNode);
    currentNode = currentNode.parent;
  }
}

平衡

通过平衡因子判断节点插入位置的情况

balance

/**
 * @param {BinarySearchTreeNode} node
 */
balance(node) {
  // balance factor is not ok
  if (node.balanceFactor > 1) {
    // left rotate
    if (node.left.balanceFactor > 0) {
      // left-left rotate
      this.rotateLeftLeft(node);
    } else if (node.left.balanceFactor < 0) {
      // left-right rotate
      this.rotateLeftRight(node);
    }
  } else if (node.balanceFactor < -1) {
    // right rotate
    if (node.right.balanceFactor < 0) {
      // right-right rotate
      this.rotateRightRight(node);
    } else if (node.right.balanceFactor > 0) {
      // right-left rotate
      this.rotateRightLeft(node);
    }
  }
}

通过层次和有序判断节点插入位置的情况

balance2

/**
 * @param {*} grand
 * @returns {*}
 */
balance2(grand) {
  const parent = grand.tallerChild();
  const child = parent.tallerChild();

  if (parent.isLeftChild(grand)) {
    // left
    if (child.isLeftChild(parent)) {
      // left-left
      rotateRight(grand);
    } else {
      // left-right
      rotateLeft(parent);
      rotateRight(grand);
    }
  } else {
    // right
    if (child.isRightChild(parent)) {
      // right-right
      rotateLeft(grand);
    } else {
      // right-left
      rotateRight(parent);
      rotateLeft(grand);
    }
  }
}

通过层次和有序判断节点插入位置，4种情况统一处理

balance3

/**
 * @param {*} grand
 * @returns {*}
 */
balance3(grand) {
  const parent = grand.tallerChild();
  const child = parent.tallerChild();

  if (parent.isLeftChild(grand)) {
    // left
    if (child.isLeftChild(parent)) {
      // left-left
      rotate(grand, node, node.right, parent, parent.right, grand);
    } else {
      // left-right
      rotate(grand, parent, node.left, node, node.right, grand);
    }
  } else {
    // right
    if (child.isRightChild(parent)) {
      // right-right
      rotate(grand, grand, parent.left, parent, node.left, node);
    } else {
      // right-left
      rotate(grand, grand, node.left, node, node.right, parent);
    }
  }
}

left-left-右旋-单旋

1. grandparent.left = parent.right

2. parent.parent = grandparent.parent

3. parent.right = grandparent

- 第1步和第2步可以交换

rotateLeftLeft

/**
  * @param {BinarySearchTreeNode} rootNode
  */
rotateLeftLeft(rootNode) {
  const leftNode = rootNode.left;
  rootNode.setLeft(null);

  if (rootNode.parent) {
    rootNode.parent.setLeft(leftNode);
  } else if (rootNode === this.root) {
    this.root = leftNode;
  }

  if (leftNode.right) {
    rootNode.setLeft(leftNode.right);
  }

  leftNode.setRight(rootNode);
}

left-right-左旋-右旋-双旋

1.先对parent节点左旋,变化为rotateLeftLeft情形

2.处理rotateLeftLeft情形

rotateLeftRight

/**
 *
 * @param {BinarySearchTreeNode} rootNode
 */
rotateLeftRight(rootNode) {
  const leftNode = rootNode.left;
  rootNode.setLeft(null);

  const leftRightNode = leftNode.right;
  leftNode.setRight(null);

  if (leftRightNode.left) {
    leftNode.setRight(leftRightNode.left);
    leftRightNode.setLeft(null);
  }

  rootNode.setLeft(leftRightNode);

  leftRightNode.setLeft(leftNode);

  this.rotateLeftLeft(rootNode);
}

right-right-左旋-单旋

1. grandparent.right = parent.left

2. parent.parent = grandparent.parent

3. parent.left = grandparent

- 第1步和第2步可以交换

rotateRightRight

/**
 * @param {BinarySearchTreeNode} rootNode
 */
rotateRightRight(rootNode) {
  const rightNode = rootNode.right;
  rootNode.setRight(null);

  if (rootNode.parent) {
    rootNode.parent.setRight(rightNode);
  } else if (rootNode === this.root) {
    this.root = rightNode;
  }

  if (rightNode.left) {
    rootNode.setRight(rightNode.left);
  }

  rightNode.setLeft(rootNode);
}

right-left-右旋-左旋-双旋

1.先对parent节点右旋,变化为rotateRightRight情形

2.处理rotateRightRight情形

rotateRightLeft

/**
 * @param {BinarySearchTreeNode} rootNode
 */
rotateRightLeft(rootNode) {
  const rightNode = rootNode.right;
  rootNode.setRight(null);

  const rightLeftNode = rightNode.left;
  rightNode.setLeft(null);

  if (rightLeftNode.right) {
    rightNode.setLeft(rightLeftNode.right);
    rightLeftNode.setRight(null);
  }

  rootNode.setRight(rightLeftNode);

  rightLeftNode.setRight(rightNode);

  this.rotateRightRight(rootNode);
}

左旋

- 和retateLeftLeft情况一致

1. grandparent.left = parent.right

2. parent.parent = grandparent.parent

3. parent.right = grandparent

- 第1步和第2步可以交换

rotateLeft

/**
 * @param {*} rootNode
 */
rotateLeft(rootNode) {
  const rightNode = rootNode.right;
  rootNode.setRight(null);

  if (rootNode.parent) {
    rootNode.parent.setRight(rightNode);
  } else if (rootNode === this.root) {
    this.root = rightNode;
  }

  if (rightNode.left) {
    rootNode.setRight(rightNode.left);
  }

  rightNode.setLeft(rootNode);
}

右旋

- 和rotateRightRight情况一直

1. grandparent.right = parent.left

2. parent.parent = grandparent.parent

3. parent.left = grandparent

- 第1步和第2步可以交换

rotateRight

/**
 * @param {*} rootNode
 */
rotateRight(rootNode) {
  const leftNode = rootNode.left;
  rootNode.setLeft(null);

  if (rootNode.parent) {
    rootNode.parent.setLeft(leftNode);
  } else if (rootNode === this.root) {
    this.root = leftNode;
  }

  if (leftNode.right) {
    rootNode.setLeft(leftNode.right);
  }

  leftNode.setRight(rootNode);
}

统一处理

/**
 * @param {*} r
 * @param {*} a
 * @param {*} b
 * @param {*} c
 * @param {*} d
 * @param {*} e
 * @param {*} f
 */
rotate(r, a, b, c, d, e, f) {
  // d
  d.parent = r.parent;
  if (r.isLeftChild()) {
    r.parent.setLeft(d);
  } else if (r.isRightChild()) {
    r.parent.setRight(d);
  } else {
    this.root = d;
  }

  //b-c
  b.setRight(c);

  // e-f
  f.setLeft(e);

  // b-d-f
  d.setLeft(b);
  d.setRight(f);
}

旋转：

  - 必定有旋转中心，右旋顺时针旋转，左旋逆时针旋转

  - 旋转中心的节点上升，绕中心旋转的节点下沉

引用的维护:

  - grandparent的父节点更新为parent节点的父节点

  - 右旋必定有节点成为旋转中心的右子树

  - 左旋必定有节点成为旋转中心的左子树

  - 注意判空

删除：

删除可能导致父节点或者祖先节点失衡，只有一个节点失衡

remove

/**
 * @param {*} value
 */
remove(value) {
  // BinarySearchTree.remove
  super.remove(value);

  //
  this.balance(this.root);
}

B树

一种多路搜索树

特点：

- 一个节点，可以存储超过2个元素，可以超过连个节点

- 具有二叉搜索树的性质

- 平衡

m阶B树的性质

m阶：节点的度最大为m

- 1 <= 根节点的元素个数 <= m-1

- ceil(m/2) - 1 <= 非根节点的元素个数 <= m-1

- 子树（度）的个数 = 节点元素个数 + 1

  - 2 <= 根节点子树的个数 <= m

  - ceil(m/2) <= 非根节点子树的个数 <= m

- B树和二叉搜索树在逻辑上是等价的

- 多代（层级）节点合并就可以得到一个B树节点，反之，B树节点也可以分解

  - 2代二叉搜索树合并的节点，最多具有4个子树（4阶B树）

  - 3代二叉搜索树合并的节点，最多具有8个子树（8阶B树）

  - n代二叉搜索树合并的节点，最多具有2^n个子树（2^n阶B树）

B树的具备二叉搜索树的性质，类似二分搜索的意思

添加

- 1.B树中查找将要添加的位置，必定是叶子节点

- 2.添加可能导致当前叶子节点的元素个数 等于 B树的阶树 m 导致 上溢

- 3.解决上溢：

  - 假设上溢节点为中间的某个节点k

  - 将k元素和父节点合并，并且将[0,k)和(k,m-1]位置的元素分裂为2个子节点

  - 向上合并肯可能导致父节点上溢，进而传播到根节点 -> 高度+1

删除

- 1.叶子节点,直接删除。元素个数低于最低限制 ceil(m/2) - 1 ,可能导致 下溢
  
  -下溢解决：

    - 此时节点元素个数必定等于ceil(m/2) - 2

    - 如果相邻兄弟节点有至少ceil(m/2)个元素，可以借一个元素 => 右旋

      - 兄弟节点的一个元素上升到父节点，父节点的一个元素下沉到当前节点
    
    - 如果相邻兄弟节点只有ceil(m/2) - 1个元素，则合并

      - 将父节点的元素挪下来和左右子树合并

      - 合并后的元素个数 = ceil(m/2) - 1 + ceil(m/2) - 2 + 1 = 2ceil(m/2) - 2 < m - 1

      - 向下合并可能导致父节点下溢，进而传播到根节点 -> 高度 - 1

- 2.非叶子节点，找到前驱或后继，替换待删除的元素，然后再删掉前驱或后继节点

  - 非叶子节点的前驱或后继必定在叶子节点中

  - 所以，删除的节点始终是叶子节点，同叶子节点的删除

4阶B树

后续的红黑树就等价于4阶B树（2，3，4树）

红黑树

引入染色 ：节点非黑即红，满足红黑树的性质则能自平衡

红黑树5大性质：

 1.节点是要么是红色要么是黑色

 2.根节点必是黑色

 3.叶子节点都是黑色
 
    - 按照空节点算

 4.红色节点的子节点都是黑色

    - 不能出现连续的红色节点（被黑色包裹）

    - 存在连续的黑色节点节点

 5.从任意节点到叶子节点的所有路径都包含相同数目的黑色节点

等价变换：

- 红黑树和4阶B树（2，3，4树）等价

  - 黑色节点和它的红色子节点融合在一起形成一个4阶B树节点

  - 红黑树的黑色节点个数和等价的4阶B树节点个数相等

实现红黑树

添加

4阶B树的元素个数（1 <= x <= 3)，新元素的添加必定添加到叶子节点中（参考二叉搜索）；

如果添加的是黑色节点，不能很好的满足红黑树的性质。如果添加的是红色节点能满足5条中的4条，因此添加新节点时默认染成红色，添加后调整。

以下列举所有的可能被添加节点(等价于4阶B树节点)的情况

(1)r<-b->r   (2)b->r  (3)r<-b  (4)b

第一种情况：

(2)b的左，(3)b的右，(4)b的左右

这四种情况，直接添加，满足红黑树的性质，不做处理

第二种情况：

(2)b右边r的左右，（3）b左边r的左右

这四种情况，根据uncle节点是否是红色节点，不是红色，做LL/LR，RR/RL单旋或双旋操作

LL/RR

1.parent右旋/左旋

2.parent和grandparent交换节点颜色

LR/RL

1.先对parent左旋/右旋 变换为 LL/RR情况

2.针对新的LL/RR处理

插入的新节点和parent，grandparent合并为B树的一个节点

第三种情况：

(1)b左边r的左右，(1)b右边r的左右

这四种情况，根据uncle节点是否是红色节点，是红色，如果和将grandparent（黑色）合并为一个B树节点则会发生上溢

- 上溢解决

- 1.将uncle和parent染成黑色（分裂成B中的两个节点）

- 2.将grandparent染成红色当作新的待插入的节点，向上合并

- 3.插入新节点grandparent（递归），可能导致上溢向上传播直至根节点

实现：

/**
 * @param {*} value
 * @returns {*}
 */
insert(value) {
  const insertedNode = super.insert(value);

  if (this.nodeComparator.equal(insertedNode, this.root)) {
    // make root always be black
    this.makeNodeBlack(insertedNode);
  } else {
    // make all newly inserted nodes to be red
    this.makeNodeRed(insertedNode);
  }

  // check all conditions and balance the nodes
  this.balance(insertedNode);

  return insertedNode;
}

/**
 * @param {*} node
 * @return {*}
 */
balance(node) {
  if (this.nodeComparator.equal(this.root, node)) {
    return;
  }

  if (this.isNodeBlack(node.parent)) {
    return;
  }

  const grandParent = node.parent.parent;

  if (node.uncle && this.isNodeRed(node.uncle)) {
    this.makeNodeBlack(node.uncle);
    this.makeNodeBlack(node.parent);

    if (!this.nodeComparator.equal(this.root, grandParent)) {
      this.makeNodeRed(grandParent);
    } else {
      return;
    }

    this.balance(grandParent);
  } else if (!node.uncle || this.isNodeBlack(node.uncle)) {
    if (grandParent) {
      let newGrandParent;

      if (this.nodeComparator.equal(grandParent.left, node.parent)) {
        // left rotate
        if (this.nodeComparator.equal(node.parent.left, node)) {
          // left-left rotate
          newGrandParent = this.leftLeftRotate(grandParent);
        } else {
          // left-right rotate
          newGrandParent = this.leftRightRotate(grandParent);
        }
      } else {
        // right rotate
        if (this.nodeComparator.equal(node.parent.right, node)) {
          // right-right rotate
          newGrandParent = this.rightRightRotate(grandParent);
        } else {
          // right-left rotate
          newGrandParent = this.rightLeftRotate(grandParent);
        }
      }

      if (newGrandParent && newGrandParent.parent === null) {
        this.root = newGrandParent;

        this.makeNodeBlack(this.root);
      }

      this.balance(newGrandParent);
    }
  }
}

删除：
todo

参考

• https://github.com/trekhleb/javascript-algorithms

这篇关于如何使用 JavaScript 实现二叉树，二叉平衡树和红黑树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！