AVLTree

AVL 树（自平衡二叉搜索树），通过旋转保持平衡。

函数签名

function createAVLTree<T>(
  compare?: (a: T, b: T) => number
): AVLTree<T>

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

API 说明

insert(value): void

插入值，自动旋转保持平衡。

时间复杂度：O(log n)

isBalanced(): boolean

检查树是否平衡。

时间复杂度：O(n)

使用示例

import { createAVLTree } from '@shared/functions/data-structures/AVLTree'

const avl = createAVLTree<number>()

// 升序插入会自动旋转保持平衡
avl.insert(10)
avl.insert(20)
avl.insert(30)

console.log(avl.isBalanced())  // true
console.log(avl.height())      // 2（平衡后）

应用场景

1. 数据库索引：保持查询效率
2. 有序集合：自动平衡的有序数据
3. 范围查询：高效区间查找
4. 内存管理：平衡的内存分配