二叉查找树

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大
于这个节点的值

平衡二叉树AVL

平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于1。

红黑树

二叉查找树的一直变种，可以解决瘸腿问题。二叉树的节点的左边子节点都是比它小的，右边节点都是比他大的 。但是如果一直都是左边太小的，会导致查找成为线性查找。
AVL树是一种严格的二叉树，任意节点的左右子树的平衡因子差值都不会大于1。整个过程通过旋转来保持平衡，旋转是比较耗时的，所以一般不用。
红黑树是一种弱平衡二叉树。每个节点增加一个存储位表示节点的颜色，可以是red或black，通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍。相对于要求严格的AVL树来说，它的旋转次数变少，所以对于搜索、插入、删除操作多的情况下，我们就用红黑树。
1、根节点是黑色的，每个叶子节点都是黑色的空节点。
2、子节点是红色或者黑色的。
3、任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
4、从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点
红黑树的高度近似log2n。

堆

堆是一个完全二叉树（除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列），堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。