关于java:万字长文彻底搞懂二叉树

算法是面试考查的重点，数据结构是算法的根基。明天次要和大家探讨下数据结构中的二叉树，当然也不仅限于二叉树，还有其余类型的扩大。

一棵树由称作跟的节点 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 种状况：

对 A 的左儿子的左子树进行了一次插入；
对 A 的左儿子的右子树进行了一次插入；
对 A 的右儿子的左子树进行了一次插入；
对 A 的右儿子的右子树进行了一次插入；

解决方案：对于 1 和 4 两种状况，插入产生在“外边”，只需通过对树的一次单旋转而实现调整；对于 2 和 3 两种状况，插入产生在“外部”，需通过对树的双旋转而实现调整（也就是先单旋转转换为插入产生在外边的状况，再应用单旋转即可）；

状况 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 个步骤：

首先移动臂依据柱面号使磁头挪动到所须要的柱面上，这一过程被称为定位或查找
如上图所示的 6 盘组示意图中，所有磁头都定位到了 10 个盘面的 10 条磁道上(磁头都是双向的)。这时依据盘面号来确定指定盘面上的磁道。
盘面确定当前，盘片开始旋转，将指定块号的磁道段挪动至磁头下。

通过下面三个步骤，指定数据的存储地位就被找到。这时就能够开始读 / 写操作了。

拜访某一具体信息，由 3 局部工夫组成：

查找时间 (seek time) Ts: 实现上述步骤(1) 所须要的工夫。这部分工夫代价最高，最大可达到 0.1s 左右。
等待时间 (latency time) Tl: 实现上述步骤(3) 所须要的工夫。因为盘片绕主轴旋转速度很快，个别为 7200 转 / 分(电脑硬盘的性能指标之一, 家用的一般硬盘的转速个别有 5400rpm(笔记本)、7200rpm 几种)。因而个别旋转一圈大概 0.0083s。
传输工夫 (transmission time) Tt: 数据通过系统总线传送到内存的工夫，个别传输一个字节(byte) 大略 0.02us=2*10^(-8)s

磁盘读取数据是以盘块 (block) 为根本单位的。位于同一盘块中的所有数据都能被一次性全副读取进去。而 磁盘 IO 代价次要破费在查找时间 Ts 上。因而咱们应该尽量将相干信息寄存在同一盘块，同一磁道中。或者至多放在同一柱面或相邻柱面上，以求在读 / 写信息时尽量减少磁头来回挪动的次数，防止过多的查找时间 Ts。

总结：在大规模数据存储方面，大量数据存储在外存磁盘中，而在外存磁盘中读取 / 写入块 (block) 中某数据时，首先须要定位到磁盘中的某块，如何无效地查找磁盘中的数据，须要一种正当高效的外存数据结构，就是上面所要重点论述的 B -tree 构造。

M 阶 B 树 满足下列条件：

根节点不是叶子节点，则至多有 2 个子节点
除根节点和叶子节点外，每个节点的子节点个数在 M /2(向上取整 ) 和 M 之间
节点的 key 值以升序排列，位于 N - 1 和 N key 的子节点的值位于 N - 1 和 N key 对应的 Value 之间
所有叶子节点呈现在同一层，叶子结点不蕴含任何关键字信息 (能够看做是内部结点或查问失败的结点，指向这些结点的指针都为 null) [ 叶子节点只是没有孩子和指向孩子的指针，这些节点也存在，也有元素。其实，要害是把什么当做叶子结点，因为如红黑树中，每一个 NULL 指针即当做叶子结点，只是没画进去而已]

上面是 B 树的简略例子：

B 树相干操作：

插入操作

如果插入节点后树的性质不被扭转，能够间接进行插入。如果待插入的节点已满，因为一片树叶只能包容两个或三个关键字，解决办法，先插入到指定的叶子，如果该节点有四个儿子，咱们将这个节点分成两个节点，每个节点两个儿子即可。而这样决裂该节点将给它的父节点带来一个新问题（该父节点就有 4 个儿子），然而咱们能够在通向根的门路上始终这么分上来，直到或者达到根节点，或者找到一个节点，这个节点只有两个儿子。

删除操作

