二叉树Binary tree
每个节点至多有两个孩子，用父子关系表达层级。
遍历 ；查找不保证层级表示、表达式树与其他树结构的基础。
二叉搜索树Binary search tree
按键的大小关系把记录放在左右子树。
基本操作 ；退化时 h 可达 n有序字典与平衡搜索树的基础。
AVL 树AVL tree
严格限制左右子树的高度差。
查找 / 插入 / 删除需要严格控制搜索路径长度的有序集合。
红黑树Red-black tree
通过颜色约束和局部调整保持搜索树高度受控。
查找 / 插入 / 删除B / B+ 树B-tree family
在一个节点内保存多个键，降低树高和访问次数。
高度约 ，B 为有效分支因子二叉堆Binary heap
以完全二叉树维护堆序，可用于实现优先队列。
查看堆顶 ；插入 / 弹出跳表Skip list
在有序链表上增加多层稀疏索引。
随机层高下期望查找 / 更新Trie / Radix TreePrefix index
按键的前缀分支；压缩变体合并单分支路径。
查找通常与键长 L 相关区间树Interval tree
为区间集合维护可剪枝的边界信息。
相交查询成本包括查找及结果输出地址重叠、范围冲突、区间检索。
线段树Segment tree
递归划分下标区间，为每个区间维护聚合值。
常见点更新 / 区间查询动态区间和、最值及可组合的区间聚合。
树状数组Fenwick tree
用下标的最低有效位组织可复用的前缀聚合区间。
点更新 / 前缀和 ，空间频繁点更新与前缀统计、计数和排名。
Maple TreeMaple Tree
以多路树组织不重叠的整数索引区间。
范围查找随树高增长；成本还取决于节点布局XArrayXArray
将无符号整数索引映射到条目，支持稀疏存储与有序遍历。
查找与索引层数相关；支持有序迭代