1.二叉搜索树、平衡二叉树
2.平衡二叉树之红黑树、
3.B 树、B+树、B* 树、
4.字典树 ( Trie树 )
二叉搜索树（又名二叉排序树）
特点：
1.左子树上的节点均小于根节点
2.右子树上的节点均大于根节点
二叉平衡树
为什么要有二叉平衡树，二叉搜索树的结构与值的插入顺序有关，同一组数，若其元素的插入顺序不同，二叉搜索树的结构是千差万别的。举个例子，给出一组数[1,3,5,8,9,13]
若按照[5,1,3,9,13,8]这样的顺序插入，其流程是这样的：
若按照[1,3,5,8,9,13]这样的顺序插入，其流程是这样的：
插入的序列越接近有序，生成的二叉搜索树就越像一个链表。
为了避免二叉搜索树变成“链表”，我们引入了平衡二叉树，即让树的结构看起来尽量“均匀”，左右子树的节点数尽量一样多。
如何生成二叉平衡树
先按照生成二叉搜索树的方法构造二叉树，直至二叉树变得不平衡，即出现这样的节点：左子树与右子树的高度差大于1。至于如何调整，要看插入的导致二叉树不平衡的节点的位置。主要有四种调整方式：LL（左旋）、RR（右旋）、LR（先左旋再右旋）、RL（先右旋再左旋）。
二叉平衡树特点：左子树与右子树的高度差不大于1
时间复杂度：log2n
出现不平衡时到底是执行LL、RR、LR、RL中的哪一种旋转，取决于插入的位置。可以根据值的大小关系来判断插入的位置。插入到不平衡节点的右子树的右子树上，自然是要执行LL旋转；插入到不平衡节点的左子树的左子树上，自然是要执行RR旋转；插入到不平衡节点的左子树的右子树上，自然是要执行LR旋转；插入到不平衡节点的右子树的左子树上，自然是要执行RL旋转。
经典面试算法题——判断一棵树是不是平衡二叉树(递归)
https://leetcode-cn.com/problems/balanced-binary-tree/
java:
class Solution {
private int height(TreeNode root) {
if (root == null) {
return -1;
}
return 1 + Math.max(height(root.left), height(root.right));
}
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
return Math.abs(height(root.left) - height(root.right)) < 2
&& isBalanced(root.left)
&& isBalanced(root.right);
}
};
