树

1. 树的相关术语

一个树结构包含一系列存在父子关系的节点。除根节点外每个节点都有一个父节点以及零个或多个子节点。
树中每个元素都叫做节点，分为内部节点和外部节点。至少有一个子节点的节点称为内部节点，没有子元素的节点称为外部节点或叶节点。
位于树顶部的节点叫做根节点。
一个节点可以有祖先和后代。
节点的一个属性是深度，节点的深度取决于它祖先节点的数量。
树的高度取决于所有节点深度的最大值。

2. 二叉树和二叉搜索树

二叉树中的节点最多只能有两个子节点，一个是左侧子节点，另一个是右侧子节点。
二叉搜索树(BST)是二叉树的一种，但规定左侧节点的值必须比父节点小，右侧节点比父节点大。

2.1 创建 BinarySearchTree 类

首先创建 Node 类表示二叉搜索树中的节点：

javascript


class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

BinarySearchTree 类：

javascript


const Compare = {
  LESS_THEN: -1,
  BIGGER_THEN: 1
}

function defaultCompare(a, b) {
  if(a === b) {
    return 0;
  } 
  return a < b ? Compare.LESS_THEN : Compare.BIGGER_THEN;
}

class BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    this.root = null;
    this.compareFn = compareFn;
  }
}

BinarySearchTree 类中的方法：

insert(key)：向树中插入一个新的键。键是树相关的术语中对节点的称呼。
search(key)：在数中查找一个键。如果节点存在，则返回 true，否则返回 false。
inOrderTraverse()：通过中序遍历方式遍历所有节点。
preOrderTraverse()：通过先序遍历的方式遍历所有节点。
postOrderTraverse()：通过后序遍历的方式遍历所有节点。
min()：返回树中最小的值/键。
max()：返回树中最大的值/键。
remove(key)：从树中移除某个键。

2.2 向二叉搜索树中插入一个键

javascript


class BinarySearchTree {
  insert(key) {
    if(this.root === null) {
      this.root = new Node(key);
    } else {
      this.insertNode(this.root, key)
    }
  }

  inserNode(node, key) {
    if(this.compareFn(key, node.key) === Compare.LESS_THEN) {
      if(node.left === null) {
        node.left = new Node(key);
      } else {
        this.insertNode(node.left, key);
      }
    } else {
      if(node.right === null) {
        node.right = new Node(key);
      } else {
        this.insertNode(node.right, key);
      }
    }
  }
}

说明

递归在树中应用较多，辅助函数 insertNode(node, key) 判断键与当前节点的大小，如果小于当前节点，则需要插入到当前节点的左边，如果左边有值，则递归判断键与左边子节点，插入右边同理。

3. 树的遍历

3.1 中序遍历

中序遍历是一种以上行顺序访问 BST 所有节点的遍历方式，也就是从最小到最大的顺序访问所有节点。中序遍历的一种应用就是对树进行排序操作。

javascript


class BinarySearchTree {
  inOrderTraverse() {
    this.inOrderTraverseNode(this.root, callback);
  }

  inOrderTraverseNode(node, callback) {
    if(node !== null) {
      this.inorderTraverseNode(node.left, callback);
      callback(node.key);
      this.inOrderTraverseNode(node.right, callback);
    }
  }
}

说明

inOrderTraverse() 方法接受一个回调函数作为参数，回调函数用来定义对每个节点的操作，这种也叫做访问者模式。

3.2 先序遍历

先序遍历是以优于后代节点的顺序访问每个节点。先序遍历的一种应用是打印一个结构化的文档。

javascript


class BinarySearchTree {
  preOrderTraverse(callback) {
    this.preOrderTraverseNode(this.root, callback);
  }

  preOrderTraverseNode(node, callback) {
    if(node !== null) {
      callback(node.key);
      this.preOrderTraverseNode(node.left, callback);
      this.preOrderTraverseNode(node.right, callback);
    }
  }
}

说明

先序遍历与中序遍历的不同点：先序遍历会先访问节点本身，然后再访问左侧子节点，最后是右侧子节点；中序遍历先访问左侧子节点，再是节点本身，最后是右侧子节点。

3.3 后序遍历

后序遍历是先访问节点的后代子节点，再访问节点本身。后序遍历的一种应用是计算目录及其子目录所有文件所占空间的大小。

javascript


class BinarySearchTree {
  postOrderTraverse(callback) {
    this.postOrderTraverseNode(this.root, callback);
  }

