CcbeanBlog
ccbean
2021-12-29
目录

数据结构与算法-二叉搜索树

# 数据结构与算法-二叉搜索树

二叉搜索树（BST，Binary Search Tree），也称为二叉排序树和二叉查找树。

# 二叉搜索树的定义

二叉搜索树是一棵二叉树，可以为空。

如果不为空，则满足以下性质：

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

二叉搜索树01

如上图所示，树二和树三符合 3 个条件属于二叉树，树一不满足条件 3 所以不是二叉树。

总结：二叉搜索树的特点就是相对较小的值总是保存在左结点上，相对较大的值总是保存在右节点上。这种特点使得二叉搜索树的查询效率非常高，这也就是二叉搜索树中“搜索”的来源。

# 应用举例

下面是一个二叉搜索树：

二叉搜索树02

若想在其中查找数据 10，只需要查找 4 次，查找效率非常高。

  • 第 1 次：将 10 与根节点 9 进行比较，由于 10 > 9，所以 10 下一步与根节点 9 的右子节点 13 比较；
  • 第 2 次：由于 10 < 13，所以 10 下一步与父节点 13 的左子节点 11 比较；
  • 第 3 次：由于 10 < 11，所以 10 下一步与父节点 11 的左子节点 10 比较；
  • 第 4 次：由于 10 = 10，最终查找到数据 10 。

二叉搜索树03

同样是 15 个数据，如果在未排序好的数组中查询数据 10，需要查询 10 次：

二叉搜索树04

如果是排序好的数组，可以通过二分查找：第一次找 8，第二次找 12，第三次找 11，第四次找10。我们发现如果把每次二分的数据拿出来以树的形式表示的话就是二叉搜索树。这就是数组二分法查找效率之所以高的原因。

# 二叉搜索树的封装

二叉搜索树有四个最基本的属性：指向节点的根（root），节点中的键（key）、左指针（right）、右指针（right）。

二叉搜索树05

所以，二叉搜索树中除了定义 root 属性外，还应定义一个节点内部类，里面包含每个节点中的 left、right 和 key 三个属性。

class Node {
  constructor (key, value) {
    this.key = key // 节点对应的key
    this.value = value
    this.left = null // 指向的左子树
    this.right = null // 指向的右子树
  }
}

# 常见操作

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

# 封装

首先创建二叉搜索树 BinarySearchTree，并添加必要属性，再进行其他方法的实现。

class BinarySearchTree {
  constructor () {
    this.root = null // 根节点
  }
}

对于BinarySearchTree来说，只需要保存根结点即可，因为其他结点都可以通过根结点找到。

# 插入节点

// 向树中插入一个新的键
insert (key) {
  const newNode = new Node(key)
  if (this.root === null) { // 插入根节点
    this.root = newNode
  } else { // 插入非根节点
    this._insertNode(this.root, newNode)
  }
}

分析：

  • 首先，根据传入的key，创建对应的Node
  • 然后，向树中插入数据需要分成两种情况：
    • 第一次插入，直接修改根结点即可。
    • 其它插入，需要进行相关的比较决定插入的位置，然后插入节点。

非根节点插入方法，如下：

/**
  * 插入非根节点到树结构中
  * @param {*} node 与插入节点比较的树节点
  * @param {*} newNode 插入节点
  */
_insertNode (node, newNode) {
  if (newNode.key < node.key) { // 准备向左子树插入节点 插入节点key小于树节点key
    if (node.left === null) {
      // 树节点左子树上没有节点
      node.left = newNode
    } else {
      // 树节点左子树上已有节点 递归
      this._insertNode(node.left, newNode)
    }
  } else { // 准备向右子树插入节点 插入节点key大于等于树节点key
    if (node.right === null) {
      // 树节点右子树上没有节点
      node.right = newNode
    } else {
      // 树节点右子树上已有节点 递归
      this._insertNode(node.right, newNode)
    }
  }
}

分析：

  • 根据比较传入的两个节点，通过递归一直查找新节点适合插入的位置，直到成功插入新节点为止。
  • 当插入节点newNode.key小于树节点node.key，向左查找:
    • 情况 1：当 node 无左子节点时，直接插入；
    • 情况 2：当 node 有左子节点时，递归调用 _insertNode()继续向下查找合适的插入位置；
  • 当插入节点newNode.key大于等于node.key，向右查找，与向左查找类似：
    • 情况 1：当 node 无右子节点时，直接插入；
    • 情况 2：当 node 有右子节点时，递归调用 _insertNode()继续向下查找合适的插入位置；

