湘潭大学 数据结构 Ch04 Trees

1、编辑编辑pptppt第四章 树编辑编辑pptppt1 预备知识预备知识 客观世界中许多事物存在层次关系客观世界中许多事物存在层次关系 人类社会家谱人类社会家谱 社会组织结构社会组织结构 图书信息管理图书信息管理编辑编辑pptppt哲学宗教哲学宗教文学文学医药卫生医药卫生农业科学农业科学工业技术工业技术哲学理论哲学理论世界哲学世界哲学欧洲哲学欧洲哲学宗教宗教宗教分析研究宗教分析研究宗教理论与概况宗教理论与概况佛教佛教宗教与社会政治宗教与社会政治宗教与科学宗教与科学破除迷信破除迷信综合综合电工技术电工技术计算机计算机建筑科学建筑科学水利工程水利工程一般性技术一般性技术计算机软件计算机软件电子模拟计

2、算机电子模拟计算机微型计算机微型计算机计算机的应用计算机的应用图书图书软件工程软件工程程序语言程序语言编译程序编译程序操作系统操作系统编辑编辑pptppt1 预备知识预备知识【定义定义】树是一些节点的集合。这个集合可以是空集；若非树是一些节点的集合。这个集合可以是空集；若非空，则树包含：空，则树包含： (1) 一个被称为一个被称为根根的特殊节点的特殊节点 r; (2) 以及以及0个或多个非空个或多个非空（子）树（子）树 T1, , Tk，每一棵子树的根，每一棵子树的根都被来自根都被来自根 r 的一条有向边的一条有向边（ edge）所连接。所连接。Note: 子树是不相交的。因此树中的每一个节点

