红黑树和树映射 (RBTree 和 TreeMap)

这是一个用 TypeScript 实现的红黑树 (RBTree) 和基于红黑树的树映射 (TreeMap) 的 npm 包。该实现提供了高效的插入、删除、搜索操作，并支持键值对存储。

安装

使用 npm 安装：

npm install @dhlx/red-black-tree

使用 pnpm 安装：

pnpm add @dhlx/red-black-tree

使用 yarn 安装：

yarn add @dhlx/red-black-tree

使用方法

导入模块

import { RBTree, TreeMap } from '@dhlx/red-black-tree';

红黑树 (RBTree)

创建红黑树

const tree = new RBTree<number>();

插入节点

tree.insert(10);
tree.insert(20);
tree.insert(15);

删除节点

tree.delete(15); // 删除值为 15 的节点
tree.deleteAll(20); // 删除所有值为 20 的节点

查找节点

const foundNode = tree.find(10);
console.log(foundNode ? foundNode.data : '未找到');

遍历树

// 中序遍历
for (const value of tree.inOrder()) {
    console.log(value);
}

// 逆序遍历
for (const value of tree.reverseInOrder()) {
    console.log(value);
}

树映射 (TreeMap)

创建树映射

const map = new TreeMap<string, number>();

设置键值对

map.set('a', 1);
map.set('b', 2);
map.set('c', 3);

获取值

console.log(map.get('b')); // 输出 2

检查键是否存在

console.log(map.has('a')); // 输出 true
console.log(map.has('d')); // 输出 false

删除键值对

map.delete('a'); // 删除键 'a'

查找最近的键值对

console.log(map.ceil('b')); // 输出 ['b', 2]（大于或等于 b 的最小键值对）
console.log(map.floor('b')); // 输出 ['b', 2]（小于或等于 b 的最大键值对）
console.log(map.higher('b')); // 输出 ['c', 3]（严格大于 b 的最小键值对）
console.log(map.lower('b')); // 输出 undefined（严格小于 b 的最大键值对）

遍历映射

for (const [key, value] of map) {
    console.log(key, value);
}

// 反向遍历
for (const [key, value] of map.rkeys()) {
    console.log(key, value);
}

API 文档

RBTree

方法

• insert(data: T): boolean 插入节点。
• delete(data: T): boolean 删除一个节点。
• deleteAll(data: T): boolean 删除所有相同值的节点。
• find(data: T): RBTreeNode<T> | null 查找节点。
• inOrder(): Generator<T> 中序遍历。
• reverseInOrder(): Generator<T> 逆序遍历。

TreeMap

方法

• set(key: K, value: V): boolean 设置键值对。
• get(key: K): V | undefined 获取键对应的值。
• has(key: K): boolean 检查键是否存在。
• delete(key: K): boolean 删除键值对。
• ceil(key: K): [K, V] | undefined 获取大于或等于目标键的最小键值对。
• floor(key: K): [K, V] | undefined 获取小于或等于目标键的最大键值对。
• higher(key: K): [K, V] | undefined 获取严格大于目标键的最小键值对。
• lower(key: K): [K, V] | undefined 获取严格小于目标键的最大键值对。
• first(): [K, V] | undefined 获取映射中的第一个键值对。
• last(): [K, V] | undefined 获取映射中的最后一个键值对。
• size(): number 获取映射中的键值对数量。

测试

项目中已包含单元测试，用于验证功能的正确性。运行以下命令以执行测试：

npm test

许可证

MIT License