测试：

const bst = new BinarySearchTree()

// insert
bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(3)
bst.insert(9)
bst.insert(8)
bst.insert(10)
bst.insert(13)
bst.insert(12)
bst.insert(14)
bst.insert(20)
bst.insert(18)
bst.insert(25)
console.log(bst)

插入结果如下图：

二叉搜索树06

此时再新插入一个节点6

bst.insert(6)

二叉搜索树07

# 二叉树遍历

这里所说的树的遍历不仅仅针对二叉搜索树，而是适用于所有的二叉树。

遍历一棵树是指访问树的每个结点，可以对树的每个节点进行一些操作，二叉树的遍历常见的有三种方式：

  • 先序遍历
  • 中序遍历
  • 后续遍历

还有层序遍历，使用较少，可以使用队列来完成。

# 先序遍历（DLR）

遍历过程为：

  1. 访问根结点
  2. 先序遍历其左子树
  3. 先序遍历其右子树

二叉搜索树08

为什么叫先序？

树结构在先拿到根节点之后，就直接先去调用handler处理，然后再去遍历根节点的左子树直到叶子节点，然后再遍历右子树。每一个节点的子树都遵循这个规则，每次都是先handler，再优先遍历左子树，最后遍历右子树，handler在前面，所以叫先序。

另一种理解是，因为最先处理A，然后处理A的左子树，再处理A的右子树，叫先序。

第一种理解更为恰当，第二种理解更好记忆。

// 先序遍历
preOrderTraversal (handler) {
  this._preOrderTraversalNode(this.root, handler)
}

_preOrderTraversalNode (node, handler) {
  if (node !== null) {
    // 回调 handler
    handler(node.key)
    // 递归1
    // 先遍历所有的左子树
    this._preOrderTraversalNode(node.left, handler)
    // 递归2
    // 后遍历所有的右子树
    this._preOrderTraversalNode(node.right, handler)
  }
}

测试：

// 先序遍历
let preString = ""
bst.preOrderTraversal((key) => {
  preString += `${key} `
})
console.log(preString) // 11 7 5 3 6 9 8 10 15 13 12 14 20 18 25

分析：遍历树使用递归，每个节点都可能有自己的子节点，在遍历过程中，在经过节点时，会先将节点打印出来。

递归遍历从根节点开始，先遍历其左子树，再遍历其右子树。当遍历到叶子节点时，由于叶子节点不会再有子节点，那么就会结束当前节点的执行，从递归函数栈中弹出当前函数，回溯到上一层节点，再继续上层节点函数的执行。

二叉搜索树09

上面测试用例的输出在遍历过程中，如下图所示，首先输出11，再先递归其左子树，输出7、5、3，然后3没有子节点，那么递归就回溯到5，再遍历5的右子树输出6，6没有子节点，递归再次回溯到5且已经执行结束，就再回溯到7，再遍历7的右子树，输出9...... 依次类推，完成整棵树的遍历。

记：preOrderTraversalNode() 为 A()

二叉搜索树15

可以看到一共递归调用了4次方法A，分别传入11、7、5、3，最后遇到null不满足 node != null 条件结束递归1；注意此时只是执行完最开始的递归1，并没有执行递归2，并且递归1执行到null停止后要一层层地往上返回，按顺序将调用的函数压出函数调用栈。

关于函数调用栈：之前的四次递归共把4个函数压入了函数调用栈，现在递归执行完了一层层地把函数压出栈。

值得注意的是：每一层函数都只是执行完了递归1，当返回到该层函数时，比如A（3）要继续执行递归2遍历二叉搜索树中的右子节点；

在执行递归2的过程中会不断调用方法A，并依次执行递归1和递归2，以此类推直到遇到null不满足 node != null 条件为止，才停止递归并一层层返回，如此循环。同理A（5）层、A（7）层、A（11）层都要经历上述循环，直到将二叉搜索树中的节点全部遍历完为止。

二叉搜索树16

# 中序遍历（LDR）

遍历过程为:

  1. 中序遍历其左子树
  2. 访问根结点
  3. 中序遍历其右子树

二叉搜索树10

为什么叫中序？

逻辑与先序相似。

