二叉搜索树（Binary Search Tree）
大约 6 分钟
二叉搜索树（Binary Search Tree）
在计算机科学中，二叉搜索树（Binary Search Tree，BST），有时也被称为有序或排序二叉树，是一种特殊的容器数据结构，用于在内存中存储“项”（例如数字、名称等）。它们允许快速查找、添加和删除项，并可用于实现动态集合或查找表，通过键（例如通过名称查找人的电话号码）来查找项。
二叉搜索树保持其键的有序性，以便查找和其他操作可以利用二分查找的原理：在树中从根到叶子进行遍历，通过与树节点中存储的键进行比较，并根据比较结果决定是继续在左子树还是右子树中查找。平均而言，这意味着每次比较可以跳过树的大约一半的节点，因此每次查找、插入或删除的时间与存储在树中的项的数量的对数成比例。这比在（未排序的）数组中按键查找项所需的线性时间要好得多，但比哈希表的相应操作要慢。
一个大小为9、深度为3的二叉搜索树，根节点为8。 未绘制叶子节点。
基本操作的伪代码
插入
insert(value) 前置条件：value已通过自定义类型检查，类型为T 后置条件：value已放置在树的正确位置 如果 root = ø root ← 节点(value) 否则 insertNode(root, value) 结束如果 结束插入 insertNode(current, value) 前置条件：current为起始节点 后置条件：value已放置在树的正确位置 如果 value < current.value 如果 current.left = ø current.left ← 节点(value) 否则 InsertNode(current.left, value) 结束如果 否则 如果 current.right = ø current.right ← 节点(value) 否则 InsertNode(current.right, value) 结束如果 结束如果 结束insertNode 查找
contains(root, value) 前置条件：root为树的根节点，value为要查找的值 后置条件：确定value是否被找到 如果 root = ø 返回 false 结束如果 如果 root.value = value 返回 true 否则，如果 value < root.value 返回 contains(root.left, value) 否则 返回 contains(root.right, value) 结束如果 结束contains 删除
remove(value) 前置条件：value为要删除的节点的值，root为BST的根节点，count为BST中的项数 后置条件：如果找到并删除了值为value的节点，则返回true；否则返回false nodeToRemove ← findNode(value) 如果 nodeToRemove = ø 返回 false 结束如果 parent ← findParent(value) 如果 count = 1 root ← ø 否则，如果 nodeToRemove.left = ø 并且 nodeToRemove.right = ø 如果 nodeToRemove.value < parent.value parent.left ← nodeToRemove.right 否则 parent.right ← nodeToRemove.right 结束如果 否则，如果 nodeToRemove.left != ø 并且 nodeToRemove.right != ø next ← nodeToRemove.right 当 next.left != ø next ← next.left 结束循环 如果 next != nodeToRemove.right remove(next.value) nodeToRemove.value ← next.value 否则 nodeToRemove.value ← next.value nodeToRemove.right ← nodeToRemove.right.right 结束如果 否则 如果 nodeToRemove.left = ø next ← nodeToRemove.right 否则 next ← nodeToRemove.left 结束如果 如果 root = nodeToRemove root = next 否则，如果 parent.left = nodeToRemove parent.left = next 否则，如果 parent.right = nodeToRemove parent.right = next 结束如果 结束如果 count ← count - 1 返回 true 结束remove 查找节点的父节点
findParent(value, root) 前置条件：value为要查找其父节点的节点的值，root为BST的根节点 且不为ø 后置条件：如果找到value的父节点，则返回对其的引用；否则返回ø 如果 value = root.value 返回 ø 结束如果 如果 value < root.value 如果 root.left = ø 返回 ø 否则，如果 root.left.value = value 返回 root 否则 返回 findParent(value, root.left) 结束如果 否则 如果 root.right = ø 返回 ø 否则，如果 root.right.value = value 返回 root 否则 返回 findParent(value, root.right) 结束如果 结束如果 结束findParent 查找节点
findNode(root, value) 前置条件：value为要查找的节点的值，root为BST的根节点 后置条件：如果找到了值为value的节点，则返回对该节点的引用；否则返回ø 如果 root = ø 返回 ø 结束如果 如果 root.value = value 返回 root 否则，如果 value < root.value 返回 findNode(root.left, value) 否则 返回 findNode(root.right, value) 结束如果 结束findNode 查找最小值
findMin(root) 前置条件：root为BST的根节点 后置条件：定位到BST中的最小值 如果 root.left = ø 返回 root.value 结束如果 findMin(root.left) 结束findMin 查找最大值
findMax(root) 前置条件：root为BST的根节点 后置条件：定位到BST中的最大值 如果 root.right = ø 返回 root.value 结束如果 findMax(root.right) 结束findMax 遍历
中序遍历
inorder(root) 前置条件：root为BST的根节点 后置条件：以中序遍历的顺序访问BST中的节点 如果 root != ø inorder(root.left) 输出 root.value inorder(root.right) 结束如果 结束inorder 前序遍历
preorder(root) 前置条件：root为BST的根节点 后置条件：以前序遍历的顺序访问BST中的节点 如果 root != ø 输出 root.value preorder(root.left) preorder(root.right) 结束如果 结束preorder 后序遍历
postorder(root) 前置条件：root为BST的根节点 后置条件：以后序遍历的顺序访问BST中的节点 如果 root != ø postorder(root.left) postorder(root.right) 输出 root.value 结束如果 结束postorder 完整代码
BinarySearchTreeNode
import BinaryTreeNode from '../BinaryTreeNode'; import Comparator from '../../../utils/comparator/Comparator'; export default class BinarySearchTreeNode extends BinaryTreeNode { /** * @param {*} [value] - node value. * @param {function} [compareFunction] - comparator function for node values. */ constructor(value = null, compareFunction = undefined) { super(value); // This comparator is used to compare node values with each other. this.compareFunction = compareFunction; this.nodeValueComparator = new Comparator(compareFunction); } /** * @param {*} value * @return {BinarySearchTreeNode} */ insert(value) { if (this.nodeValueComparator.equal(this.value, null)) { this.value = value; return this; } if (this.nodeValueComparator.lessThan(value, this.value)) { // Insert to the left. if (this.left) { return this.left.insert(value); } const newNode = new BinarySearchTreeNode(value, this.compareFunction); this.setLeft(newNode); return newNode; } if (this.nodeValueComparator.greaterThan(value, this.value)) { // Insert to the right. if (this.right) { return this.right.insert(value); } const newNode = new BinarySearchTreeNode(value, this.compareFunction); this.setRight(newNode); return newNode; } return this; } /** * @param {*} value * @return {BinarySearchTreeNode} */ find(value) { // Check the root. if (this.nodeValueComparator.equal(this.value, value)) { return this; } if (this.nodeValueComparator.lessThan(value, this.value) && this.left) { // Check left nodes. return this.left.find(value); } if (this.nodeValueComparator.greaterThan(value, this.value) && this.right) { // Check right nodes. return this.right.find(value); } return null; } /** * @param {*} value * @return {boolean} */ contains(value) { return !!this.find(value); } /** * @param {*} value * @return {boolean} */ remove(value) { const nodeToRemove = this.find(value); if (!nodeToRemove) { throw new Error('Item not found in the tree'); } const { parent } = nodeToRemove; if (!nodeToRemove.left && !nodeToRemove.right) { // Node is a leaf and thus has no children. if (parent) { // Node has a parent. Just remove the pointer to this node from the parent. parent.removeChild(nodeToRemove); } else { // Node has no parent. Just erase current node value. nodeToRemove.setValue(undefined); } } else if (nodeToRemove.left && nodeToRemove.right) { // Node has two children. // Find the next biggest value (minimum value in the right branch) // and replace current value node with that next biggest value. const nextBiggerNode = nodeToRemove.right.findMin(); if (!this.nodeComparator.equal(nextBiggerNode, nodeToRemove.right)) { this.remove(nextBiggerNode.value); nodeToRemove.setValue(nextBiggerNode.value); } else { // In case if next right value is the next bigger one and it doesn't have left child // then just replace node that is going to be deleted with the right node. nodeToRemove.setValue(nodeToRemove.right.value); nodeToRemove.setRight(nodeToRemove.right.right); } } else { // Node has only one child. // Make this child to be a direct child of current node's parent. /** @var BinarySearchTreeNode */ const childNode = nodeToRemove.left || nodeToRemove.right; if (parent) { parent.replaceChild(nodeToRemove, childNode); } else { BinaryTreeNode.copyNode(childNode, nodeToRemove); } } // Clear the parent of removed node. nodeToRemove.parent = null; return true; } /** * @return {BinarySearchTreeNode} */ findMin() { if (!this.left) { return this; } return this.left.findMin(); } } BinarySearchTree
import BinarySearchTreeNode from './BinarySearchTreeNode'; export default class BinarySearchTree { /** * @param {function} [nodeValueCompareFunction] */ constructor(nodeValueCompareFunction) { this.root = new BinarySearchTreeNode(null, nodeValueCompareFunction); // Steal node comparator from the root. this.nodeComparator = this.root.nodeComparator; } /** * @param {*} value * @return {BinarySearchTreeNode} */ insert(value) { return this.root.insert(value); } /** * @param {*} value * @return {boolean} */ contains(value) { return this.root.contains(value); } /** * @param {*} value * @return {boolean} */ remove(value) { return this.root.remove(value); } /** * @return {string} */ toString() { return this.root.toString(); } } 复杂度
时间复杂度
| 访问 | 查找 | 插入 | 删除 |
|---|---|---|---|
| O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) |
空间复杂度
O(n)