3、都是一棵子子树是不相交的。因此树中的每一个节点都是一棵子树的根。树的根。 一棵有一棵有N个节点的树中有个节点的树中有 条边。条边。 根节点通常画在上方。根节点通常画在上方。N 1编辑编辑pptpptACBDGFEHIJMLK 节点的度（节点的度（Degree）:= 节点的子树个数。节点的子树个数。 例如例如, degree(A) = 3, degree(F) = 0. 树的度树的度:= 例如例如, degree of this tree = 3. )node(degreemaxtreenode 叶节点叶节点（leaf）:= 度为度为0的节点的节点 (没有孩子没有孩子)。 父节点（父节点（Par

4、ent） := 有子树的节点是有子树的节点是其子树根节点的父节点。其子树根节点的父节点。 子节点（子节点（Child） := 若若A节点是节点是B节点的父节点，则节点的父节点，则B节点是节点是A节点节点的子节点，也叫的子节点，也叫孩子节点孩子节点。 兄弟节点兄弟节点（sibling） := 具有同一父节点的各节点彼此是兄弟节点。具有同一父节点的各节点彼此是兄弟节点。1 预备知识预备知识1. 术语术语编辑编辑pptppt1 预备知识预备知识ACBDGFEHIJMLK 祖先结点祖先结点(Ancestor) :=沿沿树根到某一结点路径树根到某一结点路径上的所有结点都是上的所有结点都是这个结点的祖先结

5、点。这个结点的祖先结点。 子孙结点子孙结点(Descendant) :=某一结点的某一结点的子树中的所有结点子树中的所有结点是这个是这个结点的子孙。结点的子孙。 ni的深度的深度:= 从根到从根到ni 唯一的路径的长度。唯一的路径的长度。 Depth(root) = 0. ni的高度的高度:= 从从ni 到一片叶子的最长路径的长度。到一片叶子的最长路径的长度。Height(leaf) = 0, height(D) = 2. 树的高度（深度）树的高度（深度）:= height(root) = depth(deepest leaf). 从从n1 到到 nk 的路径的路径 :=从结点从结点n1到到n

6、k的路径被定的路径被定义为一个结点序列义为一个结点序列n1 , n2 , , nk ，对于，对于1 i k, ni是是 ni+1的父结点。的父结点。 路径长度路径长度:=一条路径的长度为这条路径所一条路径的长度为这条路径所包含的边包含的边（分支）的个数（分支）的个数。编辑编辑pptppt2. 树的实现树的实现 链表表示法链表表示法ACBDGFEHIJMLKABCDEFGHIJKLM因此，每个节点的大小取决于因此，每个节点的大小取决于子树数目。噢，这样并不太好！子树数目。噢，这样并不太好！1 预备知识预备知识编辑编辑pptppt 儿子儿子-兄弟表示法兄弟表示法FirstChild NextSib

7、lingElementACBDGFEHIJMLKNACBNDENKN NFN NGHNIN NJN NLN NMNote: 这种表示法这种表示法并非唯一并非唯一的，因为树的节点的孩子顺序的，因为树的节点的孩子顺序是不固定的。是不固定的。1 预备知识预备知识编辑编辑pptppt 树的遍历树的遍历 访问每个节点恰好一次访问每个节点恰好一次 前序前序遍历遍历void preorder ( tree_ptr tree ) if ( tree ) visit ( tree ); for (each child C of tree ) preorder ( C ); 编辑编辑pptppt例例1 列出分级文

8、件系统中的目录。列出分级文件系统中的目录。输出格式输出格式: 深度深度为为 di 的文件的名字将被的文件的名字将被 di 次跳格次跳格(tab)缩进后打印出缩进后打印出来。来。/usrmarkalexbillbookcoursehw.chw.ccourseworkch1.cch2.cch3.ccop3530fall96spr97 sum97syl.rsyl.rsyl.rcop3212fall96fall97gradesgradesp1.rp2.rp1.rp2.rUnix directory编辑编辑pptppt/usr mark bookCh1.cCh2.cCh3.c coursecop3530

9、 fall96syl.r spr97syl.r sum97syl.r hw.c alex hw.c bill work coursecop3212 fall96gradesp1.rp2.r fall97p2.rp1.rgradesstatic void ListDir ( DirOrFile D, int Depth ) if ( D is a legitimate entry ) PrintName (D, Depth ); if ( D is a directory ) for (each child C of D ) ListDir ( C, Depth + 1 ); Note: 深度深

10、度(Depth)是一个内部簿记变量，是一个内部簿记变量，而不是主调例程能够期望知道的那种参而不是主调例程能够期望知道的那种参数，因此，驱动例程数，因此，驱动例程ListDirectory用于用于将递归例程和外界连接起来。将递归例程和外界连接起来。void ListDirectory ( DirOrFile D )ListDir( D, 0 ); T ( N ) = O( N )编辑编辑pptppt 后序后序遍历遍历void postorder ( tree_ptr tree ) if ( tree ) for (each child C of tree ) postorder ( C ); v

11、isit ( tree ); 编辑编辑pptppt例例2 计算一个目录的大小。计算一个目录的大小。/usrmarkalexbillbookcoursehw.chw.ccourseworkch1.cch2.cch3.ccop3530fall96spr97sum97syl.rsyl.rsyl.rcop3212fall96fall97gradesgradesp1.rp2.rp1.rp2.rUnix directory with 11111111111111132468152341279static int SizeDir ( DirOrFile D ) int TotalSize; TotalSiz

12、e = 0; if ( D is a legitimate entry ) TotalSize = ( D ); if ( D is a directory ) for (each child C of D ) TotalSize += SizeDir(C); /* end if D is legal */ return TotalSize;T ( N ) = O( N )编辑编辑pptppt 层序层序遍历遍历void levelorder ( tree_ptr tree ) enqueue ( tree ); while (queue is not empty) visit ( T = de

13、queue ( ) ); for (each child C of T ) enqueue ( C ); 2453671112 324 536 745 6 7编辑编辑pptppt2 二叉树二叉树【定义定义】一棵二叉树一棵二叉树T是一个有穷的结点集合。这个集合是一个有穷的结点集合。这个集合可以为可以为空空，若不为空，则它是由，若不为空，则它是由根结点根结点和称为其和称为其左子树左子树TL和和右子树右子树TR的的两个不相交的二叉树组成。可见两个不相交的二叉树组成。可见左子树和右子树还是二叉树左子树和右子树还是二叉树。 二叉树具体五种基本形态二叉树具体五种基本形态（1）空空二叉树；二叉树；（2）只有

14、根只有根结点的二叉树；结点的二叉树；（3）只有）只有根结点和左子树根结点和左子树TL的二叉树；的二叉树；（4）只有）只有根结点和右子树根结点和右子树TR的二叉树；的二叉树；（5）具有）具有根结点、左子树根结点、左子树TL和右子树和右子树TR的二叉树。的二叉树。TLTRTLTR (a) (b) (c) (d) (e)递归的定义形式递归的定义形式 二叉树二叉树与树不同，除了每个结点至多有两棵子树外，与树不同，除了每个结点至多有两棵子树外，子子树树有左右顺序之分有左右顺序之分。 例如，例如，下面下面两个树按一般树的定义它们是两个树按一般树的定义它们是同一个树同一个树；而对而对于二叉树来讲，它们是于二

15、叉树来讲，它们是不同的两个树不同的两个树。编辑编辑pptppt1616 特殊特殊二叉树二叉树 二叉树的深度小于结点数二叉树的深度小于结点数N，可以证明平均深度是，可以证明平均深度是)NO( “完美二叉树完美二叉树(Perfect Binary Tree)”。（也称为。（也称为满二叉树满二叉树）。）。BACBCDEHIJFG 一棵深度为一棵深度为k的有的有n个结点的二叉树，对树中的结点按从上至下、个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为从左到右的顺序进行编号，如果编号为i（1 i n）的结点与满二）的结点与满二叉树中编号为叉树中编号为

16、i 的结点在二叉树中的位置相同，则这棵二叉树称为的结点在二叉树中的位置相同，则这棵二叉树称为“完全二叉树完全二叉树(Complete Binary Tree)”。1211KL151413MNO “斜二叉树斜二叉树(Skewed Binary Tree)”（也称为退化二叉树）；（也称为退化二叉树）BCDEHKJFG2 二叉树二叉树编辑编辑pptppt1717 二叉树二叉树的几个的几个重要的性质重要的性质 一个二叉树第一个二叉树第 i 层的最大结点数为：层的最大结点数为：2 i-1，i 1。 对任何非空的二叉树对任何非空的二叉树 T，若，若n0表示叶结点的个数、表示叶结点

17、的个数、n2是度为是度为2的非叶结点个数，那么两者满足关系的非叶结点个数，那么两者满足关系n0 = n2 +1。 深度为深度为k的二叉树有最大结点总数为：的二叉树有最大结点总数为：2 k-1，k 1。ABCDEKJFH n0 = 4，n1 = 2 n2 = 3 n0 = n2 +1证明证明: 设设 n1 是度为是度为1结点数结点数, n 是总的结点数是总的结点数. 那么那么 n = 210nnn 设设 B 是全部分枝数是全部分枝数. 则则 n B?n = B + 1.因为所有分枝都来自度为因为所有分枝都来自度为1或或2的结点的结点, 所以所以 B n1 & n2 ?B = n1 + 2

18、 n2. 123 n0 = n2 + 1 n个结点的完全二叉树的深度为个结点的完全二叉树的深度为k 为为 ：2 二叉树二叉树编辑编辑pptppt1818 二叉树的存储结构二叉树的存储结构1. 顺序顺序存储结构存储结构 完全二叉树完全二叉树最适合这种存储结构。最适合这种存储结构。 n个结点的个结点的完全二叉树的完全二叉树的结点父子关系结点父子关系，简单地由，简单地由序列号序列号决定：决定：(b) 完全完全二叉树二叉树(a)相应的相应的顺序顺序存储结构存储结构1、非根结点（序号、非根结点（序号 i 1）的）的父结点父结点的序号是的序号是 i / 2 ;2、结点（序号为、结点（序号为 i ）的）的左

19、孩子左孩子结点的序号是结点的序号是 2i， （若（若2 i = n，否则没有左孩子），否则没有左孩子）;3、结点（序号为、结点（序号为 i ）的）的右孩子右孩子结点的序号是结点的序号是 2i+1， （若（若2 i +1Left ); visit ( tree-Element ); inorder ( tree-Right ); 中序中序遍历遍历Iterative Programvoid iter_inorder ( tree_ptr tree ) Stack S = CreateStack( MAX_SIZE ); for ( ; ; ) for ( ; tree; tree = tree-L

20、eft ) Push ( tree, S ) ; tree = Top ( S ); Pop( S ); if ( ! tree ) break; visit ( tree-Element ); tree = tree-Right; 二叉树的遍历二叉树的遍历编辑编辑pptppt编辑编辑pptpptvoid preorder ( tree_ptr tree ) if ( tree ) visit ( tree-Element ); preorder ( tree-Left ); preorder ( tree-Right ); 先序先序遍历遍历void postorder ( tree_ptr

21、tree ) if ( tree ) postorder ( tree-Left ); postorder ( tree-Right ); visit ( tree-Element ); 后序后序遍历遍历编辑编辑pptppt例例 对表达式树进行遍历对表达式树进行遍历: A + B C D+A DBC 中序中序遍历遍历 A + B C D 后序后序遍历遍历 A B C D + 先序先序遍历遍历 + A B C D编辑编辑pptppt3 查找树查找树ADT 二叉查找树二叉查找树【定义定义】二叉查找树二叉查找树是一棵二叉树。可能为空，若非空，则满足以是一棵二叉树。可能为空，若非空，则满足以下性质：下