  postOrderTraverseNode(node, callback) { 
    if(node !== null) {
      this.postOrderTraverseNode(node.left, callback);
      this.postOrderTraverseNode(node.right, callback);
      callback(node.key);
    }
  }
}

4. 搜索树中的值

4.1 搜素最小值和最大值

在二叉搜索树中，最小值就是最左边的节点，最大值就是最右边的节点。

javascript


class BinarySearchTree {
  min() {
    return this.minNode(this.root);
  }

  minNode(node) {
    let current = node;
    while(current !== null && current.left !== null) {
      current = current.left;
    }
    return current;
  }

  max() {
    return this.maxNode(this.root);
  }

  maxNode(node) {
    let current = node;
    while(current !== null && current.right !== null) {
      current = current.right;
    }
    return current;
  }
}

4.2 搜索一个特定的值

javascript


class BinarySearchTree {
  search(key) {
    return this.searchNode(this.root, key);
  }

  searchNode(node, key) {
    if(node === null) {
      return false;
    }
    if(this.compareFn(key, node.key) === Compare.LESS_THEN) {
      return this.searchNode(node.left, key);
    } else if(this.compareFn(key, node.key) === Compare.BIGGER_THEN) {
      return this.searchNode(node.right, key);
    } else {
      return true;
    }
  } 
}

类似于二分查找，如果比当前节点小就继续查找左侧子节点，比当前节点大就查找右侧子节点。

4.3 移除一个节点

移除节点需要改变父节点的指针，因此需要返回当前节点。

javascript


class BinarySearchTree {
  remove(key) {
    this.root = this.removeNode(this.root, key);
  }

  removeNode(node, key) {
    if(node === null) {
      return null;
    }
    if(this.compareFn(key, node.key) === Compare.LESS_THEN) {
      node.left = this.removeNode(node.left, key);
      return node;
    } else if(this.compareFn(key, node.key) === Compare.BIGGER_THEN) {
      node.right = this.remove(node.right, key);
      return node;
    } else {
      // 键等于node.key
      // 第1种情况：左右子节点都为空
      if(node.left === null && node.right === null) {
        node = null;
        return node;
      } 
      // 第2种情况：左右子节点有一个为空
      if(node.left === null) {
        node = node.right;
        return node;
      } else if(node.right === null) {
        node = node.left;
        return node;
      }
      // 第3种情况：左右均有节点
      const aux = this.minNode(node.right);
      node.key = aux.key;
      node.right = this.removeNode(node.right, aux.key);
      return node;
    }
  }
}

当要移除节点有左右子节点时，找到右子节点的最小元素，移动到当前节点，以维持二叉搜索树的性质。

5. 自平衡树

二叉搜索树（BST）存在一个问题，如果添加的元素有序，树的深度可能会非常深，甚至等同于一个链表，此时添加、搜索和移除某个节点性能较差。

为了解决这个问题，设计了自平衡二叉搜索树（AVL），该树 任何一个节点左右两个子树的高度差最多为 1。

5.1 AVL 树

AVL 树是一种自平衡树。添加或移除节点时，AVL 树会尝试保持自平衡。

AVLTree 类声明：

javascript


class AVLTree extends BinarySearchTree {
  constructor(compareFn) {
    super(compareFn);
  }
}

AVL 树也是二叉搜索树，因此可以直接继承 BST。在 AVL 树中插入和移除节点和 BST 中完全相同。不同之处在于需要检验平衡因子，必要时应用自平衡。

5.2 节点的高度和平衡因子

节点的高度是 从节点到任意子节点的边的最大值。

计算节点高度：

javascript


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

在 AVL 树中，需要对每个节点计算右子树高度和左子树高度之间的差值，值应为 0、1 或 -1。如果不是这三个值，则需要平衡该 AVL 树，这些差值就是平衡因子。

计算节点平衡因子：

javascript


const BalanceFactor = {
  UNBALANCED_RIGHT: 1,
  SLIGHTLY_UNBALANCED_RIGHT: 2,
  BALANCED: 3,
  SLIGHTLY_UNBALANCED_LEFT: 4,
  UNBALANCED_LEFT: 5
}

class AVLTree {
  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_UNRALANCED_RIGHT;
      case 1:
        return BalanceFactor.UNBALANCED_LEFT;
      case 2:
        return BalanceFactor.SLIGHTLY_UNBALANCED_LEFT;
      default: 
        return BalanceFactor.BALANCED;
    }
  }
}

5.3 平衡操作 - AVL旋转

