树

数据结构中有很多树结构，二叉树、二叉搜索树、二叉搜索平衡树、红黑树、B树、B+树。

二叉树（Binary Tree）

二叉树的节点至多两个子节点。

满二叉树和完全二叉树

完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树

缺点：没有排序性质，查找费时。

二叉查找树（Binary Search Tree）

定义：左子树的所有节点都小于根节点，右子树的所有节点都大于等于根节点。
性质：对二叉查找树进行中序遍历，可以得到有序的数列

缺点：查找和插入的复杂度是O(logn)，但是如果树结构退化成链表的时候，复杂度就会变成O(n)

平衡二叉查找树（AVL树）

性质：保持二叉查找树的定义，并且增加了平衡特性：左右子树的高度只差不超过1。

红黑树

B树

B+树