第十二章高级树结构 任课教员:张铭 http://db.pku.edu.cn/mzhang/dsl zhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究
第十二章 高级树结构 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究
主要内容 12.1Trie和 Patricia结构 12.2改进的BST 最佳二叉搜索树 AⅥL树 伸展树 12.3空间树结构 12.4决策树和博弈树 北京大学信息学院 @版权所有,转载或翻印必究 Page 2
北京大学信息学院 ©版权所有，转载或翻印必究 Page 2 主要内容 ◼ 12.1 Trie和Patricia 结构 ◼ 12.2 改进的BST ◼ 最佳二叉搜索树 ◼ AVL树 ◼ 伸展树 ◼ 12.3 空间树结构 ◼ 12.4 决策树和博弈树
12.1Trie结构和 Patricia树 ■BST(二叉搜索树)不是一棵平衡的树,它的树结构 与输入数据的顺序有很大的关系 输入顺序为4、5、6、7、8 输入顺序为7、5、4、6、8 北京大学信息学院 @版权所有,转载或翻印必究 Page 3
北京大学信息学院 ©版权所有，转载或翻印必究 Page 3 12.1Trie结构和Patricia树 ◼ BST（二叉搜索树）不是一棵平衡的树，它的树结构 与输入数据的顺序有很大的关系
对象空间( object space)分解 BST是一种组织上基于对象空间 ( object space)分解的数据结构 空间分解是存储在树中的对象(关键 码值)决定 最简单的方法就是对对象(这里是 关键码)的范进行划分 平均划分 按照某种方式不平均划分 北京大学信息学院 @版权所有,转载或翻印必究 Page 4
北京大学信息学院 ©版权所有，转载或翻印必究 Page 4 对象空间( object space )分解 ◼ BST是一种组织上基于对象空间 ( object space )分解的数据结构 ◼ 空间分解是存储在树中的对象（关键 码值）决定 ◼ 最简单的方法就是对对象（这里是 关键码）的范围进行划分 ◼ 平均划分 ◼ 按照某种方式不平均划分
假设划分因子为2 每次仅把当前范围分为两部分 (对应于二叉树) 在进行插入的时候,只要是小于结 点的关键码的都在左子树中 只要是大于结点的关键码的都在右 子树中 北京大学信息学院 @版权所有,转载或翻印必究 Page 5
北京大学信息学院 ©版权所有，转载或翻印必究 Page 5 ◼ 假设划分因子为2 ◼ 每次仅把当前范围分为两部分 （对应于二叉树） ◼ 在进行插入的时候，只要是小于结 点的关键码的都在左子树中 ◼ 只要是大于结点的关键码的都在右 子树中
关键码空间( key space)分解 不依赖于关键码的插入顺序 树的深度受到关键码精度的影响 ■最坏的情况下,深度等于存储关键码所需要的位数 例如,如果关键码是0到255之间的整数,那么关键码 的精度就是8个二进制位。 如果有两个关键码:10000001000001,它们的前面7位都 是相同的 所以直到第8次划分才能将这两个关键码分开 n这样的搜索树深度也为8,但这是最坏的情况 北京大学信息学院 @版权所有,转载或翻印必究 Page 6
北京大学信息学院 ©版权所有，转载或翻印必究 Page 6 关键码空间（key space）分解 ◼ 不依赖于关键码的插入顺序 ◼ 树的深度受到关键码精度的影响 ◼ 最坏的情况下，深度等于存储关键码所需要的位数 ◼ 例如，如果关键码是0到255之间的整数，那么关键码 的精度就是8个二进制位。 ◼ 如果有两个关键码：10000010和10000011，它们的前面7位都 是相同的 ◼ 所以直到第8次划分才能将这两个关键码分开 ◼ 这样的搜索树深度也为8，但这是最坏的情况
基于关键码范围的分解 保证平衡吗? 显然是不行的 如果关键码的分布得很不均衡,将导 致树的结构失衡 一种极端的情况,导致所有的关键码都小 于根结点,那么以该结点为根的子树的右 子树将没有任何的元素 北京大学信息学院 @版权所有,转载或翻印必究 Page 7
北京大学信息学院 ©版权所有，转载或翻印必究 Page 7 ◼ 基于关键码范围的分解 ◼ 保证平衡吗？ ◼ 显然是不行的 ◼ 如果关键码的分布得很不均衡，将导 致树的结构失衡 ◼ 一种极端的情况，导致所有的关键码都小 于根结点，那么以该结点为根的子树的右 子树将没有任何的元素
Trie结构 基于关键码分解的数据结构,叫作 Trie结构 “trie”这个词来源于“ retrieva 主要应用 信息检索( information retrieval) 用来存储英文字符串,尤其大规模的 英文词典 自然语言理解系统中经常用到 北京大学信息学院 @版权所有,转载或翻印必究 Page 8
北京大学信息学院 ©版权所有，转载或翻印必究 Page 8 Trie结构 ◼ 基于关键码分解的数据结构，叫作 Trie结构 ◼ “trie”这个词来源于“retrieval” ◼ 主要应用 ◼ 信息检索（information retrieval） ◼ 用来存储英文字符串，尤其大规模的 英文词典 ◼ 自然语言理解系统中经常用到
Trie结构的适用情况 a Trie结构主要基于两个原则 有一个固定的关键码集合 对于结点的分层标记 襟锶历毁奇彀霉影樓聞饗蠻葛字母等来 ■例如,元素可以用0-9的数字来标记 在根结点的地方,它分出10个子结点,分别标记0-9 然后每个子结点又可以分出10个结点 如此下去直到所有的元素都能够被区分开 北京大学信息学院 @版权所有,转载或翻印必究 Page 9
北京大学信息学院 ©版权所有，转载或翻印必究 Page 9 Trie结构的适用情况 ◼ Trie结构主要基于两个原则 ◼ 有一个固定的关键码集合 ◼ 对于结点的分层标记 ◼ 如果所有的元素都可以使用数字或者字母等来 标记，那么就可以考虑使用Trie结构 ◼ 例如，元素可以用0-9的数字来标记 ◼ 在根结点的地方，它分出10个子结点，分别标记0-9 ◼ 然后每个子结点又可以分出10个结点 ◼ 如此下去直到所有的元素都能够被区分开
Trie结构特点 与B+树一样,基于关键码空间分解 的树结构,其内部结点仅作为占位 符引导检索过程,数据纪录只存储 在叶结点中 Huffman编码树( Huffman coding tree是一种二叉Trie树 北京大学信息学院 版权所有,转载或翻印必究 Page 10
北京大学信息学院 ©版权所有，转载或翻印必究 Page 10 Trie结构特点 ◼ 与B+树一样，基于关键码空间分解 的树结构，其内部结点仅作为占位 符引导检索过程，数据纪录只存储 在叶结点中 ◼ Huffman编码树( Huffman coding tree )也是一种二叉Trie树