数据结构-查找

1. 顺序查找法
2. 分块查找法（索引顺序查找）
3. 折半查找法
   • 判定树
   • ASL（平均查找长度）
4. 二叉搜索树
   1. 查找
   2. 插入
   3. 构造
   4. 删除（中序）
5. 平衡二叉树（AVL）
   1. 插入
      • LL平衡旋转
      • LR平衡旋转
      • RR平衡旋转
      • RL平衡旋转
   2. 构造
   3. 删除
   4. 查找
6. 红黑树
   1. 定义
      • 每个结点或是黑色或是红色
      • 根节点是黑色的
      • 叶节点（虚构的外部节点、NULL节点）都是黑色
      • 不存在两个相邻的红节点
      • 对于每个结点，从该结点到任意一个叶节点的简单路径上，所含黑节点的数量相同
   2. 结论
      1. 从根到叶结点的最长路径不大于最短路径的2倍
      2. 有n个内部结点的红黑树的高度$h\leq 2\log_2{(n+1)}$
   3. 插入
      • 新插入红黑树的结点初始着为红色
   4. 删除*