22、性质：每个结点有一个每个结点有一个整数关键字，整数关键字，且关键字且关键字互异。互异。非空非空左左子树上的结点关键字的值必须子树上的结点关键字的值必须小于小于子树的根结点的关键字子树的根结点的关键字值。值。非空非空右右子树上的结点关键字的值必须子树上的结点关键字的值必须大于大于子树的根结点的关键字子树的根结点的关键字值。值。(1) 左右子树也是二叉查找树。左右子树也是二叉查找树。305240201512251022607080651. 定义定义编辑编辑pptppt3 二叉查找树二叉查找树2. ADT数据元素集数据元素集: 一个有一个有0个或多个元素的有穷结点集合。个或多个元素的有穷结点集合。操

23、作集操作集: SearchTree MakeEmpty( SearchTree T ); Position Find( ElementType X, SearchTree T ); Position FindMin( SearchTree T ); Position FindMax( SearchTree T ); SearchTree Insert( ElementType X, SearchTree T ); SearchTree Delete( ElementType X, SearchTree T ); ElementType Retrieve( Position P ); 编辑编辑p

24、ptppt3 二叉查找树二叉查找树3. 实现实现 FindPosition Find( ElementType X, SearchTree T ) if ( T = NULL ) return NULL; /* not found in an empty tree */ if ( X Element ) /* if smaller than root */ return Find( X, T-Left ); /* search left subtree */ else if ( X T-Element ) /* if larger than root */ return Find( X, T-

25、Right ); /* search right subtree */ else /* if X = root */ return T; /* found */ T( N ) = S ( N ) = O( d ) d 是是X的深度的深度这个测试必须首先进行吗这个测试必须首先进行吗?它们是尾递归。它们是尾递归。如何消除？如何消除？编辑编辑pptppt3 二叉查找树二叉查找树Position Iter_Find( ElementType X, SearchTree T ) /* iterative version of Find */ while ( T ) if ( X = T-Element

26、) return T ; /* found */ if ( X Element ) T = T-Left ; /*move down along left path */ else T = T- Right ; /* move down along right path */ /* end while-loop */ return NULL ; /* not found */ 编辑编辑pptppt 查找最大和最小元素查找最大和最小元素 最大元素最大元素一定是在一定是在树的树的最右分枝的端结点最右分枝的端结点上上 最小元素最小元素一定是在树的一定是在树的最左分枝的端结点最左分枝的端结点上上181

