数据结构——二叉搜索树.ppt

《数据结构——二叉搜索树.ppt》由会员分享，可在线阅读，更多相关《数据结构——二叉搜索树.ppt（38页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、5 5 二叉树二叉树15.1 二叉树的概念5.2 二叉树的周游二叉树的周游5.3 5.3 二叉树的存储结构二叉树的存储结构5.4 5.4 二叉搜索树二叉搜索树5.5 堆与优先队列5.6 Huffman树及其应用5.7 二叉树知识点总结主要内容主要内容2 二叉搜索树二叉搜索树二叉搜索树二叉搜索树的查找二叉搜索树的查找 二叉搜索树的插入操作二叉搜索树的插入操作二叉搜索树的删除操作二叉搜索树的删除操作3二叉搜索树一棵非空的二叉搜索树满足以下特征：一棵非空的二叉搜索树满足以下特征：1.每个结点都有一个作为搜索依据的关键码，所有每个结点都有一个作为搜索依据的关键码，所有结点的关键码互不相同。结点的关键码

2、互不相同。2.左子树（如果存在）上的所有结点的关键码均小左子树（如果存在）上的所有结点的关键码均小于根结点的关键码。于根结点的关键码。3.右子树（如果存在）上的所有结点的关键码均大右子树（如果存在）上的所有结点的关键码均大于根结点的关键码。于根结点的关键码。4.根结点的左右子树也都是二叉搜索树。根结点的左右子树也都是二叉搜索树。二叉搜索树又称为二叉搜索树又称为“二叉排序树二叉排序树”、“二叉查找树二叉查找树”、“二叉检索树二叉检索树”4二叉搜索树举例LNPEMCY12225030011020099105230216607080505540是二叉搜索树是二叉搜索树不是二叉搜索树5二叉搜索树的基本

3、操作查找查找插入插入删除删除6二叉搜索树查找操作分割式查找法：分割式查找法：若根结点的关键码等于查找的关键码，成功。若根结点的关键码等于查找的关键码，成功。否则，若小于根结点的关键码，查其左子树。否则，若小于根结点的关键码，查其左子树。大于根结点的关键码，查其右子树。大于根结点的关键码，查其右子树。二叉搜索树的高效率在于继续检索时只需要查找两棵子树之一二叉搜索树的高效率在于继续检索时只需要查找两棵子树之一713 85231837如何查找元素如何查找元素 5?555查找成功！查找成功！二叉搜索树查找操作8二叉搜索树查找分析平均情况分析 156070302050156070302050ASL=(1

4、+2+2+3+3+3)/6=14/6ASL=(1+2+3+4+5+6)/6=21/69二叉搜索树插入操作 首先执行查找算法，找出被插结点的父亲结点。首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。若二叉树为空。则首先单独生成根结点。注意注意：新插入的结点总是叶子结点新插入的结点总是叶子结点。10利用插入操作可以构造一棵二叉搜索树利用插入操作可以构造一棵二叉搜索树首先给出结点序列首先给出结点序列:13、8、23、5、18、37 1353

5、7 18 8238 235518183737二叉搜索树插入操作11二叉搜索树插入操作(另一个例子)对于关键码集合K=50，19，35，55，20，5，100，52，88，53，92二叉搜索树的生成过程如图所示：505195535522010053928812对二叉搜索树的检索，每一次只需与结点的一棵子树相比较在执行插入操作时，也不必像在有序线性表中插入元素那样要移动大量的数据，而只需改动某个结点的空指针插入一个叶结点即可与查找结点的操作一样，插入一个新结点操作的时间复杂度是根到插入位置的路径长度，因此在树形比较平衡时二叉搜索树的效率相当高 13二叉搜索树删除操作情况1 叶子结点：直接删除，更改

6、它的父亲结点的相应指针场为空。叶子结点：直接删除，更改它的父亲结点的相应指针场为空。如：删除值为如：删除值为 15、70 的结点。的结点。15607030205060302050 子树的根结点：若被删结点的左儿子为空或者右儿子为空。子树的根结点：若被删结点的左儿子为空或者右儿子为空。如何处理呢？如何处理呢？14二叉搜索树删除操作情况212225030011020099105230400450500子树的根结点：若被删结点的左儿子为空或者右儿子为空。子树的根结点：若被删结点的左儿子为空或者右儿子为空。如删除结点的关键值为如删除结点的关键值为 99 结点。结点。被删结点被删结点1222503002

7、0023040045050011010515要删除的节点有两个子节点要删除的节点有两个子节点合并删除合并删除通过复制进行删除通过复制进行删除二叉搜索树删除操作情况316合并删除要删除的节点有两个子节点要删除的节点有两个子节点合并删除合并删除rootrootnode-leftnode-rightnodenode-leftnode-right左子树中最右左子树中最右侧的节点侧的节点17合并删除删除删除node153020401510302011125401011512在合并删除后，树的高度增加在合并删除后，树的高度增加18合并删除删除删除node15302040151030205402610526

8、在合并删除后，树的高度降低在合并删除后，树的高度降低19复制删除要删除的节点有两个子节点要删除的节点有两个子节点通过复制通过复制进行删除进行删除选取选取“替身替身”取代被删结点。取代被删结点。如何选择？如何选择？左子树中最大的结点或左子树中最大的结点或 右子树中最小的结点。右子树中最小的结点。20复制删除12225030011020099105330400450500被删结点被删结点替替身身11025030010520099330400450500将替身的数据场复制到被删结点的数据场。将替身的数据场复制到被删结点的数据场。删除值为删除值为122的结点。的结点。21复制删除 1222503001

