第八章二叉搜索树

1、第八章第八章 二叉搜索树二叉搜索树 理解以有序集为基础的抽象数据类型字典。理解以有序集为基础的抽象数据类型字典。 理解用数组实现字典的方法。理解用数组实现字典的方法。 理解二叉搜索树的概念和实现方法。理解二叉搜索树的概念和实现方法。 掌握用二叉搜索树实现字典的方法。掌握用二叉搜索树实现字典的方法。 理解理解AVLAVL树的定义和性质。树的定义和性质。 掌握二叉搜索树的结点旋转变换及实现方法。掌握二叉搜索树的结点旋转变换及实现方法。 掌握掌握AVLAVL树的插入重新平衡运算及实现方法。树的插入重新平衡运算及实现方法。 掌握掌握AVLAVL树的删除重新平衡运算及实现方法。树的删除重新平衡运算及实现

2、方法。8.1 8.1 字典的定义字典的定义 字典是以有序集为基础的抽象数据类型。字典是以有序集为基础的抽象数据类型。 它支持以下运算：它支持以下运算： (1)Member(x)(1)Member(x)，成员运算。，成员运算。 (2)Insert(x)(2)Insert(x)，插入运算：将元素，插入运算：将元素x x插入集合。插入集合。 (3)Delete(x)(3)Delete(x)，删除运算：将元素，删除运算：将元素x x从从当前当前集合中删去。集合中删去。 (4)Predecessor(x)(4)Predecessor(x)，前驱运算：返回集合中小于，前驱运算：返回集合中小于x x的最大元

3、的最大元素。素。 (5)Successor(x)(5)Successor(x)，后继运算：返回集合中大于，后继运算：返回集合中大于x x的最小元素。的最小元素。 (6)Range(x(6)Range(x，y)y)，区间查询运算：返回集合中界于，区间查询运算：返回集合中界于x x和和y y之间，之间，即即x xz zy y的所有元素的所有元素z z组成的集合。组成的集合。 (7)Min( )(7)Min( )，最小元运算：返回当前集合中依线性序最小的，最小元运算：返回当前集合中依线性序最小的元素。元素。 2第八章第八章 二叉搜索树二叉搜索树 8.2 8.2 用数组实现字典用数组实现字典 用数组实

4、现字典与用数组实现字典的不同之处：用数组实现字典与用数组实现字典的不同之处： 可以利用线性序将字典中的元素从小到大依序存储在数组中，可以利用线性序将字典中的元素从小到大依序存储在数组中，通过数组下标来反映字典元素之间的序关系。通过数组下标来反映字典元素之间的序关系。 优点：优点： 可用可用二分法二分法高效地实现与线性序有关的一些运算。如：高效地实现与线性序有关的一些运算。如：Member(x) Member(x) ，Predecessor(x)Predecessor(x)和和 Successor(x)Successor(x)可在时间可在时间O(logn)O(logn)内实现。内实现。 缺点：缺

5、点： 插入和删除运算的效率较低。插入和删除运算的效率较低。 每执行一次每执行一次InsertInsert或或DeleteDelete运算，需要移动部分数组元素，从而导致运算，需要移动部分数组元素，从而导致它们在最坏情况下的计算时间为它们在最坏情况下的计算时间为O(n)O(n)。 考虑：能否用链表来实现字典？考虑：能否用链表来实现字典？ MemberMember运算需要运算需要O(n)O(n)时间，时间，一旦找到元素在链表中插入或删除的位置一旦找到元素在链表中插入或删除的位置后，只要用后，只要用O(1)O(1)时间就可完成插入或删除操作。时间就可完成插入或删除操作。 两种实现方式均不可取！两种实

6、现方式均不可取！第八章第八章 二叉搜索树二叉搜索树 8.3 8.3 用二叉搜索树实现字典用二叉搜索树实现字典8.3.1 8.3.1 基本思想：基本思想： 用二叉树来存储有序集，每一个结点存储一个元素。用二叉树来存储有序集，每一个结点存储一个元素。 满足：满足：存存储储于每个结点中的元素于每个结点中的元素x x大于其左子树中任一结点大于其左子树中任一结点中所存中所存储储的元素，小于其右子树中任一结点中所存的元素，小于其右子树中任一结点中所存储储的元素的元素。4第八章第八章 二叉搜索树二叉搜索树 例例 10， 18， 3， 8， 12， 2， 7， 410101810183101838101838