27、015207229最左端点最左端点最右端点最右端点3 二叉查找树二叉查找树编辑编辑pptppt3 二叉查找树二叉查找树 FindMinPosition FindMin( SearchTree T ) if ( T = NULL ) return NULL; /* not found in an empty tree */ else if ( T-Left = NULL ) return T; /* found left most */ else return FindMin( T-Left ); /* keep moving to left */ FindMaxPosition FindMax

28、( SearchTree T ) if ( T != NULL ) while ( T-Right != NULL ) T = T-Right; /* keep moving to find right most */ return T; /* return NULL or the right most */ T( N ) = O ( d ) T( N ) = O ( d ) 编辑编辑pptppt3 二叉查找树二叉查找树 Insert305240算法梗概算法梗概:Insert 80 检查检查 80 是否已在树中；是否已在树中； 80 40, 所以它必定是所以它必定是40的右孩子。的右孩子。80

29、Insert 35 检查检查 35 是否在树中；是否在树中； 35 5, 所以它必定是所以它必定是5的右孩子。的右孩子。25这是我们搜索关键值时这是我们搜索关键值时遇到的最后一个结点。遇到的最后一个结点。它必定是这个新结点的父结点。它必定是这个新结点的父结点。分析分析将元素将元素X插入二叉搜索树中，关键是要找到元素应该插入插入二叉搜索树中，关键是要找到元素应该插入的的位置位置。位置的确定可以利用与查找函数。位置的确定可以利用与查找函数Find类似的方法，如果在类似的方法，如果在树树中找到中找到X，说明要插入的元素已存在，可放弃插入操作。如果，说明要插入的元素已存在，可放弃插入操作。如果没没找到