9、1020099105330400450500被删结点被删结点替替身身将替身的数据场复制到被删结点的数据场。将替身的数据场复制到被删结点的数据场。删除值为删除值为122的结点。的结点。2002503001109910540045050033022内容提要5.4二叉搜索树二叉搜索树BST12.4.2 平衡的二叉搜索树平衡的二叉搜索树5.5堆与优先队列堆与优先队列5.6哈夫曼树及其应用哈夫曼树及其应用二叉树与树23平衡的二叉搜索树(AVL)BST受输入顺序影响受输入顺序影响最好最好O(log n)最坏最坏O(n)怎样使得怎样使得BST始终保持始终保持O(log n)级级的的平平衡状态？衡状态？Ade

10、lson-Velskii和和Landis发明了发明了AVLAVL树树一种平衡的二叉搜索树一种平衡的二叉搜索树任何结点的左子树和右子树高度最多相差任何结点的左子树和右子树高度最多相差1 124AVL树的性质可以为空可以为空具有具有n个结点的个结点的AVL树，高度为树，高度为O(log n)如果如果T是一棵是一棵AVL树树那么它的左右子树那么它的左右子树TL、TR也是也是AVL树树并且并且|hL-hR|1 hL、hR 是它的左右子树的高度是它的左右子树的高度 二叉树与树25/6625二叉树与树26/6626平衡因子平平衡衡因因子子，用用bf(x)来来表表示示结结点点x的的平平衡衡因因子子。它它被定

11、义为：被定义为：bf(x)=x的右子树的高度的右子树的高度 x的左子树的高度的左子树的高度对于一个对于一个AVL树中的结点平衡因子之可能取值树中的结点平衡因子之可能取值为为0，1和和-1 二叉树与树27/663 38 89 912121010151511111 1-1-10 0-1-11 10 00 027AVL树结点的插入插入与插入与BST一样一样新结点作叶结点新结点作叶结点需要调整需要调整相应子树的根结点变化大致有三类相应子树的根结点变化大致有三类结点原来是平衡的，现在成为左重或右重的结点原来是平衡的，现在成为左重或右重的修改相应前驱结点的平衡因子修改相应前驱结点的平衡因子结点原来是某一边

12、重的，而现在成为平衡的了结点原来是某一边重的，而现在成为平衡的了树的高度未变，不修改树的高度未变，不修改结点原来就是左重或右重的，而新结点又加到重的结点原来就是左重或右重的，而新结点又加到重的一边一边不平衡不平衡“危急结点危急结点”二叉树与树28/6628恢复平衡二叉树与树29/66重新调整为平衡结构重新调整为平衡结构重新调整为平衡结构重新调整为平衡结构插入插入插入插入17171717后导致不平衡后导致不平衡后导致不平衡后导致不平衡3 38 810101212151517171 1-1 10 0 2 2 2 21 10 03 38 810101515171712120 0-1 10 0 0 0

13、0 00 03 38 81010121215150 0-1 10 0 1 10 029AVL树结构调整左单旋转左单旋转右单旋转右单旋转先左后右旋转先左后右旋转先右后左旋转先右后左旋转二叉树与树30/663031左单旋转A AC Ch hh hh hB BD DE EA AC Ch hh+1h+1h hB BD DE EA AC Ch hh+1h+1h hB BD DE E初始状态初始状态插入后失衡插入后失衡调整后平衡调整后平衡3132右单旋转A Ah hh hh hD DE EB BC CA Ah+1h+1h hh hD DE EB BC CA AB Bh hh+1h+1D DE Eh hC

14、C初始状态初始状态插入后失衡插入后失衡调整后平衡调整后平衡3233先左后右旋转A Ah hh hh hD DF FB BE Eh-1h-1G GC CA Ah hh-1h-1h hD DF FB BE Eh-1h-1G GC C初初始始状状态态插插入入失失衡衡，最最近近的的失失衡衡点点为为A AA Ah hh hh hD DF FB BE Eh-1h-1G GC C围围绕绕A A的的做做孩孩子子B B左左旋旋A Ah hh hh hD DF FB BE Eh-1h-1G GC C围围绕绕A A右右旋旋3334先右后左旋转A Ah hh-1h-1h hE EF FC CD Dh hG GB BA

15、 Ah hh-1h-1h hE EF FC CD Dh-1h-1G GB B初初始始状状态态A Ah hh-1h-1h hE EF FC CD Dh hG GB B插插入入失失衡衡，最最近近的的失失衡衡点点为为A A围围绕绕A A的的右右孩孩子子C C右右旋旋B BA Ah hh-1h-1h hE EF FC CD Dh hG G围围绕绕A A左左旋旋34AVL树的插入向一棵高度平衡的向一棵高度平衡的AVL树中插入一个新结树中插入一个新结点时，如果树中某个结点的平衡因子的绝点时，如果树中某个结点的平衡因子的绝对值对值|balance|1,则出现了不平衡，需则出现了不平衡，需要做平衡化处理。要做

16、平衡化处理。二叉树与树35/663536平衡二叉搜索树插入操作举例向向AVLAVL树中插入树中插入16,3,7,11,9,26,18,14,1516,3,7,11,9,26,18,14,15的调整过程：的调整过程：16160 016163 3-1-10 0-2-216163 37 71 10 00 07 73 316160 00 07 73 3161611111 10 0-1-10 07 73 3161611119 92 2-2-2-1-10 00 07 73 311119 916161 10 00 00 00 0左右双旋左右双旋右单旋右单旋36课堂练习假定一组数据对象为（假定一组数据对象为（40，28，16，56，50，32，30，63），按次序插入每个），按次序插入每个对象生成一棵高度平衡的二叉搜索树。给对象生成一棵高度平衡的二叉搜索树。给出插入各结点后的树的形状。出插入各结点后的树的形状。二叉树与树37/6637书 面 作 业132页：页：4，5，6，7，13376页：页：15，1838