一、树

1.只有一个特殊节点，它没有父节点，它就是根节点

2.每一个非根节点有且只有一个父节点

3.每个节点包含多个指针指向其子节点

4.该例子有3层，40那一层，130那一层，10那一层，故该数的深度为3。

5.没有子节点的叫叶子节点。

6.拥有相同父节点的叫兄弟节点。

二、二叉树

在树的基础上多了些限制条件：

1.每个节点最多只能有2个子节点。

2.节点的子节点，分为左孩子节点和右孩子节点。

2.1 完全二叉树

在二叉树的基础上多了一个限制：

除最后一层外，若其余层都是满的，并且最后一层要么是满的，要么是在右边缺少连续若干节点

2.2 满二叉树

在二叉树的基础上多了一个限制：

每一层都是满的

 三、二叉查找树

在二叉树的基础上多了些限制条件

1.任何一个节点，如果它的左子树不为空，则左子树上所有节点的值都比它小

2.任何一个节点，如果它的右子树不为空，则右子树上所有节点的值都比它大

3.对于任意一个子树：左<根<右

 查找效率与树的高度成反比。

二叉查找树（其实这是二叉树的遍历）的遍历分为：

1.深度优先遍历(Depth First Search)

对于一颗二叉树，深度优先搜索是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。

1.前序遍历： 根节点----左子树----右子树  

以上图为例，结果是：80，40，10，50，115，90，95，130

2.中序变量： 左子树----根节点----右子树 在二叉查找树中使用序遍历并且打印的时候，最后打印出的结果会是从小到大的

以上图为例，结果是：10，40，50，80，90，95，115，130

3.后序遍历： 左子树----右子树----根节点

以上图为例，结果是：10，50，40，95，90，130，115，80

2.广度优先遍历（Breadth-First Search）

从树的root开始，从上到下从从左到右遍历整个树的节点

 1.层次遍历：按层次遍历    

以上图为例，结果是：80，40，115，10，50，90，130，95

这里之后有空会把几种遍历的Java实现代码添加上 

四、平衡二叉查找树（AVL）

平衡二叉查找树：

在二叉查找树的基础上多了些限制：

1.所有叶子的深度趋于平衡

2.每个节点的左子树和右子树的深度差的绝对值不超过1

平衡二叉树是在二叉查找树上引入是为了解决二叉排序树的不平衡性导致时间复杂度大大下降 

不平衡的二叉查找树可能会出现极端情况编程链表：

针对上面不平衡的二叉查找树调整成平衡树，主要是通过旋转最小失衡子树来完成。

1、平衡因子：左子树的高度减去右子树的高度。
2、最小失衡子树：离新插入的节点最近的，平衡因子最小的子树称为最小失衡子树。

旋转：

关于旋转更详细的请参考这篇博客：

AVL树的旋转图解和简单实现

左旋和右旋都是以子树为原点的：如b是a的子树，那么旋转就围绕b来进行。

如果b是a的左子树，那么就围绕b将a向右旋转，看着就像是a直接掉下来了，掉成了b的右子树。

如果b是a的右子树，那么就围绕b将a向左旋转，看着就像是a直接掉下来了，掉成了b的左子树。

插入节点时分四种情况，四种情况对应的旋转方法是不同的：

例如对于被破坏平衡的节点 a 来说：

插入方式	描述	旋转方式
LL	在a的左子树根节点的左子树上插入节点而破坏平衡	右旋转
RR	在a的右子树根节点的右子树上插入节点而破坏平衡	左旋转
LR	在a的左子树根节点的右子树上插入节点而破坏平衡	先左旋后右旋
RL	在a的右子树根节点的左子树上插入节点而破坏平衡	先右旋后左旋

以上面那个不平衡的二叉查找树为例：

在有10和11时，再插入12

本来二叉查找树是这样：

调整逻辑：

这是在节点10的右子树根节点11的右子树上插入节点12，属于RR，则此时，以11为根节点，将10左旋转变成11的左子节点：

