算法图解-终极版-树-一颗倒长的树
- BST
二分收索树， insert, delete 和find 操作， 需要先建立树的数据结构， 然完成具体操作。按照二分查找树的定义完成插入， 查找同样道理， 删除略难， 需要适当规定删除后的操作， 因为：
如果为叶子节点， 直接删除，
如果该节点， 有一个孩子， 子承父业，
如果两个， 规定长子代替该节点
如果删除根节点， 规定一个叶子节点为根节点， 然后左旋或右旋。
当然， 如果算法能读懂就不叫算法了， 需要看图， 然后思考具体步骤， 然后写代码。不写代码就像学会算法，呵呵。 - AVL
一种局部自平衡树， 如果一颗树的左右子树的深度之差的绝对值大于等于2， 那么需要局部平衡， 通过左右旋转的算法， 得到。
如上图， 树不平衡， 那么需要右旋转，算法为右旋算法：
最终结果如上 - Splay
首先Splay树不是平衡树， 但比一般的插入好，因为， 插入后接近平衡。
算法：
首先按照BST插入， 插入到叶子上
然后旋转， 一直到树根
最后返回结果。结果任然为BST。
4. B树
一个节点上最多有n（n>=3)个孩子， index最用B树， 加快查找速度， 同时节省存储空间。与BST相似， 就是多了以上一条。同时， 一个节点不能超过两个数字。
5. 2-3-4树， 类似于B树， 一种可以出现n（n>=2 and n <=4)个孩子。
6. 红黑树
7. B+树