30、找到X，查找终止的位置就是，查找终止的位置就是X应插入的位置。应插入的位置。编辑编辑pptppt3 二叉查找树二叉查找树SearchTree Insert( ElementType X, SearchTree T ) if ( T = NULL ) /* Create and return a one-node tree */ T = malloc( sizeof( struct TreeNode ) ); if ( T = NULL ) FatalError( Out of space! ); else T-Element = X; T-Left = T-Right = NULL; /* E

31、nd creating a one-node tree */ else /* If there is a tree */ if ( X Element ) T-Left = Insert( X, T-Left ); else if ( X T-Element ) T-Right = Insert( X, T-Right ); /* Else X is in the tree already; well do nothing */ return T; /* Do not forget this line! */ 怎么处理重复值怎么处理重复值?T( N ) = O ( d ) 编辑编辑pptppt

32、3 二叉查找树二叉查找树 Delete 二叉搜索树的删除操作比其它操作更为复杂，有二叉搜索树的删除操作比其它操作更为复杂，有三种情况三种情况需要考虑：需要考虑： 要删除的是要删除的是叶结点叶结点可以直接删除，然后再修改其父结点的指针。可以直接删除，然后再修改其父结点的指针。图图1 二叉搜索树叶结点的二叉搜索树叶结点的删除删除301541335035要删除结点要删除结点例例1：删除：删除 35编辑编辑pptppt3636图图2 具有一个子树的结点删除具有一个子树的结点删除 要删除的结点要删除的结点只有一个孩子只有一个孩子结点结点删除之前需要改变其删除之前需要改变其父结点父结点的的指针，指针，指向

33、指向要删除结点的要删除结点的孩子结点孩子结点。要删除结点要删除结点（只有一个孩子）（只有一个孩子）3015415035333015415035例例2：删除：删除 333 二叉查找树二叉查找树编辑编辑pptppt3737图图3 具有两个子树的结点删除具有两个子树的结点删除 要删除的结点要删除的结点有左、右两棵子树有左、右两棵子树为了保持二叉搜索树的有序性，为了保持二叉搜索树的有序性，替代被删除的元素的位置可以有两种选择：一种是取其替代被删除的元素的位置可以有两种选择：一种是取其右子树中的最右子树中的最小元素小元素；另一个是取其；另一个是取其左子树中的最大元素左子树中的最大元素。415030153

34、33534例例3：删除：删除 41(a) 取取右子树右子树中的中的最小最小元素替代元素替代41353450301533(b) 取取左子树左子树中的中的最大最大元素替代元素替代编辑编辑pptppt3 二叉查找树二叉查找树SearchTree Delete( ElementType X, SearchTree T ) Position TmpCell; if ( T = NULL ) Error( Element not found ); else if ( X Element ) /* Go left */ T-Left = Delete( X, T-Left ); else if ( X T-

35、Element ) /* Go right */ T-Right = Delete( X, T-Right ); else /* Found element to be deleted */ if ( T-Left & T-Right ) /* Two children */ /* Replace with smallest in right subtree */ TmpCell = FindMin( T-Right ); T-Element = TmpCell-Element; T-Right = Delete( T-Element, T-Right ); /* End if */

36、else /* One or zero child */ TmpCell = T; if ( T-Left = NULL ) /* Also handles 0 child */ T = T-Right; else if ( T-Right = NULL ) T = T-Left; free( TmpCell ); /* End else 1 or 0 child */ return T; T( N ) = O ( h ) h 是树的高度。是树的高度。编辑编辑pptppt3 二叉查找树二叉查找树Note: 如果删除次数不多，那么如果删除次数不多，那么懒惰删除懒惰删除是可行的：为每是可行的：为每

37、个结点添加一个标识域，个结点添加一个标识域，标记标记结点是可用还是已被删除。结点是可用还是已被删除。因此我们可以删除一个结点而不实际地释放结点空间。因此我们可以删除一个结点而不实际地释放结点空间。如果被删除的结点重新插入，就不需要再次调用如果被删除的结点重新插入，就不需要再次调用malloc了。了。当树中被删除的结点数目当树中被删除的结点数目和活跃结点的数目相当时，和活跃结点的数目相当时，操作的效率会受到很大的影响吗？操作的效率会受到很大的影响吗？编辑编辑pptppt3 二叉查找树二叉查找树4. 平均情形分析平均情形分析问题问题: 若一棵二叉查找树中包含若一棵二叉查找树中包含 n 个元素，这棵

