动态搜索结构.

马强2015年4月4日大纲二叉搜索树平衡二叉树伸展树2二叉搜索树二叉搜索树定义每个节点有一个唯一的key值，且所有结点互不相同左子树所有key值小于根的key值右子树所有key值大于根的key值左右子树都是二叉搜索树12225030011020099105230216二叉搜索树又称为“二叉排序树”、“二叉查找树”、“二叉检索树”3二叉搜索树的基本操作查找插入删除4二叉搜索树查找操作与根结点的key值比较相等则查找成功小于则查找左子树大于则查找右子树1385231837如何查找元素5?555查找成功！5二叉搜索树插入操作•首先执行查找算法，找出将要插入结点的父亲结点•判断被插结点是其父亲结点的左或右孩子。将被插结点作为叶子结点插入。•若二叉树为空。作为根结点。6二叉搜索树插入操作利用插入操作可以构造一棵二叉搜索树首先给出结点序列:13、8、23、5、18、37Φ135371882382355181837377二叉搜索树删除操作情况1•叶子结点：直接删除，更改它的父亲结点的相应指针域为空。•如：删除值为15、70的结点。156070302050603020508二叉搜索树删除操作情况212225030011020099105230400450500•若被删结点只有一个孩子结点。则用它的子树代替它。如删除结点的关键值为99结点。被删结点1222503002002304004505001101059二叉搜索树删除操作情况3被删结点左右孩子都不为空选取“替身”取代被删结点。然后删除替身结点如何选择替身？左子树中最大的结点或右子树中最小的结点1012225030011020099105330400450500被删结点替身11025030010520099330400450500将替身的数据复制到被删结点的数据。删除值为122的结点。110二叉搜索树删除操作情况31112225030011020099105330400450500被删结点替身将替身的数据场复制到被删结点的数据场。删除值为122的结点。20025030011099105400450500330200二叉搜索树删除操作情况312二叉搜索树的性能查找：从根节点向下扫描到叶子结点。O(h)插入和删除：先查找、再操作。所以也是O(h)与树的高度密切相关20025030011099105400450500330主要用于内存中目录的编制要求能够快速的查找、插入删除13二查搜索树的高度输入顺序为4、5、6、7、84567875846输入顺序为7、5、4、6、8最坏情况为n,最好情况为logn如何使树的高度保持为logn？14大纲二叉搜索树平衡二叉树伸展树15平衡二叉搜索树1962年由俄罗斯数学家G.M.Adel’son-Val’skii和E.M.Landis提出，所以简称为AVL树。定义：空树或者是具有以下性质的二叉搜索树左右子树的高度差的绝对值不超过1且左右子树都是AVL树平衡因子：右子树的高度减左子树的高度。简称：bf16平衡二叉树举例11726391518161410000000-1是AVL树163269718261411不是AVL树-30431100-117平衡化旋转目的：通过旋转使每个结点的|bf|2四种旋转：左单旋转右单旋转先左后右双旋转先右后左双旋转3060ABC10123060ABC0018平衡化旋转目的：通过旋转使每个结点的|bf|2四种旋转：左单旋转右单旋转先左后右双旋转先右后左双旋转3060ABC00-1-23060ABC0-119目的：通过旋转使每个结点的|bf|2四种旋转：左单旋转右单旋转先左后右双旋转先右后左双旋转平衡化旋转-100903060ABCDhh-11-2-1906030ABCDh0-2-20906030ABCDh0120目的：通过旋转使每个结点的|bf|2四种旋转：左单旋转右单旋转先左后右双旋转先右后左双旋转平衡化旋转100903060ABCDhh-112-1906030ACBDh0220906030ABCDh-1021平衡化旋转总结3060ABC12-13060ABC-2903060ABCDhh-11-2-1903060ABCDhh-112-1左单旋转右单旋转先左后右先右后左22AVL树的操作和性能操作查找、插入、删除二叉搜索树的方法+平衡旋转时间复杂度O(logn)23大纲二叉搜索树平衡二叉树伸展树24伸展树“八二原则”80%的人只会用到20%的数据正在访问的结点将以很高的概率再次被访问将经常访问的结点放在靠近根的位置，以便再访问。伸展树：对二叉搜索树的改进：每访问完一个结点就把该结点移动到树的根部。25伸展树的旋转方法情况一：被访问结点S的父结点是根结点采用单旋转方式PSABCPSABC26伸展树的旋转方法情况二：同构形状采用一字形旋转方式PSABCGDPSABCGDPSABCGD27伸展树的旋转方法情况三：异构形状采用之字形旋转方式PSABCGDSPABCGDPSABCGD28综合例子803010905020407060803010905020407060803010905020407060803010905020407060一字旋转之字旋转单旋转29伸展树性能分析并不要求每一次操作都是高效的一次操作的时间复杂度或许是O(1)或许是O(n)多次操作的平均时间复杂度为O(logn)30动态搜索结构二叉搜索树AVL树伸展树定义操作：查找、插入、删除四种旋转三种旋转O(logn)O(logn)3132