3 个版本
| 0.1.2 | 2020 年 10 月 1 日 |
|---|---|
| 0.1.1 | 2020 年 8 月 26 日 |
| 0.1.0 | 2020 年 8 月 25 日 |
#1694 在 数据结构
72KB
1.5K SLoC
treers
Sedgewick 树图，简单实现
关于
这是一个业余项目，用 Rust 简单重写了 Sedgewick 的树结构。
贡献
请贡献，欢迎提交问题，还有很多东西可以改进（如文档改进）。
树图
接口 特性
- SedgewickMap
| 名称 | 描述 |
|---|---|
| new | 创建新的树图实例 |
| size | 图中的元素数量 |
| get | 通过键获取图中的值 |
| put | 通过键值对插入 |
| height | 树高度 |
| is_empty | 检查图是否为空 |
| contains | 如果项目存在，返回 true |
| min | 检索图中的最小键 |
| max | 检索图中的最大键 |
| delete | 待办事项 |
- 树遍历
| 名称 | 描述 |
|---|---|
| pre_order | 前序遍历；DFS |
| in_order | 中序遍历；DFS |
| post_order | 后序遍历；DFS |
| level_order | 层序遍历；BFS |
BST - 二叉搜索树
- 非常慢（请查看基准测试）
- 有树遍历实现
| 算法 | 平均 | 最坏情况 |
|---|---|---|
| 空间 | O(n) | O(n) |
| 搜索 | O(log n) | O(n) |
| 插入 | O(log n) | O(n) |
红黑树
- 仅 比标准平衡树实现慢 3 倍（请查看基准测试）
- 有树遍历实现
- 基本规则
- 每个节点只能是红色或黑色
- 根节点必须是黑色
- 红色节点向左倾斜
- 从根到空链接的每条路径都具有相同数量的黑色链接
| 算法 | 平均 | 最坏情况 |
|---|---|---|
| 空间 | O(n) | O(n) |
| 搜索 | O(log n) | O(log n) |
| 插入 | O(log n) | O(log n) |
BTree - 平衡树
- 非常慢（请查看基准测试）
- 没有实现树遍历
- 在数据库和文件系统中应用广泛
- 注意：我已经在官方algs4中修复了一个循环（内存）错误
| 算法 | 平均 | 最坏情况 |
|---|---|---|
| 空间 | O(n) | O(n) |
| 搜索 | O(log n) | O(log n) |
| 插入 | O(log n) | O(log n) |
文档
待办事项
- 对文档和README进行更多工作
- BTree，使用栈内存存储条目
- 用迭代器替换树遍历
- 实现树剩余的方法
- 使红黑树变得非常快
资源
作者
- 伊万·兹沃尼米尔·霍尔瓦特 GitHub资料
许可
在MIT许可下授权。