Sequential Symbol Tables

顺序符号表定义

顺序符号表是一种存储键值对(key-value pairs)的数据结构，支持按键的顺序进行高效的查找和操作， 键(Keys)必须是可比较的，且按照键的大小顺序进行组织。每个键都必须是唯一的。

API

主要操作有：

• put(key, value)：将键值对存入符号表中。
• get(key)：根据键查找值。
• delete(key)：根据键删除值。
• contains(key)：判断符号表中是否包含指定键。
• isEmpty()：判断符号表是否为空。
• size()：获取符号表中键值对的数量。

有序性操作

• min()：获取最小的键。
• max()：获取最大的键。
• floor(key)：获取小于等于key的最大键。
• ceiling(key)：获取大于等于key的最小键。
• select(k)：获取排名为k的键。
• rank(key)：获取键的排名。

范围查找

• keys(lo, hi)：获取键在lo和hi之间的所有键。
• keys()：获取符号表中所有键的集合。

实现方式

• 二叉查找树
• 红黑树
• B树
• 跳表
• 有序数组

性能特征

• 查找操作的时间复杂度通常为O(logN)
• 插入和删除操作的时间复杂度也通常为O(logN)
• 顺序操作（如遍历）的效率较高

应用场景

• 数据库索引
• 编译器中的符号表
• 文件系统中的路径查找