1. 树Tree

2. 二叉树 Binary Search

二叉树遍历

　　Pre-order/In-order/Post-order

• 1. 前序(Pre-order)：根-左-右
• 2. 中序(In-order)：左-根-右  （如果一棵树是二叉搜索树，它的中序是有序的）
• 3. 后序(Post-order)：左-右-根

3. 二叉搜索树 Binary Search Tree

树和链表没有本质的区别，当一个链表分出两个next时就把它称为树，从一维空间扩展为二维空间了。

这种扩展的好处：引入了二叉搜索树，当它本身是有序的话可以根据它和当前结点的大小关系分出来它只走左分支还是右分支（它的查询、插入和搜索的效率就是从O(n)变成Log(2n)的时间复杂度 ）。

二叉搜索树，也称二叉搜索树、有序二叉树（Ordered Binary Tree）、 排序二叉树（Sorted Binary Tree），
是指一棵空树或者具有下列性质的二叉树：
　　1. 左子树上所有结点的值均小于它的根结点的值；
　　2. 右子树上所有结点的值均大于它的根结点的值；
　　3. 以此类推：左、右子树也分别为二叉查找树。 （这就是 重复性！）

二叉搜索树的中序遍历是：升序排列

二叉搜索树的查找、插入、删除等操作

     它的时间复杂度为Log(2n)，n为它的结点个数。

 极端情况下，一直插入到左边，二叉搜索树就退化成了链表，就类似于链表的查询时间复杂度了。

保证性能的关键

　　1. 保证二维维度！ —> 左右子树结点平衡（recursively）
　　2. Balanced

4. 平衡二叉树

AVL、 红黑树

treap、 splay伸展树

B+树，二三树

 ①从7位置打折，34567， 8912

 ②相应的每个左右子树也类似的做下去。  这样就可以让整个树变得平衡。

但是不会等到它真正的自平衡二叉树里面（AVL、红黑树） 不会等到这个树病入膏肓了，再去平衡。而是在每一步进行插入或者删除的时候，都去判断它是否平衡，以及将它维护成二叉平衡树的状态。

5. AVL树

　　1. 发明者 G. M. Adelson-Velsky 和 Evgenii Landis
　　2. Balance Factor（平衡因子）：
　　　　是它的左子树的高度减去它的右子树的高度（有时相反）。  （因为二叉搜索树查询效率只与高度有关，和它节点的个数是没关的）
　　　　balance factor = {-1, 0, 1} 
　　3. 通过旋转操作来进行平衡（四种）

　　　　Self-balancing binary search tree

5.1 平衡因子

      所有叶子节点高度都是0，根结点J （平衡因子 = 右子树高度 - 左子树高度   4 - 3 = +1），

上图这颗树是一个严格的平衡AVL，它的平衡因子在 -1 0 1之间。保持平衡因子不超过绝对值 1就变成了一颗二叉搜索树。

开始最直观也是最自然的一种维护方式： 

最开始最经典的AVL树，它始终要保证任何一个结点它的平衡因子都只在 0 -1 1 ，这样就可以维护它的效率。

 这时它的平衡因子的范围不在是1的范围了，变成-2了。接下来就要进行旋转操作：

5.2 旋转操作

• 1. 左旋
• 2. 右旋
• 3. 左右旋
• 4. 右左旋

1. 左旋

2. 右旋

3. 左右旋

 其中C > B < A，它的左旋是B拉上来，C顶上去，这样它还是符合二叉树的性质，就变成了左左子树的情况如下：

4. 右左旋

 这里C < B，把它右旋上去，B挪下来，这样这个树还是满足二叉搜索树的性质

因为树的查找性能在于它的深度，记录它的左右子树深度即可，同时保证任何时候任何一个结点它的左右子树的深度差不超过绝对值1，

  当它不平衡时，基础的情况是上边四种，用左右旋来维护平衡。

如果结点本身有子树的情况，它要进行左右旋和右左旋怎么办

5.3 带有子树的旋转

上图进行右旋操作：
     E移上来，S往下之后E的右子树要挂在S的左子树去；

参考动画： https://zhuanlan.zhihu.com/p/63272157 

https://en.wikipedia.org/wiki/Tree_rotation#/media/File:Tree_Rebalancing.gif

右旋：

 插入3后变成如上图所示树的形态。这时它就变成-2了，就变成左左型了，把5往上提10挪下去，8挪到另外一边（8挂到10的左子树上。）

 上图是典型的右左子树情况，先进行右旋再左旋。

5.4 AVL总结

　　1. 平衡二叉搜索树（而且是自平衡的）
　　2. 每个结点存 balance factor = {-1, 0, 1}
　　3. 四种旋转操作

不足：结点需要存储额外信息、且调整次数频繁。 （而且存储的信息是一个int类型，因为它要+-*/；频繁调整维护成本高） ==>  引入近似平衡二叉树，不需要每次非常严格的来平衡。

6. 红黑树

红黑树是近似平衡二叉树的一种， 

红黑树是一种近似平衡的二叉搜索树（Binary Search Tree），它能够确保任何一个结点的左右子树的高度差小于两倍。具体来说，红黑树是满足如下条件的二叉搜索树：
　　• 每个结点要么是红色，要么是黑色
　　• 根节点是黑色
　　• 每个叶节点（NIL节点，空节点）是黑色的。
　　• 不能有相邻接的两个红色节点
　　• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

关键性质：

从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

AVL和红黑树的对比：

• AVL trees provide faster lookups than Red Black Trees because they are more strictly balanced.
• Red Black Trees provide faster insertion and removal operations than AVL trees as fewer rotations are done due to relatively relaxed balancing.
• AVL trees store balance factors or heights with each node, thus requires storage for an integer per node whereas Red Black Tree requires only 1 bit of information per node.
• Red Black Trees are used in most of the language libraries like map, multimap, multisetin C++ whereas AVL trees are used in databases where faster retrievals are required.

 map、set全部是红黑树

DB中用AVL，读多

数据结构-04 | AVL树| 红黑树

原文：https://www.cnblogs.com/shengyang17/p/13342220.html