data-structures - 一些数据结构的示例应用

Question

我已经了解以下数据结构，并且正在寻找它们在实际应用程序中的示例用法；

• 二叉搜索树
• 红黑树
• 区间树（增强 RBT）
• 哈希表

Answer 1

1. 二叉搜索树
BST 广泛用于信息组织、索引和检索。Microsoft 的 Windows Explorer 和 Internet Explorer 是使用 BST 的最著名的应用程序。

2. 红黑树（我们称其为“AVL 树”）
RBT 只是一种特定的 BST。借助 RBT，我们可以快速定位特定值对应的数据结构。Linux 内核在管理 vm_area_struct 时将 RBT 中的所有内存区域对象链接在一起。

3. 增强彩铃
增强彩铃的工作方式与普通彩铃非常相似，不同之处在于它在每个节点中保留了附加信息。Linux Kernel引入了 Augmented RBT 以改进对 x86 架构的页面属性表 (PAT) 支持的功能。

4. 哈希表
哈希的使用极其广泛。例如著名的MD5 哈希算法、P2P 传输等。