BinarySearchTree

二叉搜索树，左子树 < 根 < 右子树。

函数签名

function createBinarySearchTree<T>(
  compare?: (a: T, b: T) => number
): BinarySearchTree<T>

interface BinarySearchTree<T> {
  insert(value: T): void
  search(value: T): boolean
  delete(value: T): boolean
  findMin(): T | undefined
  findMax(): T | undefined
  inorderTraversal(): T[]
  preorderTraversal(): T[]
  postorderTraversal(): T[]
  height(): number
  size(): number
  clear(): void
}

API 说明

insert(value: T): void

插入值。

时间复杂度：平均 O(log n)，最坏 O(n)

search(value: T): boolean

搜索值是否存在。

时间复杂度：平均 O(log n)，最坏 O(n)

delete(value: T): boolean

删除值。

时间复杂度：平均 O(log n)，最坏 O(n)

inorderTraversal(): T[]

中序遍历（升序）。

时间复杂度：O(n)

使用示例

import { createBinarySearchTree } from '@shared/functions/data-structures/BinarySearchTree'

const bst = createBinarySearchTree<number>()

bst.insert(50)
bst.insert(30)
bst.insert(70)
bst.insert(20)
bst.insert(40)

console.log(bst.search(30))  // true
console.log(bst.findMin())   // 20
console.log(bst.inorderTraversal())  // [20, 30, 40, 50, 70]

应用场景

1. 动态有序集合：维护有序数据
2. 数据库索引：B树的基础
3. 表达式树：编译器中的语法分析
4. 优先队列：可实现优先队列