7、12210183812710183812247101838122二叉搜索树的建立过程：二叉搜索树的建立过程：运算运算Insert(const T& x)Insert(const T& x)的实现：的实现：templatetemplateBinaryTreeNodeBinaryTreeNode* * BSTree:Insert(const T& x) BSTree:Insert(const T& x)BinaryTreeNode BinaryTreeNode * *p = root, p = root, * *pp = 0; pp = 0; /从根开始检测从根开始

8、检测插入位置插入位置, , * *pppp记录记录插入插入结点结点的父结的父结点点 while (p) /pwhile (p) /p非空，选择其左或右子树进行插入非空，选择其左或右子树进行插入 pp = p;pp = p; if (x data) if (x data) p = p-LeftChild;p = p-LeftChild; else if (x p-data)else if (x p-data)p = p-RightChild;p = p-RightChild; else else return 0 ; return 0 ; /表明表明x x在树中，无需插入在树中，无需插入 Bin

9、aryTreeNode BinaryTreeNode * *r = new BinaryTreeNode (x);r = new BinaryTreeNode (x);if (root) /if (root) /当前树非空当前树非空 /确定确定x x作为作为* *pppp的左儿子还是右儿子的左儿子还是右儿子 if (x data)if (x data)pp-LeftChild = r;pp-LeftChild = r; else else pp-RightChild = r;pp-RightChild = r; r-Parent = pp; r-Parent = pp; else else r

10、oot = r;root = r;return r;return r; / / Insert(x)Insert(x)运算结束运算结束运算运算Insert(const T& x)Insert(const T& x)的实现：的实现：运算运算Search(const T& x) Search(const T& x) 的实现的实现templatetemplateBinaryTreeNodeBinaryTreeNode* * BSTree:Search(const T& x) BSTree:Search(const T& x) constconst / /