向 AVL 插入节点，可以执行单旋和双旋两种操作：

左-左（LL）：向右的单旋转。
右-右（RR）：向左的单旋转。
左-右（LR）：向右的双旋转（先 RR 旋转，再 LL 旋转）。
右-左（RL）：向左的双旋转（先 LL 旋转，再 RR 旋转）。

5.3.1 左-左：向右的单旋转

这种情况出现于节点的左侧子节点的高度大于右侧子节点的高度，并且左侧子节点也是平衡或左侧较重的。如下图所示：

向右的单旋转

假设插入节点 5，会造成树失衡，下面是平衡所执行的操作：

与平衡相关的节点有三个（X、Y、Z），将节点 X 置于节点 Y 的位置；
节点 X 的左子树不变；
将节点 Y 的左子节点置为节点 X 的右子节点；
将节点 X 的右子节点置为节点 Y。

代码表示如下：

javascript


class AVLTree {
  rotationLL(node) {
    const temp = node.left;
    node.left = temp.right;
    temp.right = node;
    return temp;
  } 
}

5.3.2 右-右：向左的单旋转

这种情况出现于节点右侧子节点的高度大于节点左侧子节点的高度，并且右侧子节点也是平衡或者右侧较重的。如下图所示：

向左的单旋转

假设插入节点 90，会造成树失衡，下面是平衡所需操作：

与平衡相关的节点有三个（X、Y、Z），将节点 X 置于节点 Y 的位置；
节点 X 的右子树不变；
将节点 Y 的右子节点置为节点 X 的左子节点；
将节点 X 的左子节点置为节点 Y。

代码表示如下：

javascript


class AVLTree {
  rotationRR(node) {
    const temp = node.right;
    node.right = temp.left;
    temp.left = node;
    return temp;
  }
}

5.3.3 左-右：向右的双旋转

这种情况出现于节点左侧子节点高度大于右侧子节点的高度，并且左侧子节点的右侧较重。如下图所示：

向右的双旋转

在这种情况下，可以先对左侧子节点进行左旋，形成“左-左”的情况，再做一次右旋来进行平衡，代码表示如下：

javascript


class AVLTree {
  rotationLR(node) {
    node.left = this.rotationRR(node.left);
    return this.rotationLL(node);
  }
}

5.3.4 右-左：向左的双旋转

这种情况出现于节点右侧子节点高度大于左侧，并且右侧子节点的左侧较重。如下图所示：

向左的双旋转

在这种情况下，可以先对右侧子节点进行右旋，形成“右-右”的情况，再做一次左旋来进行平衡，代码表示如下：

javascript


class AVLTree {
  rotationRL(node) {
    node.right = this.rotationLL(node.right);
    return this.rorationRR(node);
  }
}

5.4 向AVL树插入节点

在 AVL 树中插入节点和在 BST 中一样，不过在插入后要验证是否平衡，如果不是，就要进行必要的旋转操作。

javascript


class AVLTree {
  insert(key) {
     if(this.root == null) {
       this.root = new Node(key);
     } else {
       this.insertNode(this.root, key);
     }
  }

  insertNode(node, key) {
    if(this.compareFn(key, node.key) === Compare.LESS_THEN) {
      if(node.left == null) {
        node.left = new Node(key);
      } else {
        node.left = this.insertNode(node.left, key);
      }
    } else {
      if(node.right == null) {
        node.right = new Node(key);
      } else {
        node.right = this.insertNode(node.right, key);
      }
    }

    // 如果需要，对树进行平衡操作
    const balanceFactor = this.getBalanceFactor(node);
    if(balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
      if(this.compareFn(key, node.left.key) === Compare.LESS_THEN) {
        // 右旋
        node = this.rotationLL(node);
      } else {
        node = this.rotationLR(node)
      }
    }
    if(balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
      if(this.compare(key, node.right) === Compare.BIGGER_THEN) {
        node = this.rotationRR(node);
      } else {
        node = this.rotationRL(node);
      }
    }
  } 
}

如果向左侧子树插入节点后树不平衡了，需要将当前 key 与左侧子节点比较，如果当前 key 比左侧子节点小，形成的是“左-左”情况，需要进行 LL 旋转，否则进行 LR 旋转。

如果向右侧子树插入节点后树不平衡了，需要将当前 key 与右侧子节点比较，如果当前 key 比右侧子节点大，形成的是“右-右”情况，需要进行 RR 旋转，否则进行 RL 旋转。

5.5 从AVL树中移除节点