树结构在拿到根节点后，优先遍历左子树直到叶子节点，然后调用handler处理，再遍历右子树。每一个节点的子树都遵循这个规则，每次都是先遍历左子树，再handler，然后再遍历右子树，handler在中间，所以叫中序。

// 中序遍历
inOrderTraversal (handler) {
  this._inOrderTraversalNode(this.root, handler)
}

_inOrderTraversalNode (node, handler) {
  if (node !== null) {
    // 首先遍历所有的左子树
    this._inOrderTraversalNode(node.left, handler)
    // 然后回调 handler
    handler(node.key)
    // 最后遍历所有的右子树
    this._inOrderTraversalNode(node.right, handler)
  }
}

分析：先遍历左子树节点，输出，再遍历右子树节点。

上面测试用例的输出在遍历过程中，如下图所示，首先输出11，再先递归其左子树，直到叶子节点3，然后3没有子节点，输出2，那么递归就回溯到5，输出5，再遍历5的右子树，6没有子节点，输出6，递归再次回溯到5且已经执行结束，就再回溯到7，输出7，再遍历7的右子树，直到8，输出8...... 依次类推，完成整棵树的遍历。

二叉搜索树11

# 后序遍历（LRD）

遍历过程为：

  1. 后序遍历其左子树
  2. 后序遍历其右子树
  3. 访问根结点

二叉搜索树12

为什么叫后序？

逻辑同先序相似。

// 后序遍历
postOrderTraversal (handler) {
  this._postOrderTraversalNode(this.root, handler)
}
_postOrderTraversalNode (node, handler) {
  if (node !== null) {
    // 首先遍历所有的左子树
    this._postOrderTraversalNode(node.left, handler)
    // 然后遍历所有的右子树
    this._postOrderTraversalNode(node.right, handler)
    // 最后回调 handler
    handler(node.key)
  }
}

测试

// 后序遍历
let postString = ""
bst.postOrderTraversal((key) => {
  postString += `${key} `
})
console.log(postString) // 3 6 5 8 10 9 7 12 14 13 18 25 20 15 11

先遍历左子树上的节点，再遍历右子树上的节点，最后遍历根节点。

二叉搜索树13

总结：可以以遍历根（父）节点的顺序来区分三种遍历方式。比如：先序遍历先遍历根节点、中序遍历第二遍历根节点、后续遍历最后遍历根节点。

# 最大值&最小值

在二叉搜索树中查找最值非常简单，最小值在二叉搜索树的最左边，最大值在二叉搜索树的最右边。只需要一直向左/右查找就能得到最值。

二叉搜索树14

// 最小值
min () {
  let node = this.root
  // 循环找到最左子节点
  while (node.left !== null) {
    node = node.left
  }
  return node.key
}

// 最大值
max () {
  let node = this.root
  // 循环找到最右子节点
  while (node.right !== null) {
    node = node.right
  }
  return node.key
}

# 搜索特定的值

查找二叉搜索树当中的特定值效率也非常高。只需要从根节点开始将需要查找节点的 key 值与之比较，若 node.key < key 则向左查找，若 node.key > key 就向右查找，直到找到或查找到 null 为止。这里可以使用递归实现，也可以采用循环来实现。

递归实现

// 搜索值
search (key) {
  return this._searchNode(this.root, key)
}
_searchNode (node, key) {
  if (node === null) {
    return false
  }

  if (node.key > key) { // 向左子树查找
    return this._searchNode(node.left, key)
  } else if (node.key < key) { // 向右子树查找
    return this._searchNode(node.right, key)
  } else { // 相等 说明找到了key
    return true
  }
}

循环实现

// 搜索值 循环
search2 (key) {
  let node = this.root

  while (node !== null) {
    if (node.key > key) { // 向左子树查找
      node = node.left
    } else if (node.key < key) { // 向右子树查找
      node = node.right
    } else {
      return true
    }
  }

  return false
}

递归or循环：

  • 其实递归和循环之间可以相互转换
  • 大多数情况下，递归调用可以简化代码，但是也会增加空间的复杂度。
  • 循环空间复杂度较低，但是代码会相对复杂。
  • 可以根据实际的情况自行选择，不需要套死必须使用某种方式

# 删除节点

实现思路：

第一步，找到需要删除的节点，若没找到，则不需要删除。

