数据结构

2

J

三阶B树

树

AVL树，自平衡二叉查找树，并非高度平衡（左右子节点高度差为1），所以非B树

5

如果插入的节点是个二分枝（只含一个节点直接插入即可）

红黑树

3

B | C

4

C

1

效率: (2 的 h次方) - 1 = n   h = log2(n + 1)效率与树的高度有关系 h 有关系 O(h)

B

插入节点2位于红色节点1左边先进左旋，然后进行右旋

也会进行相应的合并与分裂来维持树的平衡

树节点的高度差为1，效率接近O(log2(N+1))

顺序存储：由于不是完全二叉树所以他回浪费很多空间存空节点（子节点的关系是左：2*i + 1 右：2*i + 2）

A

E

右旋

会不会出现需要三次旋转的情况？（即需要旋转一个节点的子节的子节点然后再旋转子节点再旋转该节点）不会出现这种情况，树在构建的过程中就消除了这种可能。（因为他是一个递归过程当出现不平衡时，先将子节点平衡，父节点自然而然就也平衡了，而之旋转两次也是由他规定的高度差1所决定的）

G

左旋

F

NIL

.......

D   |   F

所以我们先旋转不平衡的节点的子节点再旋转该节点

（三节点是根节点）> 当每个节点的数量大于M-1时会进行分裂，叶子节点永远保持在同一层次，树的高度被抬高无非是因为根节点上升了高度，这也保证了树平衡的性质

这两种情况下我发现不平衡的位置都在内测（三角形的位置），当我们直接旋转不平衡的节点时，实际上只是将不平衡转移到另外一边，其高度并没有变化。当我们先将三角形旋转到外侧，再来旋转不平衡节点时，我们的三角行实际上是被位置提高的，而内测节点高度没有变化。所以我们可以得出旋转对内测节点的高度不会产生变化，而外侧则会被提高。（就好像绳子的两头拉一头另外一头会过来一样）

直接旋转根节点高度差任然为2

insert

二叉树

退化成链表

B树的基础上的一种变化，卫星数据只在叶子节点上，叶子节点间通过链表方式连接

依次插入1，2，4，5，，    其搜索效率变为O(N)

6

AVL与红黑树： AVL是严格的平衡二叉树，即他的左右 子树高度差为1，与AVL相比较红黑树并没有那么平衡（仅仅保证了黑平衡），所以在插入节点删除节点的维护方面，旋转更少效率更高，但是在查找方面，AVL高度更加低效率更加高。

平衡二叉树搜索树由于二叉搜索树的顺序插入会导致树的形状蜕变成链表，时间复杂度会从最好的O(log2(N+1) 变为O(N) (高度越高时间复杂度越差)，为了让树看起来更加矮我们让树节点的左右子树的深度差为1，使得树更加平衡

B   |   D

(三节点的父节点是二分支的插入情况)

效率：在最好的情况下即使每个节点都是三分支 log3(n + 1)

平衡树，即每个叶子节点到根节点的距离是 相同的。（高度平衡）

D

拉

二叉搜索树

AVL-树

其效率接近O(log2(N+1))

情况3和情况4

M阶B树每个节点可含M/2 ~M - 1 个节点。如2阶B树每个节点只含一个节点，有两个分支

A | B | C

再二叉树的基础上增加了顺序，搜索效率为O(N) ~ O(log2(N+1))

完全二叉树

1，插入的都是红色节点.2，红色节点只能出现在父节点的左边3，如果右子树为红色左旋4，如果红色左子树为红色右旋4，如果节点的左右节点都为红色，左右节点变为黑色该节点变为红色（向上传递），继续判断该节点的父节点。5，每次左右旋转，和向上传递红色都要判断该节点的父节点的左右子节点红黑情况6，父节点为黑色节点.

平衡树，所有叶子节点到根节点距离相同，M阶B树每个节点可含M/2 ~ M - 1个节点

1，红黑树的根节点是黑色的。2，红黑树根节点到所有叶子节点路径上的黑色节点数相同3，红黑树不可能同时出现两个红色节点4，所有叶子节点指向一个NIL节点

数据结构

存储方式

红黑树是一种二叉树，对于二叉树的操作我们更加简单，相比较2-3树而言。

H |  J

B | D

满二叉树

B+树的基础上，对非叶子节点兄弟节点间也进行了连接

插入节点的父节点存在左子节点为红色，颜色反转，最后设置父节点为黑色

每个节点可以含有1个或2个节点，所以每个节点可以有一个或两个分支

K

2-3树

B+树

Container

普通树结构存储需要维护2个额外的指针

为了使得树的高度不那么高，我们左适当的旋转操作使得树节点的高度差维持在1.1，左旋2，右旋3，左旋右旋4，右旋左旋

B-Tree（balance ）

普通树结构，每个节点含有两个分支，搜索效率O(N)

B*树

节点的出现顺序是从上往下从左往右出现的

此时根节点高度差为2

A 

这里考虑四种情况都是惹味3节点在左边的情况，还有六种情况为三节点出现在中间和右边。。。

每个节点最多只有2个 子节点

A的左边是小于A的结点，A B之间是大于A小于B的节点，B的右边是大于B的节点

3阶B树，效率最好情况是全为3f分支节点O(log3(N+1))

一个节点的左子节点的关键字一定小于右子节点

B+树 : 与B树的区别在于非叶子节点不存放卫星数据（实际需要的数据），卫星数据都放在叶子节点上，叶子节点之间通过链表的方式连接起来，所以说非叶子节点实际上只是表示一个范围。B+树相对B树而言可以存放更多的指针（因为不需要存放卫星数据），树的高度也显得更加胖矮。在数据库索引中，可以用更小的磁盘IO次数来找到需要的数据。又由于叶节点之间是通过链表方式连接，所以下次查找时也可以直接通过链表向右查找。B* 树：是B+树的进化版，他把非叶节点兄弟节点之间也通过指针连接起来，提高了查询效率。

二叉树搜索树

B-树

红黑树的插入删除操作涉及到平衡的维护（旋转）以及着色，实现起来较为复杂

平衡二叉搜索树

在树较为平衡的情况下二叉搜索树的效率较为高但是删除节点较为蛮烦需要维护树的结构（左边小于右边）

1.Insert（插入C节点后的平衡维护）

中序遍历可以输出升序数据，反向中序遍历可以输出降序（inorder(root.right); inorder(root.left))

2-3-树

2-3树3分支节点的分解效率大概为2log2(N+1)

2-3树转换成红黑树

插入节点1，由于节点2已经为红色，所以进行右旋交换2，3的颜色，发现节点2的左右 子树均为红，红色向上传递到2，2为根节点变黑

插入元素在节点的右边，进行旋转交换颜色

所有叶子节点都在同一层并且该层节点数是满的

H

效率与高度有关系，极端情况下二叉搜索树退化成链表效率变为N

I

如果不计算红色节点所有绿色节点到根节点的距离相同

B | D | F

A   |    B

散列与二叉树的比较：散列搜索效率为O(1），由于散列可能会产生hash碰撞效率并非为1，有时候当散列某元素维护的链表过长时，效率可能较为低下。散列的扩容以及装载因子需要考虑使得散列实现起来较为复杂

红黑树是黑节点平衡的，即我们去掉红色节点，所有叶子节点到根节点距离是相同。红黑树就是2-3树的3分支分解的情况。我们可以想象把2-3树3分支节点的最左边的节点独立出来，变成红色节点，我们就可以得到一颗红黑树。