5.1 平衡树

1. 扩展：二叉搜索树→平衡二叉搜索树（简称平衡树）

   1. AVL树：各种旋转场景，命名是两个发明者的名字缩写

   2. 红黑树：近似平衡的二叉搜索树

   3. 树堆（最容易实现的平衡树之一）

2. 扩展：链表

   1. 跳表：元素有序的链表，对标“平衡树和二分查找”

      • 平衡树：查询/插入/删除都高效，但比较复杂不容易实现

      • 二分查找：在数组上查询 O(logN)

大多数情况下，不会自己去实现平衡树或跳表，可以使用语言内置的“有序集合”库

1. 239. 滑动窗口最大值（H）

2. ACW-136. 邻值查找（M）

3. 1206. 设计跳表（H）：选做

4. 253. 普通平衡树（M）：选做