// 删除节点
remove (key) {
  let current = this.root // 当前节点
  let parent = null // 当前节点的父节点
  let isLeftChild = true // current是否是parent的左节点

  while (current.key !== key) {
    parent = current
    if (current.key > key) {
      // key小于当前节点key 向左查找
      current = current.left
    } else {
      // 否则，key大于等于当前节点key 向右查找
      current = current.right
    }

    // 找到最后都没找到相等的节点，返回 false
    if (current === null) return false
  }

  // ...
}

第二步，删除找到的指定节点，后分3种情况：

  • 删除叶子节点；
  • 删除只有一个子节点的节点；
  • 删除有两个子节点的节点；

删除的是叶子节点：

删除的是叶子节点分两种情况：

  1. 叶子节点也是根节点

    当该叶子节点为根节点时，如下图所示，此时 current == this.root，直接通过：this.root = null，删除根节点。

    二叉搜索树17

    当该叶子节点不为根节点时也有两种情况，如下图所示

    二叉搜索树18

    若 current = 8，可以通过：parent.left = null，删除节点 8；

    若 current = 10，可以通过：parent.right = null，删除节点 10；

    // ...
if (current.left === null && current.right === null) { // 删除叶子节点
  if (this.root === current) {
    // 删除根节点
    this.root = null
  } else if (isLeftChild) {
    // 删除左叶子节点
    parent.left = null
  } else {
    // 删除右叶子节点
    parent.right = null
  }
}
// ...

  2. 删除只有一个子节点的节点，有6种情况，分别是

    • 当current存在左子节点时，即current.right == null

      • 情况1：current为根节点（current == this.root），如节点11，此时通过：this.root = current.left，删除根节点11；
      • 情况2：current为父节点parent的左子节点（isLeftChild == true），如节点5，此时通过：parent.left = current.left，删除节点5；
      • 情况3：current为父节点parent的右子节点（isLeftChild == false），如节点9，此时通过：parent.right = current.left，删除节点9；

      二叉搜索树19

    • 当current存在右子节点时，即current.left = null

      • 情况4：current为根节点（current == this.root），如节点11，此时通过：this.root = current.right，删除根节点11。
      • 情况5：current为父节点parent的左子节点（isLeftChild == true），如节点5，此时通过：parent.left = current.right，删除节点5；
      • 情况6：current为父节点parent的右子节点（isLeftChild == false），如节点9，此时通过：parent.right = current.right，删除节点9；

      二叉搜索树20

    代码如下

    // ...
else if (current.right === null) { // 删除的节点current只有一个左子节点current.left
  if (this.root === current) {
    this.root = current.left
  } else if (isLeftChild) {
    parent.left = current.left
  } else {
    parent.right = current.left
  }
} else if (current.left === null) { // 删除的节点current只有一个右子节点current.right
  if (this.root === current) {
    this.root = current.right
  } else if (isLeftChild) {
    parent.left = current.right
  } else {
    parent.right = current.right
  }
}
// ...

  3. 删除有两个子节点的节点

    这种情况十分复杂，首先依据以下二叉搜索树，讨论这样的问题：

    二叉搜索树21

    删除节点9

    在保证删除节点9后原二叉树仍为二叉搜索树的前提下，有两种方式：

    • 方式1：从节点9的左子树中选择一合适的节点替代节点9，可知节点8符合要求；
    • 方式2：从节点9的右子树中选择一合适的节点替代节点9，可知节点10符合要求；

    二叉搜索树22

    删除节点7

    在保证删除节点7后原二叉树仍为二叉搜索树的前提下，也有两种方式：

    • 方式1：从节点7的左子树中选择一合适的节点替代节点7，可知节点5符合要求；
    • 方式2：从节点7的右子树中选择一合适的节点替代节点7，可知节点8符合要求；

    二叉搜索树23

    删除节点15

    在保证删除节点15后原树二叉树仍为二叉搜索树的前提下，同样有两种方式：

    • 方式1：从节点15的左子树中选择一合适的节点替代节点15，可知节点14符合要求；
    • 方式2：从节点15的右子树中选择一合适的节点替代节点15，可知节点18符合要求；

    二叉搜索树24

    规律总结：如果要删除的节点有两个子节点，甚至子节点还有子节点，这种情况下需要从要删除节点下面的子节点中找到一个合适的节点，来替换当前的节点。

    若用current表示需要删除的节点，则合适的节点指的是：

    • current左子树中比current小一点点的节点，即current左子树中的最大值；
    • current右子树中比current大一点点的节点，即current右子树中的最小值；

    前驱&后继

    在二叉搜索树中，这两个特殊的节点有特殊的名字：

    • 比current小一点点的节点，称为current节点的前驱。比如下图中的节点5就是节点7的前驱；
    • 比current大一点点的节点，称为current节点的后继。比如下图中的节点8就是节点7的后继；

    二叉搜索树25

    前驱节点：删除节点的左子树中最大节点，即左子树中最右节点。

    后继节点：删除节点的右子树中的最小节点，即右子树中最左节点。

    所以，删除有两个子节点的节点时，关键在于找到被删除节点的前驱（后继）节点，找到被删除节点的前驱或后继节点，然后替换掉被删除的节点。

