搜索结构

• 静态搜索结构
• 二叉搜索树
• AVL树

静态搜索结构

• 每个对象有若干属性，其中一个属性可以唯一标识对象，称为关键码
• 两种环境
  • 静态环境——静态搜索表
  • 动态环境——动态搜素表

二叉搜索树

• 每个节点都有一个关键码，所有关键码互不相同
• 左子树上所有节点的关键码都小于根节点的关键码
• 右子树上所有节点的关键码都大于根节点的关键码
• 左右子树都是二叉搜索树

搜索

• 根节点为NULL，则搜索不成功
• 用给定值x与根节点关键码比较
  • 如果等于，则成功
  • 小于，递归搜索左子树
  • 大于，递归搜索右子树

插入

• 先搜索元素是否存在
  • 成功：已有元素，不再插入
  • 失败：把新元素加到搜索停止的地方
• 建立二叉树为插入过程

删除

• 保证删除并重新链接后性质不失去

• 保证搜索性能不至于降低，还需要防止重新链接后树的高度增加

• 首先查找，确定被删除节点在二叉搜索树中

• 分情况讨论：

  • 删除叶节点：直接删除
  • 删除节点左子为空或右子为空：删除并用右子或左子顶替位置
  • 左右子树都不为空（二选一）
    • 在右子树中找最小的节点，填补到被删节点，再处理这个节点的删除问题
    • 在左子树中找最大的节点，填补到被删节点，再处理这个节点的删除问题

AVL树（高度平衡的二叉搜索树）

可视化工具：AVL Tree Visualzation

AVL是空树或者具有以下性质的二叉搜索树：左右子树都是AVL树，且左右子树高度差绝对值不超过1

节点的平衡因子balance：每个节点附加一个数字——该节点右子树与左子树的高度差

• AVL树任一节点的平衡因子只能取-1，0，1
• 如果一个节点平衡因子的绝对值大于1，则失去平衡，不再是AVL树
• 如果一个二叉搜索树是高度平衡，且有n个节点，则平均搜索长度可保持在$O(log_2n)$

平衡化旋转

• 两类
  • 单旋转（左旋和右旋）
  • 双旋转（左平衡和右平衡）
• 每插入一个新节点时，AVL树中相关节点的平衡状态会发生改变，需要从插入位置沿通向根的路径回溯，检查各节点的平衡因子
• 如果在某一节点发现高度不平衡，停止回溯，从发生不平衡的节点起，沿刚才回溯的路径取直接下两层的节点
• 如果这三个节点处于一条直线上免责采用单旋转平衡化
• 如果这三个节点处于一条折线上，则采用双旋转进行平衡化：分为先左后右和先右后左

AVL树的插入

• 插入新节点，如果不平衡，需要做平衡化处理
• 建树从空树开始，逐步插入新节点

AVL树的删除

• 如果被删节点x最多只有一个子女：

  • 将节点x从树中删去
  • 因为最多有一个子女，可以简单的把x的双亲节点中原来指向x的指针改到这个子女节点
  • 如果x没有子女，x双亲节点的指针置位NULL
  • 将原来以节点x为根的字数高度-1，调整

• 如果x有两个子女：

  • 搜索x在中序下的直接前驱y（左子树的最右一个）或者直接后继（右子树的最左一个）
  • 把y的内容传送给节点x，问题转移到删除节点y
  • 因为节点y最多有一个子女，变为上述删除方法

• 用一个bool shorter来指明子树高度是否变化

• 如果shorter是true，则从x的双亲到根的路径上的各个节点p，在shorter保持true是执行下列操作，变为false，终止

  • p的balance为0，如果他的左子树或右子树变短，则balance改为1或-1，同时shorter变为false

  • p的balance不为0且较高的子树被缩短，则p的balance改为0，同时shorter变为true

  • p的balance不为0且较矮的子树被缩短，则在p不平衡，进行平衡化旋转：

    3种情况：

    令p的较高的子树的根为q，根据q的balance

    • q的balance为0，执行单旋转，shorter变为false

      

    • q的balance与p的balance相同，执行单旋转，p和q的balance均改为0，同时shorter为true

      

    • p与q的balance相反，执行双旋转，先绕q转，再绕p转，新根balance变为0，其他节点的balance相应处理，shorter为true

      

AVL树的高度

• n个结点的AVL树的高度不超过$1.44*log_2{(n+2)}-1.328$
• AVL树删除一个节点并做平衡化旋转的时间为$O(log_2n)$
• 适合于组织在内存中较小的索引（或目录），较大的文件系统不合适
• 文件检索系统中大量使用的是B-树或B+树做文件检索