删除操作能够看成是插入操作的逆过程；先找到须要被删除的关键字并将其除去而实现删除操作。如果这个关键字是一个节点仅有的两个关键字中的一个，那么将他进来后就只剩一个关键字了。此时通过把这个节点与它的一个兄弟合并起来进行调整。如果这个兄弟已有 3 个关键字，那么能够取出一个使得两个节点各有两个关键字，如果这个兄弟只有两个关键字，那么就将这两个节点合并成一个具备 3 个关键字的节点。当初这个节点的父亲则失去了一个儿子，因而咱们还须要向上查看直到顶部。如果根节点失去了它的第二个儿子，那么这个根也要删除，而树则缩小了一层。

上面以 4 阶 B 树为例，来阐明 B 树的创立过程：

首先必须明确，对于 4 阶 B 树，每个节点最多有 4 个子树、起码有 2 个子树，因为关键字的数目比字数数目少 1，所以对应的最多有 3 个关键字，起码有 1 个关键字。

增加 6，第一个节点
增加 10，根节点最多能放三个关键字，按程序添到根节点中
增加 4，还能放到根节点中
增加 14，这时超出了关键字最大限度，须要把 14 增加为子树，因为字树的数目比关键字

这个拆的过程比较复杂，首先要确定根节点保留几个关键字，因为“非叶子节点的根节点至多有 2 棵子树”的限度，那就至多须要两个关键字分进来，又因为“子树数是要害字数 +1”，如果根节点有两个关键字，就得有三个子树，无奈满足，所以只好把除 6 以外的三个关键字都拆为子树。

增加 5，放到 4 所在的子树上
增加 11，放在 10 和 14 所在的右子树上
增加 15，按大小应该放到 10、11 和 14 所在的子树上，但因为超过了要害字数限度，又得拆分

因为“根节点必须都在同一层”，因而咱们不能给现有的左右子树增加子树，只能增加给 6 了；然而如果 6 有三个子树，就必须得有 2 个关键字，晋升谁做关键字好呢，这得看谁做 6 两头的子树，因为右子树的所有关键字都得比父节点的关键字大，所以这个晋升的关键字只能比将来右子树中的关键字都小，那就只有 10 和 11 能够思考了。晋升 10 吧，没有比它小的做子树，那就只能晋升 11 了：

持续增加其余元素也是相似的操作。

应用场景

文件系统和数据库系统中罕用的 B /B+ 树，他通过对每个节点存储个数的扩大，使得对间断的数据可能进行较快的定位和拜访，可能无效缩小查找时间，进步存储的空间局部性从而缩小 IO 操作。他宽泛用于文件系统及数据库中，如：

Windows：HPFS 文件系统
Mac：HFS，HFS+ 文件系统
Linux：ResiserFS，XFS，Ext3FS，JFS 文件系统
数据库：ORACLE，MYSQL，SQLSERVER 等中

文件查找：
对于内存中的文件名查找，因为是一个有序表构造，能够利用折半查找提高效率。至于 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+-tree 的磁盘读写代价更低
B+-tree 的外部结点并没有指向关键字具体信息的指针。因而其外部结点绝对 B 树更小。如果把所有同一外部结点的关键字寄存在同一盘块中，那么盘块所能包容的关键字数量也越多。一次性读入内存中的须要查找的关键字也就越多。相对来说 IO 读写次数也就升高了。
举个例子，假如磁盘中的一个盘块包容 16bytes，而一个关键字 2bytes，一个关键字具体信息指针 2bytes。一棵 9 阶 B -tree(一个结点最多 8 个关键字) 的外部结点须要 2 个盘快。而 B + 树外部结点只须要 1 个盘快。当须要把外部结点读入内存中的时候，B 树就比 B + 树多一次盘块查找时间(在磁盘中就是盘片旋转的工夫)。
B+-tree 的查问效率更加稳固
因为非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查问的门路长度雷同，导致每一个数据的查问效率相当。

数据库索引采纳 B + 树的次要起因是： B 树在进步了磁盘 IO 性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+ 树应运而生。B+ 树只有遍历叶子节点就能够实现整棵树的遍历。而且在数据库中基于范畴的查问是十分频繁的，而 B 树不反对这样的操作（或者说效率太低）。

B* 树 是 B +tree 的变体，在 B + 树的根底上 ( 所有的叶子结点中蕴含了全副关键字的信息，及指向含有这些关键字记录的指针)，