11、找指向找指向x x所在的结点的指针所在的结点的指针 BinaryTreeNode BinaryTreeNode * *p = root;p = root; while (p) /while (p) /* *p p中有元素中有元素if (x data) if (x data) p = p-LeftChild;p = p-LeftChild; else if (x p-data) else if (x p-data) p = p-RightChild;p = p-RightChild; else else break; /break; /找到找到x x所在的结点所在的结点* *p p return

12、 p; /return p; /当当x x不在树中时不在树中时p p为空为空 删除删除508060120110150557053删除删除6080551201101505370805012060110150557053删除删除43例例80501206011015055705343运算运算Delete(const T& x)的实现的实现运算运算Delete(const T& x)的实现（续）的实现（续）设要删除二叉搜索树中的设要删除二叉搜索树中的结点结点p p ，分三种情况：，分三种情况：p p为叶结点为叶结点 直接删除节点直接删除节点p pp p只有左子树或右子树只有左子树或右子

13、树p p只有左子树只有左子树 用用p p的左儿子代替的左儿子代替p p p p只有右子树只有右子树 用用p p的右儿子代替的右儿子代替p pp p左、右子树均非空左、右子树均非空找找p p的的左子树的最大元素结点（即左子树的最大元素结点（即p的前驱结的前驱结点），用该结点代替结点点），用该结点代替结点p，然后删除该结点。，然后删除该结点。运算运算Delete(const T& x)Delete(const T& x)的实现（续）的实现（续）templatetemplateBinaryTreeNodeBinaryTreeNode* * BSTree:Delete(const T&

14、amp; x) BSTree:Delete(const T& x)BinaryTreeNode BinaryTreeNode * *p = root, p = root, * *pp = 0; pp = 0; / /从根开始搜索值为从根开始搜索值为x x的结点的结点, ,* *pppp记该结点记该结点的父的父结点结点while(p&p-data !=x)while(p&p-data !=x) pp = p;pp = p; if (x data)if (x data)p = p-LeftChild;p = p-LeftChild; elseelsep = p-RightC

15、hild;p = p-RightChild; if (!p)if (!p)return 0; /xreturn 0; /x不在树中不在树中, ,无需删除无需删除 if (p-LeftChild&p-RightChild) /pif (p-LeftChild&p-RightChild) /p有有2 2个儿子结点个儿子结点 / / 找真正要删除的结点找真正要删除的结点: :左子树的最大元素左子树的最大元素结点结点BinaryTreeNode BinaryTreeNode * *s = p-LeftChild,s = p-LeftChild, * *ps = p; ps = p; w

16、hile(s-RightChild)while(s-RightChild) ps=s;ps=s;s = s-RightChild;s = s-RightChild; p-data=s-data; / p-data=s-data; / 实现实现x x的删除（替代）的删除（替代） p = s;p = s;pp = pspp = ps / / 此时此时p p 最多只有最多只有1 1个儿子结点个儿子结点, ,正是要删除的结点正是要删除的结点BinaryTreeNode BinaryTreeNode * *c; c; if (p-LeftChild)if (p-LeftChild) c = p-Left

17、Child; /cc = p-LeftChild; /c保存保存p p唯一唯一的左儿子的左儿子else else c = p-RightChild;c = p-RightChild;/ c/ c保存保存p p唯一唯一的右儿子的右儿子if (p = root)if (p = root) root = c;root = c;if (c) c-Parent = 0; if (c) c-Parent = 0; elseelse / / 确定确定p p是其父结点的左儿子还是右儿子是其父结点的左儿子还是右儿子if (p = pp-LeftChild)if (p = pp-LeftChild) pp-Lef

18、tChild = c; pp-LeftChild = c;elseelse pp-RightChild = c; pp-RightChild = c; if (c) if (c) c-Parent = p-Parent; c-Parent = p-Parent; delete p;delete p;return c; return c; /Delete(x) /Delete(x)运算结束运算结束 用二叉搜索树实现字典用二叉搜索树实现字典时间复杂性分析时间复杂性分析 最坏最坏情况分析情况分析member,insert,deletemember,insert,delete都需要都需要O(n)O(n

19、) 平均情况分析平均情况分析引入记号引入记号: :记：记：p(n)p(n)为含有为含有n n个结点的二叉搜索树的平均查找长度。个结点的二叉搜索树的平均查找长度。显然显然p(0)=0,p(1)=1;p(0)=0,p(1)=1; 若设某二叉搜索树的左子树有若设某二叉搜索树的左子树有i i个结点，则：个结点，则：p(i)+1p(i)+1为查找左子树中每个结点的平均查找长度为查找左子树中每个结点的平均查找长度; ;p(n-i-1)+1p(n-i-1)+1为查找右子树中每个结点的平均查找长度；为查找右子树中每个结点的平均查找长度；由此构造而得的二叉搜索树在由此构造而得的二叉搜索树在n n个结点的查找概率

20、相等的个结点的查找概率相等的情况下，其平均查找长度为：情况下，其平均查找长度为： ) 1(111)(11),(inpinipininq) 1) 1()(1() 1)(1 (1(1) ),(1)(1010niniinpinipinninqnnp102)1()1()(11niinpiniipn对对n用数学归纳法可以证明用数学归纳法可以证明:nnplog41)(又假设又假设当前的二叉搜索树有当前的二叉搜索树有n个结点，而它是从空树开始反复个结点，而它是从空树开始反复调用调用n次的次的Insert运算得到的，且被插入的运算得到的，且被插入的n个元素的所有可能个元素的所有可能的顺序是等概率的。则：的顺序

21、是等概率的。则：102)(21niiipniiplog41)(当当n=1时显然成立。若设时显然成立。若设in时有时有 ，则，则112)log41(21)(niiinnp平均情况下的时间复杂度为：平均情况下的时间复杂度为：)(log nO1121122log421niniiniin112log82niiin)log)2/log(8212/12/12nninininin)log83)2/log(8(82222nnnnn)8log2(82222nnnnnlog41 运算运算Predecessor(x)Predecessor(x)和和Successor(x)Successor(x)的实现：的实现： 类

22、似于类似于Search(x)Search(x)算法算法 运算运算Range(y, z)Range(y, z)的实现：可借助于的实现：可借助于Search(y)Search(y)和和Successor(y)Successor(y)运算运算 首先，用首先，用Search(y)Search(y)检测检测y y是否在二叉搜索树中，是是否在二叉搜索树中，是则输出则输出y y，否则不输出，否则不输出y y； 然后，从然后，从y y开始，不断地用开始，不断地用SuccessorSuccessor找当前元素在找当前元素在二叉搜索树中的后继元素。当找出的后继元素二叉搜索树中的后继元素。当找出的后继元素x x满满

23、足足x x z z时，就输出时，就输出x x，并将，并将x x作为当前元素。重复作为当前元素。重复这个过程，直到找出的当前元素的后继元素大于这个过程，直到找出的当前元素的后继元素大于z z，或二叉搜索树中已没有后继元素为止。或二叉搜索树中已没有后继元素为止。 时间复杂度：若二叉树搜索树中有时间复杂度：若二叉树搜索树中有r r个元素个元素x x满足满足y y x x z z，则在最坏情况下用，则在最坏情况下用 时间，在时间，在平均情况下用平均情况下用 时间可实现时间可实现RangeRange运算。运算。 )(rnO)log(nrO 运算运算Range(y,z)Range(y,z)的改进：的改进：

24、考虑半无限查询区域考虑半无限查询区域 , 即找出二叉搜索树中满足即找出二叉搜索树中满足y x的所有元素的所有元素x。 ),y当当y不在二叉搜索树中时，不在二叉搜索树中时，产生一条从根到叶的路径。产生一条从根到叶的路径。如下图如下图(a) 当当y在二叉搜索树中时，产在二叉搜索树中时，产生一条从根到存储元素生一条从根到存储元素y的的结点的路径。如下图结点的路径。如下图(b) 在找到的搜索路径上的所有结点可分为以下在找到的搜索路径上的所有结点可分为以下3 3种情况，如下图种情况，如下图 ： 运算运算Range(y,z)Range(y,z)的实现：的实现： 可用类似于可用类似于Range(y,Rang

25、e(y,) )算法算法 从二叉搜索树的根结点开始，同时与从二叉搜索树的根结点开始，同时与y y和和z z比较比较, ,此时此时, ,结点分类结点分类的情况可能有（见下图）的情况可能有（见下图） ： 运算运算Range(y,z)Range(y,z)的搜索路径如下图：的搜索路径如下图： 8.4 AVL树8.4.0 8.4.0 引言引言AVLAVL树产生的背景树产生的背景 问题的提出问题的提出: :用二叉搜索树实现有序字典在用二叉搜索树实现有序字典在最坏情况下最坏情况下 member,insert,delete member,insert,delete都都需要需要O(n);O(n);平均情况下需要平

26、均情况下需要O(log n )O(log n )。 问在最坏情况下能降到问在最坏情况下能降到O(log n )O(log n )吗？吗？8.4 AVL树8.4.0 8.4.0 引言引言AVLAVL树产生的背景树产生的背景( (续续) ) 解决问题的设想解决问题的设想: : n n个结点的二叉树最矮是近似满二叉树个结点的二叉树最矮是近似满二叉树, ,其高为其高为log n log n 。若放宽此限制为每一个结点的左子树与右子树高度差的绝对若放宽此限制为每一个结点的左子树与右子树高度差的绝对值不超过值不超过1 1，则二叉树当然就达不到最矮，则二叉树当然就达不到最矮, ,却可望接近最矮却可望接近最矮

27、, ,而不超过而不超过O(log n),O(log n),目的就达到了。这正是目的就达到了。这正是AVLAVL树树。剩下的问。剩下的问题是设法找一种在题是设法找一种在insertinsert和和deletedelete后只需后只需O(log n)O(log n)时间的时间的维护算法。维护算法。 设想的证实设想的证实: : (1) (1) n n个结点的个结点的AVLAVL树树的高度的高度为为O(log n );O(log n );(2) insert(2) insert和和deletedelete后的后的维护算法在最坏的情况下只需维护算法在最坏的情况下只需O(logn )O(logn )的时间

28、。的时间。8.4 AVL8.4 AVL树树8.4.1 8.4.1 AVLAVL树的定义和性质树的定义和性质 递归定义递归定义: : 空的和单结点的二叉搜索树都是空的和单结点的二叉搜索树都是AVLAVL树树; ; 结点数大于结点数大于1 1的的二叉搜索树二叉搜索树, ,若满足左子树和右子树都是若满足左子树和右子树都是AVLAVL树且左、右树且左、右子树高度之差的绝对值不超过子树高度之差的绝对值不超过1,1,那么那么, ,它是它是AVLAVL树。树。 性质性质: : (1)AVL (1)AVL树树T T的结点数的结点数n n与高度与高度h h的关系。的关系。 设高度设高度h h的的AVLAVL树的

29、最少结点数树的最少结点数N(h)N(h)。N(h)N(h)一定出现在树一定出现在树的左、右子树中一棵高为的左、右子树中一棵高为h-1,h-1,而另一棵高为而另一棵高为h-2h-2时。则时。则N(h)N(h)满足如下递归方程：满足如下递归方程： 11)2() 1(1201)(hhNhNhhhN8.4 AVL8.4 AVL树树15/2/ ) 51 (2/ ) 51 (1) 2()(22hhhFhN15/515/2/ )51 (2/ )51 (222hhh25/2/ ) 51 ()(2hhNn5log)2(log2251251nh328. 0)2log(4404. 125log)2(log25125

30、1nnh 解上面的递归方程得：解上面的递归方程得：由于由于因此因此8.4 AVL8.4 AVL树树8.4.2 8.4.2 旋转变换旋转变换 旋转变换的目的：是调整结点的子树高度，并维持旋转变换的目的：是调整结点的子树高度，并维持二叉搜索树性质，即结点中元素的中序性质。二叉搜索树性质，即结点中元素的中序性质。 旋转变换分为单旋转变换和双旋转变换旋转变换分为单旋转变换和双旋转变换2 2种类型。种类型。 单旋转变换又分为右单旋转变换和左单旋转变换。单旋转变换又分为右单旋转变换和左单旋转变换。双旋转变换又分为先左后右双旋转变换和先右后左双旋转变换又分为先左后右双旋转变换和先右后左双旋转变换。双旋转变换

31、。1、左单旋的情况、左单旋的情况原来的原来的AVL树树插入一结点，插入一结点，A点不平衡点不平衡左单旋的结果左单旋的结果2.右单旋的情况右单旋的情况原来的原来的AVL树树插入一结点，插入一结点，A点不平衡点不平衡右单旋的结果右单旋的结果原来的原来的AVL树树插入一结点，插入一结点，A点不平衡点不平衡先左旋先左旋再右旋再右旋3.先左后右双旋的情况先左后右双旋的情况4.先右后左双旋的情况先右后左双旋的情况原来的原来的AVL树树插入一结点，插入一结点，A点不平衡点不平衡先右旋先右旋再左旋再左旋8.4 AVL8.4 AVL树树8.4.3 AVL8.4.3 AVL树的插入运算树的插入运算 AVLAVL树

32、与二叉搜索树的插入运算是类似的。惟一的不树与二叉搜索树的插入运算是类似的。惟一的不同之处是，在同之处是，在AVLAVL树中执行树中执行1 1次二叉搜索树的插入运次二叉搜索树的插入运算，可能会破坏算，可能会破坏AVLAVL树的高度平衡性质，因此需要重树的高度平衡性质，因此需要重新平衡。新平衡。设新插入的结点为设新插入的结点为v v。从根结点到结点。从根结点到结点v v的路径上，的路径上，每个结点处插入运算所进入的子树高度可能增每个结点处插入运算所进入的子树高度可能增1 1。因。因此在执行此在执行1 1次二叉搜索树的插入运算后，需从新插入次二叉搜索树的插入运算后，需从新插入的结点的结点v v开始，

33、沿此插入路径向根结点回溯，修正平开始，沿此插入路径向根结点回溯，修正平衡因子，调整子树高度，恢复被破坏的平衡性质。衡因子，调整子树高度，恢复被破坏的平衡性质。 8.4 AVL8.4 AVL树树8.4.3 AVL8.4.3 AVL树的插入运算树的插入运算 新结点新结点v v的平衡因子为的平衡因子为0 0。现考察。现考察v v的父结点的父结点u u。若。若v v是是u u的左的左儿子结点，则儿子结点，则bal(u)bal(u)应当减应当减1 1，否则，否则bal(u)bal(u)应当增应当增1 1。根据。根据修正后的修正后的bal(u)bal(u)的值分以下的值分以下3 3种情形讨论。种情形讨论。

34、 情形情形1 1：bal(u)=0bal(u)=0。此时以结点。此时以结点u u为根的子树平衡，且其高为根的子树平衡，且其高度不变。因此从根结点到结点度不变。因此从根结点到结点u u的路径上各结点子树高度不的路径上各结点子树高度不变，从而各结点的平衡因子不变。此时可结束重新平衡过变，从而各结点的平衡因子不变。此时可结束重新平衡过程。程。 情形情形2 2：| bal(u) | = 1| bal(u) | = 1。此时以结点。此时以结点u u为根的子树满足平为根的子树满足平衡条件，但其高度增衡条件，但其高度增1 1。此时将当前结点向根结点方向上移，。此时将当前结点向根结点方向上移，继续考察结点继续

35、考察结点u u的父结点的平衡状态。的父结点的平衡状态。8.4 AVL8.4 AVL树树 情形情形3 3：| bal(u) | = 2| bal(u) | = 2。 先讨论先讨论bal(u)=-2bal(u)=-2的情的情形。易知，此时结点形。易知，此时结点v v是结点是结点u u的左儿子结点，且的左儿子结点，且bal(v)bal(v) 0 0。又可分为。又可分为2 2种情形。种情形。 情形情形3.13.1：bal(v)=-1bal(v)=-1。此时作。此时作1 1次右单旋转变换后，结次右单旋转变换后，结束重新平衡过程。束重新平衡过程。 情形情形3.23.2：bal(v)=1bal(v)=1。此

36、时结点。此时结点v v的右儿子结点的右儿子结点x x非空。非空。根据根据bal(x)bal(x)的值，又分为的值，又分为bal(x)=0bal(x)=0、bal(x)=-1bal(x)=-1和和bal(x)=1bal(x)=1的的3 3种情形。在这种情形。在这3 3种情形下，分别作种情形下，分别作1 1次双旋次双旋转变换后，结束重新平衡过程。转变换后，结束重新平衡过程。情形情形3.1： 情形情形3.2 ： bal(x)=0情形情形3.2 ： bal(x)=-1情形情形3.2 ： bal(x)=18.4 AVL8.4 AVL树树8.4.4 AVL8.4.4 AVL树的删除运算树的删除运算 AVL

37、AVL树与二叉搜索树的删除运算是类似的。惟一的不同之树与二叉搜索树的删除运算是类似的。惟一的不同之处是，在处是，在AVLAVL树中执行树中执行1 1次二叉搜索树的删除运算，可能会次二叉搜索树的删除运算，可能会破坏破坏AVLAVL树的高度平衡性质，因此需要重新平衡。树的高度平衡性质，因此需要重新平衡。设被删除结点为设被删除结点为p p，其惟一的儿子结点为，其惟一的儿子结点为v v。结点。结点p p被删除被删除后，结点后，结点v v取代了它的位置。从根结点到结点取代了它的位置。从根结点到结点v v的路径上，的路径上，每个结点处删除运算所进入的子树高度可能减每个结点处删除运算所进入的子树高度可能减1 1。因此在。因此在执行执行1 1次二叉搜索树的删除运算后，需从结点次二叉搜索树的删除运算后，需从结点v v开始，沿此开始，沿此删除路径向根结点回溯，修正平衡因子，调整子树高度，删除路径向根结点回溯，修正平衡因子，调整子树高度，恢复被破坏的平衡性质。恢复