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

《数据结构——二叉搜索树.ppt》由会员分享，可在线阅读，更多相关《数据结构——二叉搜索树.ppt（38页珍藏版）》请在优知文库上搜索。

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

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

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

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

5、搜索树首先给出结点序列首先给出结点序列:13、8、23、5、18、37 13537 18 8238 235518183737二叉搜索树插入操作12/84二叉搜索树插入操作(另一个例子) 对于关键码集合K = 50，19，35，55，20，5，100，52，88，53，92二叉搜索树的生成过程如图所示： 505195535522010053928813/84 对二叉搜索树的检索，每一次只需与结点的一棵子树相比较 在执行插入操作时，也不必像在有序线性表中插入元素那样要移动大量的数据，而只需改动某个结点的空指针插入一个叶结点即可 与查找结点的操作一样，插入一个新结点操作的时间复杂度是根到插入位置的路

6、径长度，因此在树形比较平衡时二叉搜索树的效率相当高 14/84二叉搜索树删除操作情况1 叶子结点：直接删除，更改它的父亲结点的相应指针场为空。叶子结点：直接删除，更改它的父亲结点的相应指针场为空。如：删除值为如：删除值为 15、70 的结点。的结点。15607030205060302050 子树的根结点：若被删结点的左儿子为空或者右儿子为空。子树的根结点：若被删结点的左儿子为空或者右儿子为空。如何处理呢？如何处理呢？15/84二叉搜索树删除操作情况212225030011020099105230400450500子树的根结点：若被删结点的左儿子为空或者右儿子为空。子树的根结点：若被删结点的左儿

7、子为空或者右儿子为空。如删除结点的关键值为如删除结点的关键值为 99 结点。结点。被删结点被删结点12225030020023040045050011010516/84 要删除的节点有两个子节点要删除的节点有两个子节点 合并删除合并删除 通过复制进行删除通过复制进行删除二叉搜索树删除操作情况317/84合并删除 要删除的节点有两个子节点要删除的节点有两个子节点合并删合并删除除rootrootnode-leftnode-rightnodenode-leftnode-right左子树中最右左子树中最右侧的节点侧的节点18/84合并删除删除删除node153020401510302011125401

8、011512在合并删除后，树的高度增加在合并删除后，树的高度增加19/84合并删除删除删除node15302040151030205402610526在合并删除后，树的高度降低在合并删除后，树的高度降低20/84复制删除 要删除的节点有两个子节点要删除的节点有两个子节点通过复通过复制进行删除制进行删除 选取选取“替身替身”取代被删结点。取代被删结点。 如何选择？如何选择？ 左子树中最大的结点或左子树中最大的结点或 右子树中最小的结点。右子树中最小的结点。21/84复制删除12225030011020099105330400450500被删结点被删结点替替身身110250300105200993

9、30400450500将替身的数据场复制到被删结点的数据场。将替身的数据场复制到被删结点的数据场。删除值为删除值为122的结点。的结点。22/84复制删除 12225030011020099105330400450500被删结点被删结点替替身身将替身的数据场复制到被删结点的数据场。将替身的数据场复制到被删结点的数据场。删除值为删除值为122的结点。的结点。 2002503001109910540045050033023/84内容提要 5.4二叉搜索树二叉搜索树BST 12.4.2 平衡的二叉搜索树平衡的二叉搜索树 5.5堆与优先队列堆与优先队列 5.6哈夫曼树及其应用哈夫曼树及其应用二叉树与树

10、24/84平衡的二叉搜索树(AVL) BST受输入顺序影响受输入顺序影响最好最好O(log n) 最坏最坏O(n) 怎样使得怎样使得BST始终保持始终保持O(log n)级的级的平平衡状态？衡状态？ Adelson-Velskii和和Landis发明了发明了AVLAVL树树一种平衡的二叉搜索树一种平衡的二叉搜索树任何结点的左子树和右子树高度最多相差任何结点的左子树和右子树高度最多相差1 1 输入顺序为输入顺序为 4、5、6、7、8 4 5 6 7 8 7 5 8 4 6 输入顺序为输入顺序为 7、5、4、6、8 25/84AVL树的性质 可以为空可以为空 具有具有n个结点的个结点的AVL树，高

11、度为树，高度为O(log n) 如果如果T是一棵是一棵AVL树树那么它的左右子树那么它的左右子树TL、TR也是也是AVL树树并且并且| hL-hR|1 hL、hR 是它的左右子树的高度是它的左右子树的高度 二叉树与树25/6626/84二叉树与树26/6627/84平衡因子 平衡因子，用平衡因子，用bf(x)来表示结点来表示结点x的平衡因子。它的平衡因子。它被定义为：被定义为： bf(x)= x的右子树的高度的右子树的高度 x的左子树的高度的左子树的高度 对于一个对于一个AVL树中的结点平衡因子之可能取值树中的结点平衡因子之可能取值为为0，1和和-1 二叉树与树27/6628/84AVL树结点

12、的插入 插入与插入与BST一样一样新结点作叶结点新结点作叶结点 需要调整需要调整 相应子树的根结点变化大致有三类相应子树的根结点变化大致有三类结点原来是平衡的，现在成为左重或右重的结点原来是平衡的，现在成为左重或右重的 修改相应前驱结点的平衡因子修改相应前驱结点的平衡因子结点原来是某一边重的，而现在成为平衡的了结点原来是某一边重的，而现在成为平衡的了 树的高度未变，不修改树的高度未变，不修改结点原来就是左重或右重的，而新结点又加到重的结点原来就是左重或右重的，而新结点又加到重的一边一边 不平衡不平衡 “危急结点危急结点”二叉树与树28/6629/84恢复平衡二叉树与树29/6630/84AVL

13、树结构调整 左单旋转左单旋转 右单旋转右单旋转 先左后右旋转先左后右旋转 先右后左旋转先右后左旋转二叉树与树30/6631/8431左单旋转32/8432右单旋转33/8433先左后右旋转34/8434先右后左旋转35/84AVL树的插入 向一棵高度平衡的向一棵高度平衡的AVL树中插入一个新树中插入一个新结点时，如果树中某个结点的平衡因子结点时，如果树中某个结点的平衡因子的绝对值的绝对值|balance|1,则出现了不平衡，则出现了不平衡，需要做平衡化处理。需要做平衡化处理。二叉树与树35/6636/8436平衡二叉搜索树插入操作举例37/84课堂练习 假定一组数据对象为（假定一组数据对象为（40，28，16，56，50，32，30，63），按次序插入每个对），按次序插入每个对象生成一棵高度平衡的二叉搜索树。给象生成一棵高度平衡的二叉搜索树。给出插入各结点后的树的形状。出插入各结点后的树的形状。二叉树与树37/6638/84书 面 作 业 132页：页：4，5，6，7，13 376页：页：15，18