移除节点也与 BST 一样，只不过多了验证平衡的步骤。

javascript


class AVLTree {
  remove(key) {
    this.root = this.removeNode(this.root, key);
  }

  removeNode(node, key) {
    node = super.removeNode(node, key);
    if(node == null) {
      return node;
    }
    const balanceFactor = this.getBalanceFactor(node);
    // 跟插入时有点点区别
    if(balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
      const balanceFactorLeft = this.getBalanceFactor(node.left);
      if(balanceFactorLeft === BalanceFactor.BALANCED || 
         balanceFactor === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
        return this.rotationLL(node);
      }
      if(balanceFactorLeft === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
        return this.rotationLR(node.left)
      }
    }
    if(balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
      const balanceFactorRight = this.getBalanceFactor(node.right);
      if(balanceFactorRight === BalanceFactor.BALANCED || 
         balanceFactorRight === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
        return this.rotationRR(node);
      }
      if(balanceFactorRight === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
        return this.rotationRL(node.right);
      }
    }
    return node;
  }
}

6. 红黑树

和 AVL 树一样，红黑树也是一个自平衡二叉搜索树。
AVL 树在插入和删除时，可能会造成旋转。当插入或删除操作较多时，红黑树的性能会优于 AVL 树；插入或删除频率低时，AVL 树性能更好。

红黑树遵循以下规则：

每个节点不是红的就是黑的；
树的根节点是黑的；
所有叶节点是黑的（用 NULL 表示的节点）；
如果一个节点是红的，那么它的两个子节点是黑的；
不能有两个相邻的红节点，即一个红节点不能有红的父节点或子节点；
从给定的节点到它的后代节点的所有路径包含相同数量的黑色节点。

6.1 创建红黑树

创建 RedBlackTree 类：

javascript


class RedBlackTree extends BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    super(compareFn);
  }
}

说明

红黑树也是二叉搜索树，因此可以继承 BST 树并重写所需的方法。

6.2 向红黑树中插入节点

红黑树节点比之前多一些额外属性：节点的颜色和指向父节点的引用。

javascript


class RedBlackNode extends Node {
  constructor(key) {
    super(key);
    this.color = Colors.RED;
    this.parent = null;
  }

  isRed() {
    return this.color === Colors.RED;
  }
}

向红黑树插入节点与 BST 相同，不过在插入后需要给节点应用一种颜色，并验证是否满足红黑树的规则以及是否还是自平衡的。

javascript


class RedBlackTree {
  insert(key) {
    if(this.root == null) {
      this.root = new RedBlackTreeNode(key);
      this.root.color = Colors.BLACK;
    } else {
      // insertNode 方法返回新插入的节点
      const newNode = this.insertNode(this.root, key);
      // 验证插入后是否满足规则
      this.fixTreeProperties(newNode);
    }
  }

  insertNode(node, key) {
    if(this.compareFn(key, node.key) === Compare.LESS_THEN) {
      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 RebBlackNode(key);
        node.right.parent = node;
        return node.right;
      } else {
        return this.insertNode(node.right, key);
      }
    }
  }
}

如果树是空的，就创建一个节点作为根节点，并将节点的颜色设置为黑色；如果不是空的，就向 BST 树一样在正确的位置插入节点。

6.3 插入节点后验证红黑树属性

验证红黑树属性包括两个操作：重新填色和旋转。

向树插入节点后，新插入的节点是红色，这不会影响黑色节点的数量，但如果插入节点的父节点是红色，违反了红黑树的规则，需要重新填色。涉及父节点、祖父节点和叔节点。

javascript