代码实现：

  • 查找需要被删除的节点current的后继时，需要在current的右子树中查找最小值，即在current的右子树中一直向左遍历查找；
  • 查找前驱时，则需要在current的左子树中查找最大值，即在current的左子树中一直向右遍历查找。

下面只讨论查找current后继的情况，查找前驱的原理相同。

// 删除节点
remove (key) {
  let current = this.root // 当前节点
  let parent = this.root // 当前节点的父节点
  let isLeftChild = true // current是否是parent的左节点

  while (current.key !== key) {
    parent = current
    if (current.key > key) {
      // key小于当前节点key 向左查找
      isLeftChild = true
      current = current.left
    } else {
      // 否则，key大于等于当前节点key 向右查找
      isLeftChild = false
      current = current.right
    }

    // 找到最后都没找到相等的节点，返回 false
    if (current === null) return false
  }

  if (current.left === null && current.right === null) { // 删除叶子节点
    if (this.root === current) {
      // 要删除的节点是根节点
      this.root = null
    } else if (isLeftChild) {
      // 要删除节点是父节点的左子节点
      parent.left = null
    } else {
      // 要删除节点是父节点的右子节点
      parent.right = null
    }
  } else if (current.right === null) { // 删除的节点current只有一个左子节点current.left
    if (this.root === current) {
      this.root = current.left
    } else if (isLeftChild) {
      parent.left = current.left
    } else {
      parent.right = current.left
    }
  } else if (current.left === null) { // 删除的节点current只有一个右子节点current.right
    if (this.root === current) {
      this.root = current.right
    } else if (isLeftChild) {
      parent.left = current.right
    } else {
      parent.right = current.right
    }
  } else { // 删除的节点current有两个子节点
    // 查找后继节点
    const successor = this.getSuccessor(current)

    // 判断是否是根节点
    if (this.root === current) {
      this.root = successor
    } else if (isLeftChild) {
      parent.left = successor
    } else {
      parent.right = successor
    }

    // 将后继的左子节点改为被删除节点的左子节点
    successor.left = current.left
  }

  return true
}

// 查找后继
getSuccessor (predelNode) {
  let successor = predelNode // 后继节点
  let current = predelNode.right // 后继节点要查找的右子树
  let successorParent = successor

  // 循环查找 current 的右子树节点
  while (current !== null) {
    successorParent = successor
    successor = current
    current = current.left
  }

  if (successor !== predelNode.right) {
    // 寻找到的后继节点不直接是要删除节点的右子节点right
    // 如图中删除15，后继是18，需要处理19
    successorParent.left = successor.right
    successor.right = predelNode.right
  }

  return successor
}

# 完整实现

class Node {
  constructor (key, value) {
    this.key = key // 节点对应的key
    this.value = value
    this.left = null // 指向的左子树
    this.right = null // 指向的右子树
  }
}

/**
 * 二叉搜索树
 */
