搜索树 - 2.ppt

山东大学计算机科学与技术学院数据结构第 11 章搜索树 1搜索树 Serch Trees 第11章山东大学计算机科学与技术学院数据结构第 11 章搜索树 2本章内容: ? 二叉搜索树(Binary Search Trees ) ? AVL 树(AVL Trees) ? 红-黑树(Red-Black Trees) ? B-树(B-Trees) 2/2/2017 3 1. 二叉搜索树 2. AVL 树 3. B树本章重点 2/2/2017 4 同样 3 个数据{ 1, 2, 3 },输入顺序不同,建立起来的二叉搜索树的形态也不同。这直接影响到二叉搜索树的搜索性能。如果输入序列选得不好,会建立起一棵单支树,使得二叉搜索树的高度达到最大,这样必然会降低搜索性能。{2, 1, 3} {2, 1, 3} {1, 2, 3} {1, 3, 2} {2, 3, 1} {3, 1, 2} {3, 2, 1} {1, 2, 3} {1, 3, 2} {2, 3, 1} {3, 1, 2} {3, 2, 1} 123 1111 322 23 32 3 山东大学计算机科学与技术学院数据结构第 11 章搜索树 AVL 树?当搜索树的高度总是 O(logn) 时,能够保证每个搜索树操作所占用的时间为 O(logn) 。? AVL( Adelson- Velsky 和Landis 1962 年提出) 树——一种平衡树。?山东大学计算机科学与技术学院数据结构第 11 章搜索树 6AVL 树 AVL 树定义: ?空二叉树是 AVL 树。?如果 T是一棵非空的二叉树, T L和T R分别是其左子树右子树,当 T满足以下条件时, T是一棵 AVL 树。 1. T L和T R是 AVL 树, 2. |h L– h R | ? 1 ,h L和h R分别是左子树和右子树的高度。山东大学计算机科学与技术学院数据结构第 11 章搜索树 7AVL 搜索树? AVL 搜索树(平衡二叉搜索树/平衡二叉排序树): 既是二叉搜索树,也是 AVL 树。? AVL 树?–(a) 、(b) ? AVL 搜索树?–(b) 山东大学计算机科学与技术学院数据结构第 11 章搜索树 8带索引的 AVL 搜索树?带索引的 AVL 搜索树既是带索引的二叉搜索树, 也是 AVL 树。?带索引的 AVL 搜索树?–(a) 、(b) 山东大学计算机科学与技术学院数据结构第 11 章搜索树 9AVL 树的特征 1. n 个元素(节点)的AVL 树的高度是 O(logn) 。 2. 对于每一个 n(n ≥0)值,都存在一棵 AVL 树。(否则,在插入完成后,一棵 AVL 树将不是 AVL 树,因为对当前元素数来说不存在对应的 AVL 树)。 3. 一棵 n元素的 AVL 搜索树能在 O ( 高度)= O(logn) 的时间内完成搜索。 4. 将一个新元素插入到一棵 n元素的 AVL 搜索树中,可得到一棵 n+1 元素的 AVL 树,这种插入过程可以在 O(logn) 时间内完成。 5. 从一棵 n元素的 AVL 搜索树中删除一个元素,可得到一棵 n-1 元素的 AVL 树,这种删除过程可以在 O(logn) 时间内完成。?特征 4包含了特征 2。山东大学计算机科学与技术学院数据结构第 11 章搜索树 10 AVL 树的高度?一棵有 n个节点的 AVL 树的高度至多: – log 2 (n+2). ?一棵有 n个节点的 AVL 树的高度至少: – log 2 (n+1). ? N h:高度为 h的AVL 树中的最小节点数。? N h =N h-1 +N h-2 + 1 ,N 0 =0, N 1 = 1, (N 2 = 2, N 3 = 4, 与斐波那契数列的定义非常相似) ?利用归纳法可证得: N h = F h+2 - 1