B树中非根和非叶子结点再减少指向兄弟的指针；B树定义了非叶子结点关键字个数至多为(2/3) M，即块的最低使用率为 2 /3（代替 B + 树的 1 /2），B 树调配新结点的概率比 B + 树要低，空间使用率更高。
B+ 树节点满时就会决裂，而 B * 树节点满时会查看兄弟节点是否满（因为每个节点都有指向兄弟的指针），如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则从以后节点和兄弟节点各拿出 1 / 3 的数据创立一个新的节点进去；

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 节点了。

相干操作：

查找
红黑树是一种非凡的二叉查找树，他的查找办法也和二叉查找树一样，不须要做太多更改。然而因为红黑树比个别的二叉查找树具备更好的均衡，所以查找起来更快。
插入
如上图所示，规范的二叉查找树遍历即可。新插入的节点标记为红色，所有状况依据需要进行左旋或者右旋。

性质

在最坏的状况下，红黑树的高度不超过 2lgN
红黑树的均匀高度大概为 lgN

下图是红黑树在各种状况下的工夫复杂度，能够看出红黑树是 2 - 3 查找树的一种实现，它能保障最坏状况下依然具备对数的工夫复杂度。

利用
红黑树这种数据结构利用非常宽泛，在多种编程语言中被用作符号表的实现

Java 中的 java.util.TreeMap,java.util.TreeSet
C++ STL 中的：map,multimap,multiset
.NET 中的：SortedDictionary,SortedSet 等

至于为什么不抉择 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 的。

更具体参考：浅谈算法和数据结构: 九均衡查找树之红黑树

红黑树是一种含有红黑结点并能自均衡的二叉查找树。它必须满足上面性质：

性质 1：每个节点要么是彩色，要么是红色。
性质 2：根节点是彩色。
性质 3：每个叶子节点（NIL）是彩色。
性质 4：每个红色结点的两个子结点肯定都是彩色。
性质 5：任意一结点到每个叶子结点的门路都蕴含数量雷同的黑结点。

后面讲到红黑树能自均衡，次要靠三种操作：左旋、右旋和变色。

左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点放弃不变。

右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点放弃不变。

变色：结点的色彩由红变黑或由黑变红。

上面针对红黑树的插入和删除进行剖析：

红黑树的插入

Case 1，红黑树为空树：间接把插入结点作为根结点就行，但留神，依据红黑树性质 2：根节点是彩色。

Case 2，插入结点的 key 曾经存在：那么把插入结点设置为将要代替结点的色彩，再把结点的值更新就实现插入。

Case 3，插入结点的父结点为黑结点：因为插入的结点是红色的，并不会影响红黑树的均衡，而且父结点为彩色，直接插入即可，无需做自均衡。

Case 4，插入结点的父结点为红结点 依据红黑树性质 2，根结点是彩色。如果插入的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。这点很重要，因为后续的旋转操作必定须要祖父结点的参加。

具体又分为如下几种状况：

1）叔叔结点存在并且为红结点，

2）插入结点位于父结点的外侧，须要进行单次旋转。

3）插入结点位于父结点的内侧，须要进行两次旋转。

红黑树的删除

首先利用右子树中的最小结点代替被删除的结点，同时循环删除代替的结点。删除结点后，为了保障红黑树的均衡，可能呈现如下几种须要调节的状况：

Case 1：被删除的结点是红色，间接删除；
Case 2：如果 root 结点是 DB（Double Black, 删除结点的色彩与代替结点的色彩均为 Black），能够间接将 DB 改为失常结点；
Case 3：如果 DB 结点的兄弟结点是彩色，并且兄弟结点的子结点均为彩色。

解决：移除 DB；将父结点改为彩色，如果父结点原本就为彩色，则父结点变为 DB 结点；将兄弟结点改为红色。操作实现后，如果依然存在 DB，则根据其余 Case 调整。

在上面的例子中，就呈现了这种状况，第一次调整之后，20 变成了 DB；因而须要进一步调节，最初 5 变成红色，root 结点 10 变成 DB，依据 Case 2 的规定，间接将 Root 的 DB 去掉，改为失常结点即可。

Case 4: DB 的兄弟结点是红色。

