动态搜索结构

1、马强2015年4月4日大纲二叉搜索树平衡二叉树伸展树 2 二叉搜索树二叉搜索树定义每个节点有一个唯一的key值，且所有结点互不相同左子树所有key值小于根的key值右子树所有key值大于根的key值左右子树都是二叉搜索树12225030011020099105230216二叉搜索树又称为二叉搜索树又称为“二叉排序树二叉排序树”、“二叉查找树二叉查找树”、“二叉检索树二叉检索树”3二叉搜索树的基本操作查找插入删除4二叉搜索树查找操作 与根结点的key值比较相等则 查找成功小于则查找左子树大于则查找右子树13 85231837如何查找元素如何查找元素 5 ?555查找成功！查找成功！5二叉搜索树插

2、入操作 首先执行查找算法，找出将要插入结点的父亲结点首先执行查找算法，找出将要插入结点的父亲结点 判断被插结点是其父亲结点的左或右孩子。将被插判断被插结点是其父亲结点的左或右孩子。将被插结点作为叶子结点插入。结点作为叶子结点插入。 若二叉树为空。作为根结点。若二叉树为空。作为根结点。6二叉搜索树插入操作利用插入操作可以构造一棵二叉搜索树利用插入操作可以构造一棵二叉搜索树首先给出结点序列首先给出结点序列:13、8、23、5、18、37 13537 18 8238 2355181837377二叉搜索树删除操作情况1 叶子结点：直接删除，更改它的父亲结点的相应指针域为空。叶子结点：直接删除，更改它的

3、父亲结点的相应指针域为空。如：删除值为如：删除值为 15、70 的结点。的结点。156070302050603020508二叉搜索树删除操作情况212225030011020099105230400450500若被删结点只有一个孩子结点。则用它的子树代替它。若被删结点只有一个孩子结点。则用它的子树代替它。如删除结点的关键值为如删除结点的关键值为 99 结点。结点。被删结点被删结点1222503002002304004505001101059二叉搜索树删除操作情况3被删结点左右孩子都不为空选取“替身”取代被删结点。然后删除替身结点如何选择替身？左子树中最大的结点或 右子树中最小的结点101222

4、5030011020099105330400450500被删结点被删结点替替身身11025030010520099330400450500将替身的数据复制到被删结点的数据。将替身的数据复制到被删结点的数据。删除值为删除值为122的结点。的结点。110二叉搜索树删除操作情况311 12225030011020099105330400450500被删结点被删结点替替身身将替身的数据场复制到被删结点的数据场。将替身的数据场复制到被删结点的数据场。删除值为删除值为122的结点。的结点。 20025030011099105400450500330200二叉搜索树删除操作情况312二叉搜索树的性能查找：从

5、根节点向下扫描到叶子结点。O(h)插入和删除：先查找、再操作。所以也是O(h)与树的高度密切相关20025030011099105400450500330主要用于内存中目录的编制要求能够快速的查找、插入删除13二查搜索树的高度 输入顺序为输入顺序为 4、5、6、7、8 4 5 6 7 8 7 5 8 4 6 输入顺序为输入顺序为 7、5、4、6、8 最坏情况为n,最好情况为logn如何使树的高度保持为logn？14大纲二叉搜索树平衡二叉树伸展树 15平衡二叉搜索树1962年由俄罗斯数学家G.M.Adelson-Valskii和E.M.Landis提出，所以简称为AVL树。定义：空树或者是具有以

6、下性质的二叉搜索树左右子树的高度差的绝对值不超过 1且左右子树都是AVL树平衡因子：右子树的高度减左子树的高度。简称：bf16平衡二叉树举例11726391518161410000000-1是AVL树163269718261411不是AVL树-30431100-117平衡化旋转目的：通过旋转使每个结点的 |bf|2四种旋转：左单旋转右单旋转先左后右双旋转先右后左双旋转3060ABC10 123060ABC0018平衡化旋转目的：通过旋转使每个结点的 |bf|2四种旋转：左单旋转右单旋转先左后右双旋转先右后左双旋转3060ABC00-1-23060ABC0-119目的：通过旋转使每个结点的 |b

7、f|2四种旋转：左单旋转右单旋转先左后右双旋转先右后左双旋转平衡化旋转-100903060ABCDhh-11-2-1906030ABCDh0-2-20906030ABCDh0120目的：通过旋转使每个结点的 |bf|2四种旋转：左单旋转右单旋转先左后右双旋转先右后左双旋转平衡化旋转100903060ABCDhh-112-1906030ACBDh0220906030ABCDh-1021平衡化旋转总结3060ABC12-13060ABC-2903060ABCDhh-11-2-1903060ABCDhh-112-1左单旋转右单旋转先左后右先右后左22AVL树的操作和性能操作查找、插入、删除二叉搜索树

8、的方法+平衡旋转时间复杂度O(logn)23大纲二叉搜索树平衡二叉树伸展树 24伸展树“八二原则”80%的人只会用到20%的数据正在访问的结点将以很高的概率再次被访问将经常访问的结点放在靠近根的位置，以便再访问。伸展树：对二叉搜索树的改进：每访问完一个结点就把该结点移动到树的根部。25伸展树的旋转方法情况一：被访问结点S的父结点是根结点采用单旋转方式PSABCPSABC26伸展树的旋转方法情况二：同构形状采用一字形旋转方式PSABCGDPSABCGDPSABCGD27伸展树的旋转方法情况三：异构形状采用之字形旋转方式PSABCGDSPABCGDPSABCGD28综合例子803010905020407060803010905020407060803010905020407060803010905020407060一字旋转之字旋转单