个人中心
文章发布
退出
作者热门文章
- Java锁的逻辑（结合对象头和ObjectMonitor）
- 还在用饼状图？来瞧瞧这些炫酷的百分比可视化新图形（附代码实现）⛵
- 自动注册实体类到EntityFrameworkCore上下文，并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
26
4
算法是面试考察的重点，数据结构是算法的根基。今天主要和大家探讨下数据结构中的二叉树，当然也不仅限于二叉树，还有其他类型的扩展.
一棵树由称作跟的节点r以及0个或多个非空的树T1,T2, ...Tk组成，这些子树中每一颗的根都被来至根r的一条有向的边所连接.
深度： 对任意节点ni，ni的深度为从根到ni的唯一路径的长。因此，根的深度为0. 高： 从ni到一片树叶的最长路径的长。因此所有树叶的高都是0.一颗树的高等于它的根的高.
树有很多应用，流行的用法包括Unix在内的很多常用操作系统的目录结构.
遍历包括先序遍历（对节点的处理在它的诸儿子节点处理之前进行的）和后续遍历（在诸儿子节点处理之后进行） 。
二叉树是一棵树，其中每个节点不能有多于两个的儿子.
遍历方法:
满二叉树： 一颗高度为h，并且含有2^h-1个节点的二叉树称为满二叉树，即树的每一层都含有最多的节点。 完全二叉树： 设一个高度为h，有n个节点的二叉树，当且仅当其每一个节点都与高度为h的满二叉树中编号为1~n的节点一一对应时，称为完全二叉树.
struct TreeNode
{
int val;
TreeNode* left; // left child
TreeNode* right; // right child
}
使二叉树成为二叉查找树的性质是，对于树中的每个节点X，它的左子树中所有关键字值小于X的关键字值，而它的右子树中所有关键字值大于X的关键字值.
注意对是否为空树进行判断，可以使用递归，使用的栈空间的量只是O(logN).
查找最小值时，从根开始并且只要有左儿子就向左进行，终止点是最小的元素。查找最大值时与之相反.
为了将X插入到树T中，可以像查找那样沿着树查找。如果找到X，可以什么也不做或者做一些更新。否则将X插入到遍历的路径上的最后一点上.
分3种情况:
void remove(const int& x, BinaryNode* root)
{
if (root == NULL)
reutrn;
else if (x < root->val)
remove(x, root->left);
else if (x > root->val)
remove(x, root->right);
else if(t->left != NULL && t->right != NULL)
{
root->val = findMin(root->right)->val;
remove(root->val, root->right);
}
else
{
BinaryNode *oldNode = root;
root = (root->left != NULL) ? root->left : root->right;
delete oldNode;
}
}
Java版本如下:
一棵树的所有节点的深度的和称为内部路径长，二叉查找树的平均值为O(NlogN)，因此任意节点期望深度为O(logN).
一颗AVL树是其每个节点的左子树和右子树的高度最多差1的 二叉查找树 。可以证明，一个AVL树的高度最多只比logN稍微多一点。AVL树也成为平衡二叉树.
因此，除去可能的插入外，所有树的操作都可以以时间O(logN)执行。注意，当进行插入操作时，我们需要更新通向根节点路径上的那些节点的所有平衡信息，而插入操作隐含着困难的原因在于，插入一个节点可能破坏AVL树的特性.
AVL树插入时可能出现的4种情况，把必须重新平衡的节点称为A，由于任意节点最多有两个儿子，因此高度不平衡时，A点的两颗子树的高度相差2，这种不平衡出现了下面4种情况:
解决方案：对于1和4两种情况，插入发生在“外边”，只需通过对树的一次单旋转而完成调整；对于2和3两种情况，插入发生在“内部”，需通过对树的双旋转而完成调整（也就是先单旋转转换为插入发生在外边的情况，再使用单旋转即可）； 。
struct AvlNode
{
int element;
AvlNode *left;
AvlNode *right;
int height;
AvlNode(int theElement, AvlNode *lt, AvlNode *rt, int h = 0)
: element(theElement), left(lt), right(rt), height(h) {}
}
int height (AvlNode *root) const
{
return root == NULL ? -1 : root->height;
}
/* Insert node */
void insert(const int& x, AvlNode *root)
{
if (root == NULL)
root = new AvlNode(x, NULL, NULL);
else if (x < root->element)
{
insert(x, root->left);
// 需要旋转
if (height(root->left) - height(root->right) == 2)
{
if (x < root->left->element)
rotateWithLeftChild(root);
else
doubleWithLeftChild(root);
}
}
else if (root->element < x)
{
insert(x, root->right);
if (height(root->right) - height(root->left) == 2)
{
if (root->right->element < x)
rotateWithRightChild(root);
else
doubleWithRightChild(root); }
}
else
; // duplicate
root->height = max(height(root->left), height(root->right)) + 1;
}
/* Rotate binary tree with left child */
void rotateWithLeftChild(AvlNode* k2)
{
AvlNode* k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = max(height(k2->left), height(k2->right)) + 1;
k1->height = max(height(k1->left), k2->height) + 1;
k2 = k1;
}
/* Rotate binary tree with right child */
void rotateWithRightChild(AvlNode* k1)
{
AvlNode* k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1->height = max(height(k1->left), height(k1->right)) + 1;
k2->height = max(height(k2->right), k1->height) + 1;
k1 = k2;
}
/* Double rotate binary tree with left child */
void rotateWithRightChild(AvlNode* k3)
{
rotateWithRightChild(k3->left);
rotateWithLeftChild(k3);
}
/* Double rotate binary tree with right child */
void doubleWithLeftChild(AvlNode* k1)
{
rotateWithLeftChild(k1->left);
rotateWithRightChild(k1);
}
大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于 树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下，因此我们该想办法降低树的深度，从而减少磁盘查找存取的次数。 一个基本的想法就是：采用多叉树结构（由于树节点元素数量是有限的，自然该节点的子树数量也就是有限的）.
磁盘的构造:
磁盘是一个扁平的圆盘(与电唱机的唱片类似)。盘面上有许多称为磁道的圆圈，数据就记录在这些磁道上。磁盘可以是单片的，也可以是由若干盘片组成的盘组，每一盘片上有两个面。如下图所示的6片盘组为例，除去最顶端和最底端的外侧面不存储数据之外，一共有10个面可以用来保存信息.
磁盘的读/写原理和效率:
磁盘上数据必须用一个三维地址唯一标示：柱面号、盘面号、块号(磁道上的盘块).
读/写磁盘上某一指定数据需要下面3个步骤:
经过上面三个步骤，指定数据的存储位置就被找到。这时就可以开始读/写操作了.
访问某一具体信息，由3部分时间组成:
磁盘读取数据是以盘块(block)为基本单位的。位于同一盘块中的所有数据都能被一次性全部读取出来。而 磁盘IO代价主要花费在查找时间Ts上 。因此我们应该尽量将相关信息存放在同一盘块，同一磁道中。或者至少放在同一柱面或相邻柱面上，以求在读/写信息时尽量减少磁头来回移动的次数，避免过多的查找时间Ts.
总结：在大规模数据存储方面，大量数据存储在外存磁盘中，而在外存磁盘中读取/写入块(block)中某数据时，首先需要定位到磁盘中的某块， 如何有效地查找磁盘中的数据，需要一种合理高效的外存数据结构，就是下面所要重点阐述的B-tree结构 .
M阶 B树 满足下列条件:
向上取整 )和M之间 叶子节点只是没有孩子和指向孩子的指针，这些节点也存在，也有元素。其实，关键是把什么当做叶子结点，因为如红黑树中，每一个NULL指针即当做叶子结点，只是没画出来而已 ] 下面是B树的简单例子:
B树相关操作:
如果插入节点后树的性质不被改变，可以直接进行插入。如果待插入的节点已满，由于一片树叶只能容纳两个或三个关键字，解决办法，先插入到指定的叶子，如果该节点有四个儿子，我们将这个节点分成两个节点，每个节点两个儿子即可。而这样分裂该节点将给它的父节点带来一个新问题（该父节点就有4个儿子），但是我们可以在通向根的路径上一直这么分下去，直到或者到达根节点，或者找到一个节点，这个节点只有两个儿子.
删除操作可以看成是插入操作的逆过程；先找到需要被删除的关键字并将其除去而完成删除操作。如果这个关键字是一个节点仅有的两个关键字中的一个，那么将他出去后就只剩一个关键字了。此时通过把这个节点与它的一个兄弟合并起来进行调整。如果这个兄弟已有3个关键字，那么可以取出一个使得两个节点各有两个关键字，如果这个兄弟只有两个关键字，那么就将这两个节点合并成一个具有3个关键字的节点。现在这个节点的父亲则失去了一个儿子，因此我们还需要向上检查直到顶部。如果根节点失去了它的第二个儿子，那么这个根也要删除，而树则减少了一层.
下面以4 阶 B 树为例，来说明B树的创建过程:
首先必须明确，对于4阶B树，每个节点最多有 4 个子树、最少有 2 个子树，由于关键字的数目比字数数目少1，所以对应的最多有3个关键字，最少有1个关键字.
这个拆的过程比较复杂，首先要确定根节点保留几个关键字，由于“非叶子节点的根节点至少有 2 棵子树”的限制，那就至少需要两个关键字分出去，又因为“子树数是关键字数+1”，如果根节点有两个关键字，就得有三个子树，无法满足，所以只好把除 6 以外的三个关键字都拆为子树.
因为“根节点必须都在同一层”，因此我们不能给现有的左右子树添加子树，只能添加给 6 了；但是如果 6 有三个子树，就必须得有 2 个关键字，提升谁做关键字好呢，这得看谁做 6 中间的子树，因为右子树的所有关键字都得比父节点的关键字大，所以这个提升的关键字只能比未来右子树中的关键字都小，那就只有 10 和 11 可以考虑了。提升 10 吧，没有比它小的做子树，那就只能提升 11 了:
继续添加其他元素也是类似的操作.
使用场景 。
文件系统和数据库系统中常用的B/B+ 树，他通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。他广泛用于文件系统及数据库中，如:
文件查找： 关于内存中的文件名查找，由于是一个有序表结构，可以利用折半查找提高效率。至于IO操作是影响整个B树查找效率的决定因素。当然，如果我们使用平衡二叉树的磁盘存储结构来进行查找，磁盘4次，最多5次，而且 文件越多，B树比平衡二叉树所用的磁盘IO操作次数将越少，效率也越高.
B树中的每个结点根据实际情况可以包含大量的关键字信息和分支(当然是不能超过磁盘块的大小，根据磁盘驱动(disk drives)的不同，一般块的大小在1k~4k左右)；这样树的深度降低了，这就意味着查找一个元素只要很少结点从外存磁盘中读入内存，很快访问到要查找的数据.
树的高度:
当B树包含N个关键字时，B树的最大高度为l-1（因为计算B树高度时，叶结点所在层不计算在内），即：l - 1 = log┌m/2┐((N+1)/2 )+1 .
证明： 若B树某一非叶子节点包含N个关键字，则此非叶子节点含有N+1个孩子结点，而所有的叶子结点都在第I层，我们可以得出： 1. 因为根至少有两个孩子，因此第2层至少有两个结点。 2. 除根和叶子外，其它结点至少有┌m/2┐个孩子， **** 因此在第3层至少有2 ┌m/2┐个结点， 4. 在第4层至少有2 (┌m/2┐^2)个结点， 5. 在第 I 层至少有2 (┌m/2┐^(l-2) )个结点，于是有： N+1 ≥ 2 ┌m/2┐I-2； 6. 考虑第L层的结点个数为N+1，那么2*(┌m/2┐^(l-2)）≤N+1，也就是L层的最少结点数刚好达到N+1个，即： I≤ log┌m/2┐((N+1)/2 )+2； 。
复杂度分析： 对于一颗节点为N度为M的子树，查找和插入需要log(M-1)N ~ log(M/2)N次比较。这个很好证明，对于度为M的B树，每一个节点的子节点个数为M/2 到 M-1之间，所以树的高度在log(M-1)N至log(M/2)N之间.
B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定；我们先看看两者的区别:
B+跟B树不同,B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加； 。
B+树叶子节点保存了父节点的所有关键字记录的指针， 所有数据地址必须要到叶子节点才能获取到。 所以每次数据查询的次数都一样； 。
B+树叶子节点的关键字从小到大有序排列， 左边结尾数据都会保存右边节点开始数据的指针 ,
非叶子节点的子节点数=关键字数（来源百度百科）（根据各种资料 这里有两种算法的实现方式，另一种为非叶节点的关键字数=子节点数-1（来源维基百科)，虽然他们数据排列结构不一样，但其原理还是一样的Mysql 的B+树是用第一种方式实现）.
以下来自百度百科:
以下来自维基百科:
特点:
1、 B+树的层级更少 ：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快； 。
2、 B+树查询速度更稳定 ：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定,
3、 B+树天然具备排序功能 ：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高.
4、 B+树全节点遍历更快 ：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描.
B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快.
用途： B树和B+广泛应用于文件存储系统以及数据库系统中。MySQL就普遍使用B+Tree实现其索引结构。索引（Index）是帮助MySQL高效获取数据的数据结构。索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数.
B+tree比B树更适合实际应用中操作系统的文件索引:
数据库索引采用B+树的主要原因是： B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）.
B*树 是B+tree的变体，在B+树的基础上( 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针 )， 。
1、相同思想和策略 。
从平衡二叉树、B树、B+树、B*树总体来看它们的贯彻的思想是相同的，都是采用二分法和数据平衡策略来提升查找数据的速度； 。
2、不同的方式的磁盘空间利用 。
不同点是他们一个一个在演变的过程中通过IO从磁盘读取数据的原理进行一步步的演变，每一次演变都是为了让节点的空间更合理的运用起来，从而使树的层级减少达到快速查找数据的目的； 。
红黑树的主要像是对2-3查找树进行编码，尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型， 红色链接用来链接两个2-nodes节点来表示一个3-nodes节点,黑色链接用来链接普通的2-3节点 。特别的，使用红色链接的两个2-nodes来表示一个3-nodes节点，并且 向左倾斜 ，即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改，和普通的二叉查找树相同.
根据以上描述，红黑树定义如下： 红黑树是一种具有红色和黑色链接的二叉查找树，同时满足:
完美黑色平衡 的，即 任意空链接到根节点的路径上的黑色链接的个数都相同。 
下图可以看到红黑树其实是2-3树的另外一种表现形式：如果我们将红色的连线水平绘制，那么它连接的两个2-node节点就是2-3树中的一个3-node节点了.
相关操作:
性质 。
下图是红黑树在各种情况下的时间复杂度，可以看出红黑树是2-3查找树的一种实现，它能保证最坏情况下仍然具有对数的时间复杂度.
应用 红黑树这种数据结构应用十分广泛，在多种编程语言中被用作符号表的实现 。
至于为什么不选择AVL树来实现这些数据结构，主要有以下几点原因:
1. 如果插入一个node引起了树的不平衡，AVL和RB-Tree都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转，只需要O(1)的复杂度。 2. AVL的结构相较RB-Tree来说更为平衡，在插入和删除node更容易引起Tree的unbalance，因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高。因此，RB-Tree在需要大量插入和删除node的场景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。 **** map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说，RB-tree的统计性能是高于AVL的.
更详细参考： 浅谈算法和数据结构: 九 平衡查找树之红黑树 。
红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质:
前面讲到红黑树能自平衡，主要靠三种操作：左旋、右旋和变色.
下面针对红黑树的插入和删除进行分析:
红黑树的插入 。
Case 1，红黑树为空树：直接把插入结点作为根结点就行，但注意，根据红黑树性质2：根节点是黑色.
Case 2，插入结点的key已经存在：那么把插入结点设置为将要替代结点的颜色，再把结点的值更新就完成插入.
Case 3，插入结点的父结点为黑结点：由于插入的结点是红色的，并不会影响红黑树的平衡，而且父结点为黑色，直接插入即可，无需做自平衡.
Case 4， 插入结点的父结点为红结点 根据红黑树性质2，根结点是黑色。如果插入的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。这点很重要，因为后续的旋转操作肯定需要祖父结点的参与.
具体又分为如下几种情况:
1） 叔叔结点存在并且为红结点， 。
2）插入结点位于父结点的外侧，需要进行单次旋转.
3）插入结点位于父结点的内侧，需要进行两次旋转.
红黑树的删除 。
首先利用右子树中的最小结点替代被删除的结点，同时循环删除替代的结点。删除结点后，为了保证红黑树的平衡， 可能出现如下几种需要调节的情况:
处理： 移除DB ；将父结点改为黑色，如果父结点本来就为黑色，则父结点变为DB结点；将兄弟结点改为红色。操作完成后，如果仍然存在DB，则依据其他Case调整.
在下面的例子中，就出现了这种情况，第一次调整之后， 20变成了DB；因此需要进一步调节，最后5变成红色，root结点10变成DB，根据Case 2的规则，直接将Root的DB去掉，改为正常结点即可.
操作：互换父结点和兄弟结点的颜色；将父结点朝DB的方向旋转。如此之后，如需要可以依据其他Case调整.
操作：互换DB的兄弟结点以及兄弟结点中靠近DB的子结点的颜色；将兄弟结点朝DB的反方向旋转。如需要参考其他规则调整.
操作：互换父结点和兄弟结点的颜色；朝DB的方向旋转父结点；将DB改为正常结点；将原来兄弟结点中的红色子结点变为黑色.
参考:
Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树或键树，是一种多叉树结构，如下图所示： 上图是一棵Trie树，表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出Trie树的基本性质:
通常在实现的时候，会在节点结构中设置一个标志，用来标记该结点处是否构成一个单词（关键字）。可以看出，Trie树的关键字一般都是字符串，而且Trie树把每个关键字保存在一条路径上，而不是一个结点中。另外，两个有公共前缀的关键字，在Trie树中前缀部分的路径相同，所以Trie树又叫做前缀树(Prefix Tree).
优点:
关于查询，会有人说 hash 表时间复杂度是O(1)不是更快？但是，哈希搜索的效率通常取决于 hash 函数的好坏，若一个坏的 hash 函数导致很多的冲突，效率并不一定比Trie树高。Trie树中不同的关键字不会产生冲突.
缺点:
const int ALPHABET_SIZE = 26;
struct trieNode
{
int count; // 记录每个节点代表的单词个数
trieNode* children[ALPHABET_SIZE];
};
trieNode* createTrieNode()
{
trieNode* pNode = new trieNode();
pNode->count = 0;
for (int i = 0; i < ALPHABET_SIZE; i++)
{
pNode->children[i] = NULL;
}
return pNode;
}
void trieInsert(trieNode* root, char* key)
{
trieNode* node = root;
char* p = key;
while (*p)
{
if (node->children[*p-'a'] == NULL)
{
node->children[*p-'a'] = createTrieNode();
}
node = node->children[*p-'a'];
++p;
}
node->count += 1;
}
/*
查询：不存在返回0，存在返回出现的次数
*/
int trieSearch(trieNode* root, char* key)
{
trieNode* node = root;
char* p = key;
while (*p && node != NULL)
{
node = node->children[*p-'a'];
++p;
}
if (node == NULL)
return 0;
else
return node->count;
}
拓展：后缀树 。
后缀树（Suffix tree）是一种数据结构，能快速解决很多关于字符串的问题。 后缀，顾名思义，就是后面尾巴的意思。比如说给定一长度为n的字符串S=S1S2..Si..Sn，和整数i，1 <= i <= n，子串SiSi+1...Sn便都是字符串S的后缀。 以字符串S=XMADAMYX为例，它的长度为8，所以S[1..8], S[2..8], ... , S[8..8]都算S的后缀，我们一般还把空字串也算成后缀。这样，我们一共有如下后缀。对于后缀S[i..n]，我们说这项后缀起始于i.
S[1..8], XMADAMYX， 也就是字符串本身，起始位置为1 S[2..8], MADAMYX，起始位置为2 S[.8], ADAMYX，起始位置为3 S[4..8], DAMYX，起始位置为4 S[5..8], AMYX，起始位置为5 S[6..8], MYX，起始位置为6 S[7..8], YX，起始位置为7 S[8..8], X，起始位置为8 空字串，记为$.
而后缀树，就是包含一则字符串所有后缀的压缩Trie。把上面的后缀加入Trie后，我们得到下面的结构:
应用：常用来查找在串S中查询字串P是否存在 。
树的带权路径长度： 指树中所有叶子 节点到根节点的路径长度与该叶子节点权值的乘积之和 ，如果在一棵二叉树中共有n个叶子节点，用Wi表示第i个叶子节点的权值，Li表示第i个也叶子节点到根节点的路径长度，则该二叉树的带权路径长度 WPL=W1 L1 + W2 L2 + ... Wn*Ln.
赫夫曼树（Huffman Tree），又称最优二叉树，是一类带权路径长度最短的树。假设有n个权值{w1,w2,...,wn}，如果构造一棵有n个叶子节点的二叉树，而这n个叶子节点的权值是{w1,w2,...,wn}，则所构造出的带权路径长度最小的二叉树就被称为赫夫曼树.
根据节点的个数以及权值的不同，赫夫曼树的形状也各不相同，赫夫曼树具有如下特性:
Huffman树的构建过程： 1. 将给定的n个权值看做n棵只有根节点（无左右孩子）的二叉树，组成一个集合HT，每棵树的权值为该节点的权值。 2. 从集合HT中选出 2棵权值最小的二叉树 ，组成一棵新的二叉树， 其权值为这2棵二叉树的权值之和 。 将步骤2中选出的2棵二叉树从集合HT中删去，同时将步骤2中新得到的二叉树加入到集合HT中。 4. 重复步骤2和步骤3，直到集合HT中只含一棵树，这棵树便是赫夫曼树.
举例如下： 构建出的Huffman树的可能情况有如下两种:
Huffman编码 赫夫曼树的应用十分广泛，比如众所周知的在通信电文中的应用。在等传送电文时，我们希望电文的总长尽可能短，因此可以对每个字符设计长度不等的编码，让电文中出现较多的字符采用尽可能短的编码。为了保证在译码时不出现歧义，我们可以采取如下图所示的编码方式： 对应的Huffman编码：5：11；4：10；3：00；2：011；1：010；上面构建的第二幅Huffman树的编码类似； 。
B+树最大的性能问题是会产生大量的随机IO，随着新数据的插入，叶子节点会慢慢分裂，逻辑上连续的叶子节点在物理上往往不连续，甚至分离的很远，但做范围查询时，会产生大量读随机IO.
对于大量的随机写也一样，举一个插入key跨度很大的例子，如7->1000->3->2000 ... 新插入的数据存储在磁盘上相隔很远，会产生大量的随机写IO. 。
为了克服B+树的弱点，HBase引入了LSM树的概念，即Log-Structured Merge-Trees.
为了更好的说明LSM树的原理，下面举个比较极端的例子:
现在假设有1000个节点的随机key，对于磁盘来说，肯定是把这1000个节点顺序写入磁盘最快，但是这样一来，读就悲剧了，因为key在磁盘中完全无序，每次读取都要全扫描； 。
那么，为了让读性能尽量高，数据在磁盘中必须得有序，这就是B+树的原理，但是写就悲剧了，因为会产生大量的随机IO，磁盘寻道速度跟不上.
LSM树本质上就是在读写之间取得平衡，和B+树相比，它牺牲了部分读性能，用来大幅提高写性能.
它的原理是把一颗大树拆分成N棵小树， 它首先写入到内存中（内存没有寻道速度的问题，随机写的性能得到大幅提升），在内存中构建一颗有序小树，随着小树越来越大，内存的小树会flush到磁盘上。当读时，由于不知道数据在哪棵小树上，因此必须遍历所有的小树，但在每颗小树内部数据是有序的.
以上就是LSM树最本质的原理，有了原理，再看具体的技术就很简单了.
1）首先说说为什么要有WAL（Write Ahead Log），很简单，因为数据是先写到内存中，如果断电，内存中的数据会丢失，因此为了保护内存中的数据，需要在磁盘上先记录logfile，当内存中的数据flush到磁盘上时，就可以抛弃相应的Logfile.
2）什么是memstore, storefile？很简单，上面说过，LSM树就是一堆小树，在内存中的小树即memstore，每次flush，内存中的memstore变成磁盘上一个新的storefile.
3）为什么会有compact？很简单，随着小树越来越多，读的性能会越来越差，因此需要在适当的时候，对磁盘中的小树进行merge，多棵小树变成一颗大树.
关于LSM Tree，对于最简单的二层LSM Tree而言，内存中的数据和磁盘中的数据merge操作，如下图:
LSM Tree弄了很多个小的有序结构，比如每m个数据，在内存里排序一次，下面100个数据，再排序一次……这样依次做下去，就可以获得N/m个有序的小的有序结构.
在查询的时候，因为不知道这个数据到底是在哪里，所以就从最新的一个小的有序结构里做二分查找，找得到就返回，找不到就继续找下一个小有序结构，一直到找到为止.
很容易可以看出，这样的模式，读取的时间复杂度是 (N/m)*log2N 。读取效率是会下降的.
LSM Tree优化方式:
a、Bloom filter: 就是个带随即概率的bitmap,可以快速的告诉你，某一个小的有序结构里有没有指定的那个数据的。于是就可以不用二分查找，而只需简单的计算几次就能知道数据是否在某个小集合里啦。效率得到了提升，但付出的是空间代价.
b、compact:小树合并为大树:因为小树他性能有问题，所以要有个进程不断地将小树合并到大树上，这样大部分的老数据查询也可以直接使用log2N的方式找到，不需要再进行(N/m)*log2n的查询了 。
欢迎关注公众号【码老思】，获取最通俗易懂的原创技术干货.
最后此篇关于万字长文彻底搞懂二叉树的文章就讲到这里了,如果你想了解更多关于万字长文彻底搞懂二叉树的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
26
4
0
我想在我的 Tree 类中创建一个函数来遍历 n-ary Tree[T] 以取回具有 (level, T) 的元组，以便该 Tree 的用户可以执行类似 tree.traverse.foreach{
给定一个层次格式的数组，它们的直接子级存储在一个连续的数组中，返回一个 n 叉树 给定输入格式: [{'name':'a', 'level': -1}, {'name':'b', 'level
我要求教授给我一份另一个学期的旧作业。它是关于构建一个家谱，然后找到给定的两个节点之间的亲属关系。家谱是关于那美克星人(龙珠z)的，所以每个那美克星人都有一个父亲。 问题是输入是这样的: First
我正在尝试创建一个包含子 vector 的 n 叉树。 这就是我到目前为止所得到的。 在 node.h 文件中我有这个: #include #include using namespa
我正在尝试了解 n 叉树的预序遍历。我一直在阅读，我发现的所有示例都使用左子树和右子树，但是在 n 叉树中，什么是左子树，什么是右子树？有人可以给出一个很好的解释或伪代码吗？ 最佳答案 而不是考虑 l
我应该反序列化一个 n 叉树。 这段代码创建了我的树: foodtree.addChildren("Food", { "Plant", "Animal" } ); foodtree.a
我正在尝试创建叉 TreeMap ，但仍然没有成功。这是我的代码: #include #include #include void procStatus(int level) { prin
我有一个二叉树，代表一个解析后的逻辑公式。例如，f = a & b & -c | d 由前缀表示法的列表列表表示，其中第一个元素是运算符(一元或二元)，接下来的元素是它们的参数: f = [ |, [
我正在尝试根据给定的输入创建一棵树。那里将有一个根，包括子节点和子子节点。我可以实现树，在其中我可以将子节点添加到特定的主节点(我已经知道根)。但是，我试图弄清楚实现树的推荐方法是什么，我们必须首先从
我在 n 个节点上有一个完整的 19 元树。我标记所有具有以下属性的节点，即它们的所有非根祖先都是最年长或最小的 child (包括根)。我必须为标记节点的数量给出一个渐近界限。 我注意到 第一层有一
如何在不使用递归的情况下遍历 n 叉树？ 递归方式: traverse(Node node) { if(node == null) return; for(Node c
我的树/节点类: import java.util.ArrayList; import java.util.List; public class Node { private T data;
关闭。这个问题需要更多focused .它目前不接受答案。 想改善这个问题吗？更新问题，使其仅关注一个问题 editing this post . 4年前关闭。 Improve this questi
我在我的 Java 应用程序中有一个非 UI 使用的所谓的“k-ary”树，我想知道 javax.swing.tree 包是否是完成这项工作的正确工具，即使它与 Swing 打包在一起. 我有一类 W
我正在用 Java 实现 N 叉树；每个节点可以有尽可能多的节点。当我尝试 build 一棵树时，问题就来了。我有一个函数可以递归地创建一个特定高度的树，并根据节点列表分配子节点。当我调用该函数时，根
嗨，我有这段代码来搜索 n 叉树，但它不能正常工作，我不知道这有什么问题当搜索 n4 和 n5 时，它返回 n3怎么了？ public FamilyNode findNodeByName(Family
哪个是 C 语言中 N 叉树的简洁实现？ 特别是，我想实现一个 n 元树，而不是自平衡的，每个节点中的子节点数量不受限制，其中每个节点都包含一个已经定义的结构，例如: struct task {
#include #include #include typedef struct _Tree { struct _Tree *child; struct _Tree *
我正在编写文件系统层次结构的 N 叉树表示形式，其中每个节点都包含有关它所表示的文件/文件夹的一些信息。 public class TreeNode { private FileSystemE
如何在 R 中为给定数量的分支和深度构建 N 叉树，例如深度为 3 的二叉树？ 编辑:将源问题与问答分开。 最佳答案 我想提出解决方案，我用它来构建树数据结构 叶安姆 分支因子。要将数据存储在树中，字
我是一名优秀的程序员,十分优秀！