class RedBlackTree {
  fixTreeProperties(node) {
    while(node && node.parent && node.parent.color.isRed()) {
      let parent = node.parent;
      const grandParent = parent.parent;
      // 情形A：父节点是左侧子节点
      if(grandParent && grandParent.left === parent) {
        const uncle = grandParent.right;
        // 情形A1：叔节点是红色，只需要重新填色
        if(uncle && uncle.color = Colors.RED) {
          grandParent.color = Colors.RED;
          uncle.color = Colors.BLACK;
          parent.color = Colors.BLACK;
          node = grandParent;
        } else {
          // 叔节点不存在或者是黑色，不能直接填色
          // 情形A2：节点是父节点的右子节点-左旋转
          if(node === parent.right) {
            this.rotationRR(parent);
            node = parent;
            parent = node.parent;
          }
          // 情形A3：节点是父节点的左子节点-右旋转
          this.rotationLL(grandParent);
          parent.color = Colors.BLACK;
          grandParent.color = Colors.RED;
          node = parent;
        }
      } else {
        // 情形B：父节点是右侧子节点
        const uncle = grandParent.left;
        // 情形B1：叔节点是红色，只需要重新填色
        if(uncle && uncle.color === Colors.RED) {
          grandParent.color = Colors.RED;
          parent.color = Colors.BLACK;
          uncle.color = Colors.BLACK;
          node = grandParent;
        } else {
          // 叔节点不存在或是黑色，不能直接填色
          // 情形B2：节点是父节点的左子节点-右旋转
          if(node === parent.left) {
            this.rotationLL(parent);
            node = parent;
            parent = node.parent;
          }
          // 情形B3：节点是父节点的右子节点-左旋转
          this.rotationRR(grandParent);
          parent.color = Colors.BLACK;
          grandParent.color = Colors.RED;
          node = parent;
        }
      }
    }
  }
}

情形 A2 如下图所示：

情形A2

情形 A3 如下图所示：

情形A3

情形 B2 如下图所示：

情形B2

情形 B3 如下图所示：

情形B3

6.4 红黑树旋转

只使用到了右-右旋转（左旋转）和左-左旋转（右旋转），逻辑和 AVL 树一样，多了更新父节点的操作。

左-左旋转（右旋转）代码如下：

javascript


class RedBlackTree {
  rotationLL(node) {
    const temp = node.left;
    node.left = temp.right;
    if(temp.right && temp.right.key) {
      temp.right.parent = node;
    }
    temp.parent = node.parent;
    if(!node.parent) {
      this.root = temp;
    } else {
      if(ndoe === node.parent.left) {
        node.parent.left = temp;
      } else {
        node.parent.right = temp;
      }
    }
    temp.right = node;
    node.parent = temp;
  }
}

右-右旋转（左旋转）代码如下：

javascript


class RedBlackTree {
  rotationRR(node) {
    const temp = node.right;
    node.right = temp.left;
    if(temp.left && temp.left.key) {
      temp.left.parent = node;
    }
    temp.parent = node.parent;
    if(!node.parent) {
      this.root = temp;
    } else {
      if(node === node.parent.left) {
        node.parent.left = temp;
      } else {
        node.parent.right = temp;
      }
    }
    temp.left = node;
    node.parent = temp;
  }
}

树 ​

1. 树的相关术语 ​

2. 二叉树和二叉搜索树 ​

2.1 创建 BinarySearchTree 类 ​

2.2 向二叉搜索树中插入一个键 ​

3. 树的遍历 ​

3.1 中序遍历 ​

3.2 先序遍历 ​

3.3 后序遍历 ​

4. 搜索树中的值 ​

4.1 搜素最小值和最大值 ​

4.2 搜索一个特定的值 ​

4.3 移除一个节点 ​

5. 自平衡树 ​

5.1 AVL 树 ​

5.2 节点的高度和平衡因子 ​

5.3 平衡操作 - AVL旋转 ​

5.3.1 左-左：向右的单旋转 ​

5.3.2 右-右：向左的单旋转 ​

5.3.3 左-右：向右的双旋转 ​

5.3.4 右-左：向左的双旋转 ​

5.4 向AVL树插入节点 ​

5.5 从AVL树中移除节点 ​

6. 红黑树 ​

6.1 创建红黑树 ​

6.2 向红黑树中插入节点 ​

6.3 插入节点后验证红黑树属性 ​

6.4 红黑树旋转 ​

树

1. 树的相关术语

2. 二叉树和二叉搜索树

2.1 创建 BinarySearchTree 类

2.2 向二叉搜索树中插入一个键

3. 树的遍历

3.1 中序遍历

3.2 先序遍历

3.3 后序遍历

4. 搜索树中的值

4.1 搜素最小值和最大值

4.2 搜索一个特定的值

4.3 移除一个节点

5. 自平衡树

5.1 AVL 树

5.2 节点的高度和平衡因子

5.3 平衡操作 - AVL旋转

5.3.1 左-左：向右的单旋转

5.3.2 右-右：向左的单旋转

5.3.3 左-右：向右的双旋转

5.3.4 右-左：向左的双旋转

5.4 向AVL树插入节点

5.5 从AVL树中移除节点

6. 红黑树

6.1 创建红黑树

6.2 向红黑树中插入节点

6.3 插入节点后验证红黑树属性

6.4 红黑树旋转