然后插入13，并未导致失衡

然后插入14，变成了下图这样，导致失衡，需要旋转来调整

 调整逻辑：

1.找离新插入的节点最近的平衡因子最小的失衡子树，即是12->13->14。

这里说一下是怎么找的，11的失衡因子是-2，12的失衡因子是-2，13的失衡因子是-1。所以最小失衡因子是-2，

由于12离新插入的节点最近，所以，最终选出来的离新插入的节点最近的平衡因子最小的失衡子树是12->13->14。

2.以13为中心，将12左旋变成13的左子节点：

 最后插入15，又会导致失衡

调整逻辑： 

1.找离新插入的节点最近的平衡因子最小的失衡子树，即是11->13->14->15。

这里说一下是怎么找的，11的失衡因子是-2，13的失衡因子是-1，14的失衡因子是-1。所以最小失衡因子是-2，

最终选出来的离新插入的节点最近的平衡因子最小的失衡子树是11->13->14->15。

2.以13为原点，11要左旋变成13的左子节点

五、红黑树

在二叉查找树的基础上多了一些限制:

1、每个节点要么是黑色，要么是红色。
2、根节点是黑色。
3、所有叶子节点是黑色，即空节点（NIL）。
4、如果一个节点是红色的，则它的两个子节点必须是黑色的，也就是父子节点不能都为红色。
5、从一个节点到其所有叶子节点的所有路径上包含相同数目的黑节点。这样可以确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树

 

六、B树（B-Tree、Balance Tree）

B-树就是B树，不是读什么B减树。

平衡多路查找树

B树的阶数表示一个节点最多可以有多少个孩子节点。比如3阶B树，那一个节点最多可以有3个孩子节点。2阶B树相当于平衡二叉查找树。

图示3阶B树

一个M阶的B树符合以下条件：

1.根节点至少有2个孩子节点

2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m

3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m

4.所有的叶子结点都位于同一层。

5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

B树插入：

 比如以上方图示例子为例，插入一个25

第三排第二个节点，已经有了2个元素，23和36了，不能再放元素进去了（3阶B树，每个节点内最多只能是3-1=2个元素）

向上找，它的父节点，第二排第一个节点，也有两个元素20和40了，不能再放元素进去了。

再向上找，它的父节点就是根节点，第一排第一个节点，里面只有一个元素，还能再放一个元素进去，把新增的25插入根节点，拆分节点23.36和节点20.40.使其符合（左边大于右边）最后变成：

七、B+树

MySQL的Innodb的BTree索引就是用B+树实现的

这里标红高亮：之前去一家公司面试，第一轮面试官死活给我说Java8的ConcurrentHashMap就用CAS就能实现线程安全

第二轮，CTO给我说MySQL的Innodb的索引是用红黑树实现的。我有点怀疑人生。

不用红黑树的原因：

1.红黑树之类的这种平衡、近似平衡的二叉查找树，查找的效率跟树的高度相关。

2.数据库的索引是存在磁盘上的，需要考虑磁盘开销。用索引查找的时候不是把整个索引加到内存中，而是逐个加载磁盘页。一个磁盘页对应着索引树上的一个节点。

故：最坏的情况下，如果树高度为N，那么我们可以就要做N次磁盘IO开销。

3.当B+树节点中元素的数量多的时候，虽然查询是比较次数比二叉查找树、红黑树多，但是和磁盘IO速度相比，内存多耗时这点点是可以忽略的。

 

在B树的基础上：

1.B+树包含2种类型的结点：内部结点（也称索引结点）和叶子结点。根结点本身即可以是内部结点，也可以是叶子结点。根结点的关键字个数最少可以只有1个。

2.B+树与B树最大的不同是内部结点不保存数据，只用于索引，MySQL的数据（或者说记录）都保存在叶子结点中。

3.每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字（MySQL表中建索引的那一列的值）的大小形成一个顺序链接。