一、树的种类二、二叉排序树三、平衡二叉树四、红黑树1.每个节点不是黑色就是红色2.根节点永远都是黑色的3.叶子结点都是黑色的4.如果一个节点的颜色是红色的,那么他的子节点的颜色一定是黑色的5.从根节点出发到任意一个叶子结点,走过的路径上的黑色节点数目相同结论:在红黑树当中最长的链不会超过最短链的2倍最短:黑黑黑黑黑黑最长:黑红黑红黑红黑红黑红黑五、哈夫曼树和哈夫曼编码