介绍
树
树是一种非常重要的数据结构。类似于链表，树中的结点也是通过结点自带的指针相连。通常来说，树只有一个根结点，其余每个结点只有一个父结点。除了叶子结点之外，每个结点都有一个或多个孩子结点。
二叉树
二叉树是树结构中最基础的一种结构，其中每个结点最多有两个子结点。
二叉树还有两种特殊情况：
- 满二叉树：树中所有的叶子结点都位于树的最底层，其他层的所有结点均有两个子结点。换句话说，在当前的高度下，树中每一层的结点数量都达到最大值。
- 完全二叉树：树中最底层的所有结点连续出现在最左边，其他层的结点数量都达到最大值。
一般的二叉树没有太多具体的用途，因为其中的结点没有规律。举个例子，如果要查找二叉树中是否包含某个值，只能遍历所有结点进行检查。
二叉搜索树
二叉搜索树，也称为二叉查找树，是一种特殊的二叉树。相比一般的二叉树，二叉搜索树可以提高访问效率。
二叉搜索树的性质包括：
- 没有值相等的结点。
- 对于任意一个结点，其值大于左子结点的值，小于右子结点的值。
对于二叉搜索树，一般有三种操作：
- 查找：类似于二分查找。
- 插入：依赖查找操作，在进行插入。
- 删除：依赖查找操作，如果存在再进行删除。
假设二叉搜索树的高度为，查找的平均时间复杂度为 。当二叉搜索树退化为单链表时（最坏情况），此时查找效率为 。插入和删除的时间复杂度依赖于查找操作。
平衡二叉树
平衡二叉树是指平衡的二叉树，其中的“平衡”是通过限制树中每个结点的左子树和右子树的高度来实现的。因为一般的二叉树用处不大，所以“平衡”这一性质主要应用在二叉搜索树上。
平衡二叉搜索树主要是为了解决一般的二叉搜索树存在退化的问题。当二叉搜索树退化为单链表时，查找效率急剧下降。
平衡二叉搜索树有多种不同的实现，比如 AVL 树、红黑树等。
AVL 树
AVL 树是最早发明的平衡二叉搜索树。在AVL树中，每个结点的左子树和右子树的深度之差的绝对值不超过1。因此，AVL树是高度平衡的。
假设AVL树的高度为，查找、插入和删除在平均和最坏情况下的时间复杂度都是。
红黑树
多叉树（N叉树）
B树
B+树
堆
堆是一种特殊的完全二叉树，其中树中的所有结点存放在一个数组中，每一个结点对应了数组中的一个元素。堆中的结点没有使用指针相连，而是通过数组的下标来建立父子关系，因此空间效率比较高。
结点之间的关系如下：对于下标为i的结点，如果下标从0开始，那么左子结点和右子结点的下标分别是2*i+1和2*i+2。
普通的堆通常没有太大的实际意义，所以总是使用有一定规律的堆，比如
- 最大堆：对于任意一个结点，其值大于子结点的值。
- 最小堆：对于任意一个结点，其值小于子结点的值。