操作：调换父结点和兄弟结点的色彩；将父结点朝 DB 的方向旋转。如此之后，如须要能够根据其余 Case 调整。

Case 5：DB 结点的兄弟结点是彩色，兄弟结点的子结点中，远离 DB 结点的子结点是彩色，凑近 DB 结点的子结点是红色。

操作：调换 DB 的兄弟结点以及兄弟结点中凑近 DB 的子结点的色彩；将兄弟结点朝 DB 的反方向旋转。如须要参考其余规定调整。

Case 6：DB 结点的兄弟结点是彩色，兄弟结点的子结点中，远离 DB 结点的子结点是红色。

操作：调换父结点和兄弟结点的色彩；朝 DB 的方向旋转父结点；将 DB 改为失常结点；将原来兄弟结点中的红色子结点变为彩色。

参考：

https://www.jianshu.com/p/e136ec79235c
https://www.youtube.com/watch?v=w5cvkTXY0vQ

Trie 树，又叫字典树、前缀树（Prefix Tree）、单词查找树或键树，是一种多叉树结构，如下图所示：

上图是一棵 Trie 树，示意了关键字汇合{“a”,“to”,“tea”,“ted”,“ten”,“i”,“in”,“inn”}。从上图能够演绎出 Trie 树的根本性质：

根节点不蕴含字符，除根节点外的每一个子节点都蕴含一个字符。
从根节点到某一个节点，门路上通过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点蕴含的字符互不雷同。

通常在实现的时候，会在节点构造中设置一个标记，用来标记该结点处是否形成一个单词（关键字）。能够看出，Trie 树的关键字个别都是字符串，而且 Trie 树把每个关键字保留在一条门路上，而不是一个结点中。另外，两个有公共前缀的关键字，在 Trie 树中前缀局部的门路雷同，所以 Trie 树又叫做前缀树(Prefix Tree)。

长处：

插入和查问的效率很高，都为O(m)，其中 m 是待插入 / 查问的字符串的长度。

对于查问，会有人说 hash 表工夫复杂度是 O(1)不是更快？然而，哈希搜寻的效率通常取决于 hash 函数的好坏，若一个坏的 hash 函数导致很多的抵触，效率并不一定比 Trie 树高。Trie 树中不同的关键字不会产生抵触。
Trie 树只有在容许一个关键字关联多个值的状况下才有相似 hash 碰撞产生。
Trie 树不必求 hash 值，对短字符串有更快的速度。通常，求 hash 值也是须要遍历字符串的。
Trie 树能够对关键字按字典序排序。

毛病：

当 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=W1L1 + W2L2 + … Wn*Ln。

赫夫曼树（Huffman Tree），又称最优二叉树，是一类带权门路长度最短的树。假如有 n 个权值{w1,w2,…,wn}，如果结构一棵有 n 个叶子节点的二叉树，而这 n 个叶子节点的权值是{w1,w2,…,wn}，则所结构出的带权门路长度最小的二叉树就被称为赫夫曼树。

依据节点的个数以及权值的不同，赫夫曼树的形态也各不相同，赫夫曼树具备如下个性：

对于同一组权值，所能失去的赫夫曼树不肯定是惟一的。
赫夫曼树的左右子树能够调换，因为这并不影响树的带权门路长度。
带权值的节点都是叶子节点，不带权值的节点都是某棵子二叉树的根节点。
权值越大的节点越凑近赫夫曼树的根节点，权值越小的节点越远离赫夫曼树的根节点。
赫夫曼树中只有叶子节点和度为 2 的节点，没有度为 1 的节点。
一棵有 n 个叶子节点的赫夫曼树共有 2n- 1 个节点。

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 的查问了

欢送关注公众号【码老思】，获取最通俗易懂的原创技术干货。

1 基础知识

1.1 树的遍历

2 二叉树

3 二叉查找树

1 查找

2 查找最小值或最大值

3 插入

4 删除

5 均匀情景剖析

4 AVL 树

4.1 单旋转

4.2 双旋转

4.3 AVL 树实现

5 高级数据结构

5.1 B 树

5.2 B+ 树

5.3 B* 树

5.4 红黑树 – 算法第 4 版

5.5 红黑树 – 标准版

6 Trie 树

7 Huffman 树

8 LSM 树

站内搜索