数据结构——二叉搜索树.ppt
1/84,5 二叉树,2/84,5.1 二叉树的概念5.2 二叉树的周游5.3 二叉树的存储结构5.4 二叉搜索树5.5 堆与优先队列5.6 Huffman树及其应用5.7 二叉树知识点总结,主要内容,3/84,二叉搜索树,二叉搜索树二叉搜索树的查找 二叉搜索树的插入操作二叉搜索树的删除操作,二叉搜索树,一棵非空的二叉搜索树满足以下特征：每个结点都有一个作为搜索依据的关键码，所有结点的关键码互不相同。左子树（如果存在）上的所有结点的关键码均小于根结点的关键码。右子树（如果存在）上的所有结点的关键码均大于根结点的关键码。根结点的左右子树也都是二叉搜索树。,二叉搜索树又称为“二叉排序树”、“二叉查找树”、“二叉检索树”,5/84,二叉搜索树举例,是二叉搜索树,是二叉搜索树,不是二叉搜索树,6/84,二叉搜索树的基本操作,查找插入删除,7/84,二叉搜索树查找操作,分割式查找法：若根结点的关键码等于查找的关键码，成功。否则，若小于根结点的关键码，查其左子树。大于根结点的关键码，查其右子树。,二叉搜索树的高效率在于继续检索时只需要查找两棵子树之一,8/84,如何查找元素 5?,查找成功！,二叉搜索树查找操作,9/84,二叉搜索树查找分析平均情况分析,15,60,70,30,20,50,ASL=(1+2+2+3+3+3)/6=14/6,ASL=(1+2+3+4+5+6)/6=21/6,10/84,二叉搜索树插入操作,首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。,11/84,利用插入操作可以构造一棵二叉搜索树,二叉搜索树插入操作,12/84,二叉搜索树插入操作(另一个例子),对于关键码集合K=50，19，35，55，20，5，100，52，88，53，92二叉搜索树的生成过程如图所示：,13/84,对二叉搜索树的检索，每一次只需与结点的一棵子树相比较在执行插入操作时，也不必像在有序线性表中插入元素那样要移动大量的数据，而只需改动某个结点的空指针插入一个叶结点即可与查找结点的操作一样，插入一个新结点操作的时间复杂度是根到插入位置的路径长度，因此在树形比较平衡时二叉搜索树的效率相当高,14/84,二叉搜索树删除操作情况1,叶子结点：直接删除，更改它的父亲结点的相应指针场为空。如：删除值为 15、70 的结点。,15,60,70,30,20,50,子树的根结点：若被删结点的左儿子为空或者右儿子为空。如何处理呢？,15/84,二叉搜索树删除操作情况2,122,250,300,110,200,99,105,230,400,450,500,子树的根结点：若被删结点的左儿子为空或者右儿子为空。如删除结点的关键值为 99 结点。,16/84,要删除的节点有两个子节点合并删除通过复制进行删除,二叉搜索树删除操作情况3,17/84,合并删除,要删除的节点有两个子节点合并删除,18/84,合并删除,在合并删除后，树的高度增加,19/84,合并删除,15,10,30,20,5,40,2,6,在合并删除后，树的高度降低,20/84,复制删除,要删除的节点有两个子节点通过复制进行删除选取“替身”取代被删结点。如何选择？左子树中最大的结点或 右子树中最小的结点。,21/84,复制删除,122,250,300,110,200,99,105,330,400,450,500,将替身的数据场复制到被删结点的数据场。删除值为122的结点。,22/84,复制删除,122,250,300,110,200,99,105,330,400,450,500,被删结点,将替身的数据场复制到被删结点的数据场。删除值为122的结点。,23/84,内容提要,5.4二叉搜索树BST12.4.2 平衡的二叉搜索树5.5堆与优先队列5.6哈夫曼树及其应用,二叉树与树,24/84,平衡的二叉搜索树(AVL),BST受输入顺序影响最好O(log n)最坏O(n)怎样使得BST始终保持O(log n)级的平衡状态？Adelson-Velskii和Landis发明了AVL树一种平衡的二叉搜索树任何结点的左子树和右子树高度最多相差1,25/84,AVL树的性质,可以为空具有n个结点的AVL树，高度为O(log n)如果T是一棵AVL树那么它的左右子树TL、TR也是AVL树并且|hL-hR|1 hL、hR 是它的左右子树的高度,二叉树与树,25/66,26/84,二叉树与树,26/66,27/84,平衡因子,平衡因子，用bf(x)来表示结点x的平衡因子。它被定义为：bf(x)=x的右子树的高度 x的左子树的高度对于一个AVL树中的结点平衡因子之可能取值为0，1和-1,二叉树与树,27/66,28/84,AVL树结点的插入,插入与BST一样新结点作叶结点需要调整相应子树的根结点变化大致有三类结点原来是平衡的，现在成为左重或右重的修改相应前驱结点的平衡因子结点原来是某一边重的，而现在成为平衡的了树的高度未变，不修改结点原来就是左重或右重的，而新结点又加到重的一边不平衡“危急结点”,二叉树与树,28/66,29/84,恢复平衡,二叉树与树,29/66,重新调整为平衡结构,3,8,10,12,15,0,-1,0,1,0,30/84,AVL树结构调整,左单旋转右单旋转先左后右旋转先右后左旋转,二叉树与树,30/66,31/84,31,左单旋转,A,C,h,h,h,B,D,E,初始状态,插入后失衡,调整后平衡,32/84,32,右单旋转,A,h,h,h,D,E,B,C,A,h+1,h,h,D,E,B,C,初始状态,插入后失衡,调整后平衡,33/84,33,先左后右旋转,插入失衡，最近的失衡点为A,34/84,34,先右后左旋转,围绕A的右孩子C右旋,35/84,AVL树的插入,向一棵高度平衡的AVL树中插入一个新结点时，如果树中某个结点的平衡因子的绝对值|balance|1,则出现了不平衡，需要做平衡化处理。,二叉树与树,35/66,36/84,36,平衡二叉搜索树插入操作举例,向AVL树中插入16,3,7,11,9,26,18,14,15的调整过程：,0,37/84,课堂练习,假定一组数据对象为（40，28，16，56，50，32，30，63），按次序插入每个对象生成一棵高度平衡的二叉搜索树。给出插入各结点后的树的形状。,二叉树与树,37/66,38/84,书 面 作 业,132页：4，5，6，7，13376页：15，18,