38、树有多高？个元素，这棵树有多高？答案答案: 树的高度依赖于插入的次序。树的高度依赖于插入的次序。例例 给定元素给定元素 1, 2, 3, 4, 5, 6, 7. 将它们按以下顺序插入将它们按以下顺序插入一棵二叉查找树：一棵二叉查找树：4, 2, 1, 3, 6, 5, 7 和和 1, 2, 3, 4, 5, 6, 74567213h = 22314567h = 6编辑编辑pptppt3 二叉查找树二叉查找树【定义定义】一棵包含一棵包含 N 个结点的树的个结点的树的内部路径长内部路径长被定义为被定义为：0)1(, )()(1 DidNDNid( i ) 是结点是结点 i 的的深度深度【定理定理】

39、 假设所有的二叉查找树是等概率出现的，那么平假设所有的二叉查找树是等概率出现的，那么平均的均的 D(N) (包括所有可能的输入序列包括所有可能的输入序列) 是是 O(N log N)。 因此任意结点的因此任意结点的期望期望深度是深度是 O(log N).证明证明: D( N ) = D( i ) + D( N i 1 ) + N 1rooti nodesN i 1 nodes+1由于所有的子树大小是等概率的，由于所有的子树大小是等概率的，因此因此 D( i ) 和和 D( N i 1 ) 的平均的平均值都是值都是. )(10NjDNj 1 )()(102 NjDNDNjN=p.212-213=

40、 O(N log N)编辑编辑pptppt4 AVL 树树目标目标: 加速搜索（包括插入和删除）。加速搜索（包括插入和删除）。工具工具: 二叉查找树二叉查找树rootsmalllarge问题问题 : 虽然虽然 Tp = O( height ), 但是但是height最坏情况最坏情况下可能高达下可能高达 O( N )。编辑编辑pptppt4 AVL 树树 例例不同的插入次序，将导致不同的不同的插入次序，将导致不同的深度深度和平均查找长度和平均查找长度ASL。 (a) 按一月到十二月的按一月到十二月的自然月份序列自然月份序列输入所生成的；输入所生成的； (b) 输入序列为输入序列为（July, F

41、eb, May, Mar, Aug, Jan, Apr, Jun, Oct, Sept, Nov, Dec） (c) 输入序列则是按输入序列则是按月份字符串月份字符串从小到大的顺序排列的。从小到大的顺序排列的。JanFebMarAprAugDecJuneJulyMaySeptOctNovJanFebMarAprAugDecJuneJulyMaySeptOctNovAprAugOctSept 按按ASL的定义，可以分别计算出三棵二叉搜索树的的定义，可以分别计算出三棵二叉搜索树的平均平均查找查找长度长度：ASL(a)=(1+22+33+43+52+61)/12 = 3.5；ASL(b)=(1+22

42、+34+45)/12 = 3.0；ASL(c)=(1+21+31+41+51+61+71+81+91+101+111+121)/12 = 6.5；编辑编辑pptppt4 AVL 树树【定义定义】一棵空的二叉树是高度平衡的。如果一棵空的二叉树是高度平衡的。如果 T 是一棵非空是一棵非空二叉树，有二叉树，有左子树左子树 TL 和右子树和右子树 TR, 那么那么 T 是是高度平衡的（高度平衡的（AVL树）树），当且仅当：，当且仅当： (1) TL 和和 TR 是高度平衡的是高度平衡的, 而且而且 (2) | hL hR | 1 ，hL 和和 hR 是是 TL 和和 TR 各自的高度各自的高度。【定义

43、定义】平衡因子平衡因子BF( node ) = hL hR 。在一棵。在一棵 AVL 树中树中, BF( node ) = 1, 0, 或或 1。582143778214354563217空树的高度定义为空树的高度定义为 1.编辑编辑pptppt4 AVL 树树例例1 输入月份输入月份MarMar0 1MayMay0NovNov0 1 2May0 1Nov0 0 2 1Mar0 00首个不平衡的首个不平衡的“发现者发现者”是是Mar（未必是根结点未必是根结点），它是调整起点位），它是调整起点位置。而置。而“麻烦结点麻烦结点”Nov 在发现者在发现者右右子树的子树的右边右边，因而叫，因而叫 RR

44、 插入插入，需要，需要RR 旋转（右单旋）；旋转（右单旋）；一般情况一般情况:A 1B0BLBRALRR插入插入RR旋转旋转A 2B 1BLBRALBLB0AALBR0A 不一定是树的根不一定是树的根Single rotation编辑编辑pptppt4 AVL 树树AugMay0 1Nov0 0 2 1Mar0 11Aug0AprApr0122LL旋转旋转May0 1Nov0 0 2 1Aug0 11 1Mar00Apr0一般情况一般情况:A1B0BRBLARLL插入插入A2B1BRBLARLL旋转旋转B0AARBLBR0 首个首个“发现者发现者”是是Mar； “麻烦结点麻烦结点”Apr 在发

45、现在发现者者左左子树的子树的左边左边，因而叫，因而叫 LL 插入；插入；编辑编辑pptppt4 AVL 树树May0 1Nov0 0 2 1Aug0 11 1Mar00Apr0JanJan01 12LR旋转旋转Mar0 1May0 1 2 1Aug0 10 1Jan00Apr0Nov0一般情况一般情况:A1B0BLARC0CRCLLR插入插入A2B 1BLARC 1CRCLORLR旋转旋转BLARC0A 1 or 0CRB0 or 1CLOR双旋转双旋转首个首个“发现者发现者”是是May； “麻烦结点麻烦结点”Jan在在左左子树的子树的右边右边，因而叫，因而叫 LR 插入插入；编辑编辑pptp

46、pt4 AVL 树树DecJulyMar0 1May0 1 2 1Aug0 11 1Jan0Apr0Nov0July0Dec0FebFeb0 11 22RL旋转旋转July0Dec0 1Aug0 1 2 1Jan0 10 1Feb00Apr0Mar0 1May0 1 2 1 1Nov0一般情况一般情况:A1B0BRALC0CLCRRL插入插入A 2B1BRALC 1CLCRORRL旋转旋转BRALC0A0 or 1CLB 1 or 0CROR编辑编辑pptppt4 AVL 树树July0Dec0 1Aug0 1 2 1Jan0 10 1Feb00Apr0Mar0 1May0 1 2 1 1No

47、v0JuneOctSeptJune0 1 1 12Nov0Dec0 1Aug1 2 1Feb01July 1Apr0Mar0May 1June0Jan0Oct0 1 2 1 1Oct0Dec0 1Aug1 2 1Feb01July 1Apr0Mar0Nov0June0Jan0May0Sept0 1 1 1 1Note: 有时候插入元素即便有时候插入元素即便不需要调整结构，也可能需要重新计算不需要调整结构，也可能需要重新计算一些平衡因子。一些平衡因子。另一个方法是为每一个结点保存一个另一个方法是为每一个结点保存一个 height 信息。信息。编辑编辑pptppt4 AVL 树树AvlTree I

48、nsert( ElementType X, AvlTree T ) if ( T = NULL ) /* Create and return a one-node tree */ T = malloc( sizeof( struct AvlNode ) ); if ( T = NULL ) FatalError( Out of space! ); else T-Element = X; T-Height = 0; T-Left = T-Right = NULL; /* End creating a one-node tree */ elseif ( X Element ) /* handle

49、left insertion */ T-Left = Insert( X, T-Left ); if ( Height( T-Left ) - Height( T-Right ) = 2 ) /* not balanced */ if ( X Left-Element ) /* LL Rotation */T = SingleRotateWithLeft( T ); else /* LR Rotation */T = DoubleRotateWithLeft( T ); /* End left */else if( X T-Element ) /* handle right insertion

50、 */T-Right = Insert( X, T-Right ); if ( Height( T-Right ) - Height( T-Left ) = 2 ) /* not balanced */ if ( X T-Right-Element ) /* RR Rotation */T = SingleRotateWithRight( T ); else /* RL Rotation */T = DoubleRotateWithRight( T ); /* End right */ /* Else X is in the tree already; well do nothing */ T

51、-Height = Max( Height( T-Left ), Height( T-Right ) ) + 1; return T; 编辑编辑pptppt4 AVL 树树最后一个问题最后一个问题: 查找和插入的时间复杂性查找和插入的时间复杂性 Tp = O( h ) 其中其中 h 是二叉树的高度，是二叉树的高度，但是，但是， h = ?设设 nh 为高度为为高度为h的平衡二叉树的最小结点数的平衡二叉树的最小结点数. 二叉树看起来应该是如二叉树看起来应该是如下结构形式：下结构形式：Ah 2h 1Ah 2h 1或或 nh = nh 1 + nh 2 + 1 斐波那契序列斐波那契序列: F0 =

52、0, F1 = 1, Fi = Fi 1 + Fi 2 for i 1 nh = Fh+2 1, for h 0斐波那契序列的理论值是：斐波那契序列的理论值是：iiF 25151)(ln1251512nOhnhh 编辑编辑pptppt nh = nh 1 + nh 2 + 1设设 nh 是高度为是高度为h的平衡二叉树的的平衡二叉树的最小结点数最小结点数. h nh Fh0 1 11 2 12 4 23 7 34 12 55 20 86 33 137 54 218 88 349 nh = Fh+2 1, （对（对 h 0） 给定结点数为给定结点数为 n的的AVL树的树的最大高度为最大高度为O(l

53、og2n)！ )(lnnOh 1251512hhn 从而保证了从而保证了AVL树的树的查找时间性能为查找时间性能为O(log2n)！ 4 AVL 树树编辑编辑pptppt5 伸展树伸展树目标目标 : 任意任意 M 次从空树开始连续的操作最多花费次从空树开始连续的操作最多花费 O(M log N) 的时间。的时间。 这是否意味着每个操作只需这是否意味着每个操作只需花费花费O(log N) 时间时间?不，这意味着不，这意味着摊还摊还时间时间是是 O(log N). 所以单次操作可能仍需要所以单次操作可能仍需要 花费花费 O(N) 时间时间? 那么，重点是什么？那么，重点是什么？这个界是很弱的，但效

54、果是相同的：这个界是很弱的，但效果是相同的：不存在不存在坏的坏的输入序列。输入序列。 但是，如果一个结点需要但是，如果一个结点需要 O(N) 时间去访问，时间去访问， 我们可以持续访问它我们可以持续访问它 M 次次, 对吗？对吗？ 我们当然可以我们当然可以 那只是意味着那只是意味着 任何时候结点被访问后必须被任何时候结点被访问后必须被移动移动。Idea : 一个结点被访问后，它将通过一系列的一个结点被访问后，它将通过一系列的AVL树的旋转操作被推至树的旋转操作被推至根根处。处。编辑编辑pptpptk5Fk4Ek3Dk2Ak1CB5 伸展树伸展树k5Fk4Ek3Dk2BAk1Ck5Fk4Ek2B

55、Ak1k3DCk5Fk4Ek2BAk1k3DCk4Ek5Fk2BAk1k3DC没起作用没起作用!编辑编辑pptppt5 伸展树伸展树更坏的情况更坏的情况:12213321Insert: 1, 2, 3, N321NFind: 1321NFind: 2312N Find: N321NT (N) = O ( N2 ) 编辑编辑pptppt5 伸展树伸展树另想办法另想办法 对任意非根结点对任意非根结点 X , 用用 P 指代它的父结点，指代它的父结点， G 代表它的祖父结点代表它的祖父结点:情况情况 1: P 是根结点是根结点旋转旋转 X 和和 P情况情况 2: P 不是根结点不是根结点之字形之字形

56、GDPAXBCXGCDPAB双旋转双旋转一字形一字形GDPCXAB单旋转单旋转XAPBGDC编辑编辑pptppt5 伸展树伸展树k5Fk4Ek3Dk2Ak1CBk5Fk4Ek1k3DCk2BAk1k2BAk4k5FEk3DC伸展操作不仅将被访问结点移到根处，伸展操作不仅将被访问结点移到根处，而且整体上将路径上大部分结点的深度而且整体上将路径上大部分结点的深度减少了将近一半。减少了将近一半。编辑编辑pptppt5 伸展树伸展树Insert: 1, 2, 3, 4, 5, 6, 771654327654132Find: 176145321674532一个一个32个结点的例子在个结点的例子在图图 4.52 4.60编辑编辑pptppt5 伸展树伸展树Deletions: 步骤步骤 1: Find X ;X 将成为根。将成为根。 步骤步骤 2: Remove X ;将得到两棵子树将得到两棵子树 TL 和和 TR . 步骤步骤 3: FindMax ( TL ) ;最大的元素将成为最大的元素将成为 TL 的根的根, 而且没有右子而且没有右子树。树。 步骤步骤 4: 将将 TR 作为作为 TL 的根的右子树的根的右子树.伸展树真的比伸展树真的比 AVL 树好吗树好吗?编辑编辑pptppt 二叉查找树的其他