树概念总结
一.前言
面试中被问了树相关的问题，对树不熟练，决定复习一下相关概念，免得日常研发过程中遇到类似需要树的问题，第一反应是用其他的数据结构来弥补而不是第一想到最优先的树。
二.正文
2.1 二叉树
2.1.1 定义
在二叉树中每个节点最多只有两个子节点，可以分别把它们称为左子节点和右子节点。二叉树的根节点没有父节点，一棵非空二叉树只有一个父节点。二叉树的叶节点没有子节点。
2.2 哈夫曼树
2.2.1 定义
哈夫曼（Huffman）树又称最优树，是一类带权路径长度最短的树，在实际中有广泛的用途。哈夫曼树的定义，涉及路径、路径长度、权等概念，下面先给出这些概念的定义，然后再介绍哈夫曼树。
（1）路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。
（2）路径长度：路径上的分支数目称作路径长度。
（3）树的路径长度：从树根到每一结点的路径长度之和。
（4）权：赋予某个实体的一个量，是对实体的某个或某些属性的数值化描述。在数据结构中，实体有结点（元素）和边（关系）两大类，所以对应有结点权和边权。结点权或边权具体代表什么意义，由具体情况决定。如果在一棵树中的结点上带有权值，则对应的就有带权树等概念。
（5）结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。
（6）树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作[插图]。
（7）哈夫曼树：假设有 m 个权值{w1, w2,…, wm}，可以构造一棵含 n 个叶子结点的二叉树，每个叶子结点的权为 wi，则其中带权路径长度 WPL 最小的二叉树称做最优二叉树或哈夫曼树。
权重：23x2 + 11x3 +5x4 + 3x4 + 29x2 + 14x3 + 7x4 + 8x4= 271
2.2.2 应用 哈夫曼编码(文件压缩)
在进行数据压缩时，为了使压缩后的数据文件尽可能短，可采用不定长编码。其基本思想是：为出现次数较多的字符编以较短的编码。为确保对数据文件进行有效的压缩和对压缩文件进行正确的解码，可以利用哈夫曼树来设计二进制编码。
（1）前缀编码：如果在一个编码方案中，任一个编码都不是其他任何编码的前缀（最左子串），则称编码是前缀编码。例如，案例 5.1 中的第 2 种编码方案（见表 5.1（b））的编码 0，10，110，111 是前缀编码，而第 3 种编码方案（见表 5.1（c））的编码 0，01，010，111 就不是前缀编码。前缀编码可以保证对压缩文件进行解码时不产生二义性，确保正确解码。
（2）哈夫曼编码：对一棵具有 n 个叶子的哈夫曼树，若对树中的每个左分支赋予 0，右分支赋予 1，则从根到每个叶子的路径上，各分支的赋值分别构成一个二进制串，该二进制串就称为哈夫曼编码。
2.3 二叉搜索树
2.3.1 定义
1）若左子树非空，则左子树上所有结点关键字值均小于根结点的关键字值。
2）若右子树非空，则右子树上所有结点关键字值均大于根结点的关键字值。
3）左、右子树本身也是一颗二叉排序树。
查找效率 O(N)和 O(log2n)之间
2.4 平衡二叉树
2.4.1 定义
为了避免树的高度增长过快，降低二叉排序树的性能，我们规定在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差的绝对值不超过 1，并将这样的二叉树称为平衡二叉树（AVL）
2.4.2 应用
windows 对进程地址空间的管理用到了 AVL 树
2.5 红黑树
2.5.1 定义
红黑树的五个性质：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
2.5.2 应用
广泛用在 C++的 STL 中。如 map 和 set 都是用红黑树实现的。
linux 的 epoll 底层也是红黑树存储注册的行为
2.6 B+树
2.6.1 定义
1 Ｂ树和Ｂ＋树的出现是因为磁盘ＩＯ；众所周知，ＩＯ操作的效率很低，那么，当在大量数据存储中，查询时我们不能一下子将所有数据加载到内存中，只能逐一加载磁盘页，每个磁盘页对应树的节点。造成大量磁盘ＩＯ操作（最坏情况下为树的高度）。平衡二叉树由于树深度过大而造成磁盘 IO 读写过于频繁，进而导致效率低下。所以，我们为了减少磁盘ＩＯ的次数，就你必须降低树的深度，将“瘦高”的树变得“矮胖”。
一个 m 阶的 B+树具有如下几个特征：
1.有 k 个子树的中间节点包含有 k 个元素（B 树中是 k-1 个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
2.6.2 应用
用在磁盘文件组织 数据索引和数据库索引
三.参考
努力分享对他人有价值的知识 2018.06.14 加入
还未添加个人简介
评论