module.exports = class BinarySearchTree {
  constructor () {
    this.root = null
  }

  // 向树中插入一个新的键
  insert (key) {
    const newNode = new Node(key)
    if (this.root === null) { // 插入根节点
      this.root = newNode
    } else { // 插入非根节点
      this._insertNode(this.root, newNode)
    }
  }

  /**
   * 插入非根节点到树结构中
   * @param {*} node 与插入节点比较的树节点
   * @param {*} newNode 插入节点
   */
  _insertNode (node, newNode) {
    if (newNode.key < node.key) { // 左子树插入节点 插入节点key小于树节点key
      if (node.left === null) {
        // 树节点左子树上没有节点
        node.left = newNode
      } else {
        // 树节点左子树上已有节点 递归
        this._insertNode(node.left, newNode)
      }
    } else { // 右子树插入节点 插入节点key大于等于树节点key
      if (node.right === null) {
        // 树节点右子树上没有节点
        node.right = newNode
      } else {
        // 树节点右子树上已有节点 递归
        this._insertNode(node.right, newNode)
      }
    }
  }

  // 先序遍历
  preOrderTraversal (handler) {
    this._preOrderTraversalNode(this.root, handler)
  }
  _preOrderTraversalNode (node, handler) {
    if (node !== null) {
      // 首先回调 handler
      handler(node.key)
      // 然后遍历所有的左子树
      this._preOrderTraversalNode(node.left, handler)
      // 最后遍历所有的右子树
      this._preOrderTraversalNode(node.right, handler)
    }
  }

  // 中序遍历
  inOrderTraversal (handler) {
    this._inOrderTraversalNode(this.root, handler)
  }
  _inOrderTraversalNode (node, handler) {
    if (node !== null) {
      // 首先遍历所有的左子树
      this._inOrderTraversalNode(node.left, handler)
      // 然后回调 handler
      handler(node.key)
      // 最后遍历所有的右子树
      this._inOrderTraversalNode(node.right, handler)
    }
  }

  // 后序遍历
  postOrderTraversal (handler) {
    this._postOrderTraversalNode(this.root, handler)
  }
  _postOrderTraversalNode (node, handler) {
    if (node !== null) {
      // 首先遍历所有的左子树
      this._postOrderTraversalNode(node.left, handler)
      // 然后遍历所有的右子树
      this._postOrderTraversalNode(node.right, handler)
      // 最后回调 handler
      handler(node.key)
    }
  }

  // 最小值
  min () {
    let node = this.root
    // 循环找到最左子节点
    while (node.left !== null) {
      node = node.left
    }
    return node.key
  }

  // 最大值
  max () {
    let node = this.root
    // 循环找到最右子节点
    while (node.right !== null) {
      node = node.right
    }
    return node.key
  }

  // 搜索值 递归
  search (key) {
    return this._searchNode(this.root, key)
  }
  _searchNode (node, key) {
    if (node === null) {
      return false
    }

    if (node.key > key) { // 向左子树查找
      return this._searchNode(node.left, key)
    } else if (node.key < key) { // 向右子树查找
      return this._searchNode(node.right, key)
    } else { // 相等 说明找到了key
      return true
    }
  }

  // 搜索值 循环
  search2 (key) {
    let node = this.root

    while (node !== null) {
      if (node.key > key) { // 向左子树查找
        node = node.left
      } else if (node.key < key) { // 向右子树查找
        node = node.right
      } else {
        return true
      }
    }

    return false
  }

  // 删除节点
  remove (key) {
    let current = this.root // 当前节点
    let parent = this.root // 当前节点的父节点
    let isLeftChild = true // current是否是parent的左节点

    while (current.key !== key) {
      parent = current
      if (current.key > key) {
        // key小于当前节点key 向左查找
        isLeftChild = true
        current = current.left
      } else {
        // 否则，key大于等于当前节点key 向右查找
        isLeftChild = false
        current = current.right
      }

      // 找到最后都没找到相等的节点，返回 false
      if (current === null) return false
    }

    if (current.left === null && current.right === null) { // 删除叶子节点
      if (this.root === current) {
        // 要删除的节点是根节点
        this.root = null
      } else if (isLeftChild) {
        // 要删除节点是父节点的左子节点
        parent.left = null
      } else {
        // 要删除节点是父节点的右子节点
        parent.right = null
      }
    } else if (current.right === null) { // 删除的节点current只有一个左子节点current.left
      if (this.root === current) {
        this.root = current.left
      } else if (isLeftChild) {
        parent.left = current.left
      } else {
        parent.right = current.left
      }
    } else if (current.left === null) { // 删除的节点current只有一个右子节点current.right
      if (this.root === current) {
        this.root = current.right
      } else if (isLeftChild) {
        parent.left = current.right
      } else {
        parent.right = current.right
      }
    } else { // 删除的节点current有两个子节点
      // 查找后继节点
      const successor = this.getSuccessor(current)

      // 判断是否是根节点
      if (this.root === current) {
        this.root = successor
      } else if (isLeftChild) {
        parent.left = successor
      } else {
        parent.right = successor
      }

      // 将后继的左子节点改为被删除节点的左子节点
      successor.left = current.left
    }

    return true
  }

  // 查找后继
  getSuccessor (predelNode) {
    let successor = predelNode // 后继节点
    let current = predelNode.right // 后继节点要查找的右子树
    let successorParent = successor

    // 循环查找 current 的右子树节点
    while (current !== null) {
      successorParent = successor
      successor = current
      current = current.left
    }

    if (successor !== predelNode.right) {
      // 寻找到的后继节点不直接是要删除节点的右子节点right
      // 如图中删除15，后继是18，需要处理19
      successorParent.left = successor.right
      successor.right = predelNode.right
    }

    return successor
  }
}

