树结构

树（tree）是n（n >= 0）个节点构成的有限集合。当n = 0时，称为空树
对于任意一颗非空树，具有以下性质

• 有一个称为“根（Root）”的特殊节点，用r表示
• 其余节点可分为m（m > 0）个互不交的有限集合，其中每个集合又是一棵树，称为原来树的“子树（SubTree）”

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-P50MJTL0-1618314971670)(https://gitee.com/jq96m/imgbed/raw/master/img/%E6%A0%91.svg)]

---

二叉树

树中每个节点最多只能有两个子节点，这样的树称为“二叉树”。几乎所有的树都可以表示成二叉树形式
二叉树中有几个比较重要的特特性

• 二叉树第i层的最大节点数为：2i-1 (i>=1)
• 深度为k的二叉树最大节点数为：2k-1 (k>=1)
• 对于非空二叉树，若n0表示叶节点个数，n2表示度为2的非叶节点个数，那么两者满足关系n0 = n2+1

二叉搜索树

• 非空左子树的所有键值小于其根节点的键值
• 非空右子树的所有键值大于其根节点的键值
• 左右子树本身也都是二叉搜索树

二叉搜索树的封装

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

class BinarySearchTree {
  constructor() {
    this.root = null
  }
  // 插入一个新的键
  insert(key) {
    const node = new Node(key)
    if (this.root === null) {
      this.root = node
    } else {
      recursion(this.root, node)
    }
    function recursion(node, newNode) {
      if (newNode.key < node.key) {
        if (node.left === null) {
          node.left = newNode
        } else {
          recursion(node.left, newNode)
        }
      } else {
        if (node.right === null) {
          node.right = newNode
        } else {
          recursion(node.right, newNode)
        }
      }
    }
  }
  // 先序遍历所有节点
  prevOrderTraversal(handler) {
    recursion(this.root, handler)
    function recursion(node, handler) {
      if (node != null) {
        handler(node.key)
        recursion(node.left, handler)
        recursion(node.right, handler)
      }
    }
  }
  // 中序遍历所有节点
  middleOrderTraversal(handler) {
    recursion(this.root, handler)
    function recursion(node, handler) {
      if (node != null) {
        recursion(node.left, handler)
        handler(node.key)
        recursion(node.right, handler)
      }
    }
  }
  // 后续遍历所有节点
  postOrderTraversal(handler) {
    recursion(this.root, handler)
    function recursion(node, handler) {
      if (node != null) {
        recursion(node.left, handler)
        recursion(node.right, handler)
        handler(node.key)
      }
    }
  }
  // 返回最小值/键
  min() {
    let current = this.root
    while (current.left) {
      current = current.left
    }
    return current.key
  }
  // 返回最大值/键
  max() {
    let current = this.root
    while (current.right) {
      current = current.right
    }
    return current.key
  }
  // 在树中查找键，返回true或false
  search(key) {
    let current = this.root
    while (current) {
      if (key < current.key) {
        current = current.left
      } else if (key > current.right) {
        current = current.right
      } else {
        return true
      }
    }
    return false
  }
  // 移除某个键
  remove(key) {
    let parent = null
    let current = this.root
    let isLeft = true
    while (current.key !== key) {
      parent = current
      if (key < current.key) {
        current = current.left
      } else {
        isLeft = false
        current = current.right
      }
      if (current === null) return false
    }
    // 1. 删除的节点是叶子节点
    if (current.left === null && current.right === null) {
      if (current === this.root) {
        this.root = null
      } else if (isLeft) {
        parent.left = null
      } else {
        parent.right = null
      }
    }
    // 2. 删除的节点有一个子节点
    else if (current.right === null) {
      if (current === this.root) {
        this.root = current.left
      } else if (isLeft) {
        parent.left = current.left
      } else {
        parent.right = current.left
      }
    } else if (current.left === null) {
      if (current === this.root) {
        this.root = current.right
      } else if (isLeft) {
        parent.left = current.right
      } else {
        parent.right = current.right
      }
    }
    // 3. 删除的节点有两个子节点
    else {
      let successer = this.getSuccessor(current)
      if (this.root === current) {
        this.root = successer
      } else if (isLeft) {
        parent.left = successer
      } else {
        parent.right = successer
      }
      successer.left = current.left
    }
    return true
  }
  // 获取后继（即右树中的最小值），若使用前驱就是 左数中的最大值
  getSuccessor(delNode) {
    let successerParent = delNode
    let successer = delNode
    let current = delNode.right
    while (current) {
      successerParent = successer
      successer = current
      current = current.left
    }
    // 若后继节点不是删除节点的右节点
    if (successer !== delNode.right) {
      successerParent.left = successer.right
      successer.right = delNode.right
    }
    return successer
  }
}

红黑树

红黑树除二叉树的规则外还有以下特点

1. 节点是黑色或红色
2. 根节点是黑色
3. 叶子节点是黑色的空节点（NIL节点）
4. 红色节点的子节点都是黑色（从根节点到叶子节点的路径中不会出现两个连续的红色节点）
5. 从任意节点到其每个叶子的所有路径都包含相同数目的黑色节点

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RLNiH04m-1618314971674)(https://gitee.com/jq96m/imgbed/raw/master/img/%E7%BA%A2%E9%BB%91%E6%A0%91.svg)]

有了上面性值的约束，可以保证：最长路径不超过最短路径的两倍

红黑树的旋转

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-v9RGHUax-1618314971677)(https://gitee.com/jq96m/imgbed/raw/master/img/%E7%BA%A2%E9%BB%91%E6%A0%91%E6%97%8B%E8%BD%AC.svg)]### 插入操作
设插入的节点为N，其父节点为P，祖父节点为G，父节点的兄弟节点为U。有以下五种情况

情况一

新节点N位于树根上，没有父节点
这样直接将颜色变为黑色即可

情况二

新节点的父节点P是黑色
不需要变化

情况三

P为红色，U也为红色
将其P、U、G变为另一种颜色[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FemZkc5D-1618314971680)(https://gitee.com/jq96m/imgbed/raw/master/img/%E7%BA%A2%E9%BB%91%E6%A0%91%E6%8F%92%E5%85%A53.svg)]
若其祖父节点的父节点为红色，这样便违反了红黑树性值。可以使用递归调整颜色

情况四

P红、U黑、G黑，N是左儿子
将G变为红色、P变为黑色，然后右旋转[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lK5zEfTv-1618314971682)(https://gitee.com/jq96m/imgbed/raw/master/img/%E7%BA%A2%E9%BB%91%E6%A0%91%E6%8F%92%E5%85%A54.svg)]

情况五

P红、U黑、G黑，N是右儿子
以P为根进行左旋转 → 以祖父为根进行右旋转，并改变颜色[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-K1uQNWOL-1618314971684)(https://gitee.com/jq96m/imgbed/raw/master/img/%E7%BA%A2%E9%BB%91%E6%A0%91%E6%8F%92%E5%85%A55.svg)]