插入的时间复杂度：O(logn)

const insert = (root, value) => {
  const newNode = { val: value, left: null, right: null }
  if (!root) {
    return newNode
  let node = root
  while(node) {
    if (value > node.val) {
      if (!node.right) {
        node.right = newNode
        return
      } else {
        node = node.right
    } else {
      if (!node.left) {
        node.left = newNode
        return
      } else {
        node = node.left
  return root
二叉搜索树删除
删除节点node 流程：
叶子节点，直接删除，把node的parent对于node的指向置空
只有一个子节点child，则删除node，然后把子节点child作为新的跟节点，即把node的parent对于node的指向改为child
      1                     1                       1
     /   ==> 删除节点2 ==> /   ==> 节点3替换 ==>   /
    2                     x                       3
   /                    /                        / \
  3                    3                        4   5
 / \                 /  \
4   5               4   5
删除的节点有左节点和右节点，则删除节点node，然后node的左子树的最大值，就是node的左子树的最右子节点pNode（一路向右），然后把pNode的值作为node的新值，删除的转移成删除pNode
      15                                                 15
     / \                                                / \
    9  23                                              9  23
   / \      ===> 删除节点9 ===> 找到左子树最大值4 ==> / \      ===> 
  3 12 17                                            3  12 17
 / \                                                / \
1   4                                              1  (4)
==> 替换9变成4，然后删除4
    4   23
  3  12 17
删除的时间复杂度：O(logn)
const del = (root, value) => {
  let parent = null
  let node = root
  while(node && node.val !== value) {
    parent = node
    if (value > node.val) {
      node = node.right
    } else {
      node = node.left
  // 未找到节点
  if (!node) {
    return root
  // 左右子树都存在的节点，需要找到左子树中最右的节点
  // 将最右节点的值替换到node上，然后删除的节点则转移成了，最右节点
  if (node.left && node.right) {
    // 缓存节点，由于值处理
    const temp = node
    // 变量修改
    parent = node
    // 从node的左子树开始找
    node = node.left
    while(node.right) {
      parent = node
      node = node.right
    // 找到了，值进行替换
    temp.val = node.val
  // 因为上面找到的最右节点一定是一个右节点为空的节点，因此可以进行下面的判断
  // 对于只有一个子节点的情况，删除的时候
  // 只需要把存在的子节点替换父节点即可，此处是直接替换，不是值替换
  // 对于叶子节点的删除，只需要父节点删除对于的子节点即可，此时child = null
  const child = node.left || node.right
  // 如果是根节点，并且没有左子树或者右子树，那直接左子树/右子树
  if (!parent) {
    return child
  if (parent.left === node) {
    parent.node = child
  } else {
    parent.right = child
二叉搜索树的查找
查找流程：
从根节点开始比较，大于则往右子树查找，小于往左子树查找
查找的平均时间复杂度是树高 O(logn)
const find = (root, target) => {
  let node = root
  while(node && node.val !== target) {
    if (target > node.val) {
      node = node.right
    } else {
      node = node.left
  return !!(node && node.val === target)
最佳二叉搜索树
二叉搜索树查找的时间复杂度是树高，平均复杂度是O(logn)，但是当最大值或者最小值作为树根的时候，树的高度会变成n，远大于平均复杂度，因此尽可能的平均左右子树的节点树，可以有效的降低树高。
让中位数做树的根节点
代码实现从1～n的节点构建一个最佳二叉树
const createBestBinarySearchTree = (start, end) => {
  if (start > end) {
    return null
  const mid = Math.floor((start + end) / 2)
  const root = { val: mid, left: null, right: null }
  root.left = createBestBinarySearchTree(start, mid - 1)
  root.right = createBestBinarySearchTree(mid + 1, end)
  return root
平衡二叉搜索树
对于最佳二叉搜索树进行多次的插入和删除后，会变成非最佳二叉排序树，因为随着插入和删除，树根可能不是中位数了，相最大/最小偏移，影响查找速度，因此要动态的保持查找效率，需要利用平衡二叉树，也就是平衡二叉搜索树
  
分类：
 阅读
 
标签：
 
数据结构
 
  
 

      安装掘金浏览器插件
     
多内容聚合浏览、多引擎快捷搜索、多工具便捷提效、多模式随心畅享，你想要的，这里都有！
 前往安装
     
 

    BSOXDTDTPJHVCKFD
        前端工程师