二叉树的概念#
满二叉树#
一颗二叉树只有度（度是孩子结点）为 0 的结点和度为 2 的结点，且度为 0 的结点在同一层上。
- 总共有 $2^{k}-1$ 个结点（k 为树的深度）
- 每一层有 $2^{n-1}$ 个结点（n 为当前层数）
完全二叉树#
只允许最后一层不为满，且最后一行必须是从左往右排序不能有间隔。
- 底层可以有 1~$2^{k-1}$ 个结点，中间不能有间隔。
二叉搜索树#
二叉搜索树是一个有序树，又名 二叉排序树 、二叉查找树。
- 若左子树非空，则左子树上所有结点的值均小于其根结点的值；
- 若右子树非空，则右子树上所有结点的值均大于其根结点的值；
- 左右子树分别为二叉排序树；
- 没有键值相等的结点。
二叉搜索树的根结点是确定不变的的，当在进行数据的插入和删除的时候会造成二叉树朝着单链表的方向发展，降低了数据的查询效率，所有就有平衡二叉树。
平衡二叉树#
AVL 树（Adelson-Velsky and Landis Tree）
平衡二叉树是基于二叉树优化而来。
- 可以是空树；
- 任何一个结点的左子树与右子树的都是平衡树，并且高度之差的绝对值不超过 1；
实现平衡的方法
平衡因子：某结点的左子树和右子树的高度（深度）差即为结点平衡因子，平衡二叉树中不存在平衡因子大于 1 的结点（只有 -1、0、1）。
平衡二叉搜索树#
平衡二叉搜索树是一个空树或者左右子树都是平衡二叉树(高度差不超过 1)。