测试：

const BinarySearchTree = require('../../lib/BinarySearchTree')

const bst = new BinarySearchTree()

// insert
bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(3)
bst.insert(9)
bst.insert(8)
bst.insert(10)
bst.insert(13)
bst.insert(12)
bst.insert(14)
bst.insert(20)
bst.insert(18)
bst.insert(25)
bst.insert(6)
bst.insert(19)
console.log(bst)

// 先序遍历
let preString = ""
bst.preOrderTraversal((key) => {
  preString += `${key} `
})
console.log(preString) // 11 7 5 3 6 9 8 10 15 13 12 14 20 18 25

// 中序遍历
let inString = ""
bst.inOrderTraversal((key) => {
  inString += `${key} `
})
console.log(inString) // 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25

// 后序遍历
let postString = ""
bst.postOrderTraversal((key) => {
  postString += `${key} `
})
console.log(postString) // 3 6 5 8 10 9 7 12 14 13 18 25 20 15 11

// 最小值
console.log(bst.min())

// 最大值
console.log(bst.max())

// 搜索特定的值
console.log(bst.search(10)) // true
console.log(bst.search(13)) // true
console.log(bst.search(21)) // false

// 删除没有子节点的节点
console.log('remove(3)', bst.remove(3))
console.log('remove(8)', bst.remove(8))
console.log('remove(10)', bst.remove(10))

// 删除有一个子节点的节点
console.log('remove(5)', bst.remove(5))
console.log('remove(19)', bst.remove(19))

// 删除有两个子节点的节点
console.log('remove(9)', bst.remove(9))
console.log('remove(7)', bst.remove(7))
console.log('remove(15)', bst.remove(15))

# 平衡树

二叉搜索树的缺陷：

当插入的数据是有序的数据，就会造成二叉搜索树的深度过大。比如原二叉搜索树右 11 7 15 组成，如下图

二叉搜索树26

当插入一组有序数据：6 5 4 3 2就会变成深度过大的搜索二叉树，会严重影响二叉搜索树的性能。

二叉搜索树28

非平衡树

  • 比较好的二叉搜索树，它的数据应该是左右均匀分布的；
  • 但是插入连续数据后，二叉搜索树中的数据分布就变得不均匀了，我们称这种树为非平衡树；
  • 对于一棵平衡二叉树来说，插入/查找等操作的效率是O(logN)；
  • 而对于一棵非平衡二叉树来说，相当于编写了一个链表，查找效率变成了O(N);

树的平衡性

为了能以较快的时间O(logN)来操作一棵树，我们需要保证树总是平衡的：

  • 起码大部分是平衡的，此时的时间复杂度也是接近O(logN)的；
  • 这就要求树中每个节点左边的子孙节点的个数，应该尽可能地等于右边的子孙节点的个数；

常见的平衡树

  • AVL树：是最早的一种平衡树，它通过在每个节点多存储一个额外的数据来保持树的平衡。由于AVL树是平衡树，所以它的时间复杂度也是O(logN)。但是它的整体效率不如红黑树，开发中比较少用。
  • 红黑树：同样通过一些特性来保持树的平衡，时间复杂度也是O(logN)。进行插入/删除等操作时，性能优于AVL树，所以平衡树的应用基本都是红黑树。
编辑 (opens new window)
上次更新: 2022/01/12, 11:17:42
数据结构与算法-树
数据结构与算法-红黑树（一）

← 数据结构与算法-红黑树（一）→

最近更新
01
阅读精通正则表达式总结
09-29
02
项目搭建规范的配置
07-15
03
Vite的使用
07-03
更多文章>
Theme by Vdoing | Copyright © 2018-2023 Ccbeango