1.小结
1.1 树是由边连接的节点组成
1.2 根是树当中最顶端的节点,它没有父节点
1.3 二叉树当中,每个节点最多有两个子节点
1.4 二叉搜索树当中,所有A节点左边子孙节点的关键字都比A小...1.8 遍历树是按照某种顺序访问树种所有的节点
1.9 最简单的遍历方法是前序,中序和后序
1.10 非平衡树是指根左边的后代比右边的多,或者相反
1.11 查找节点需要比较要找的关键字值和节点的关键字值...1.3 在红黑树当中,每一个节点都是黑色的或者是红色的,也可以是任意的两种颜色,蓝色多和黄色也是可以的,实际上,所说的节点有颜色是任意的彼方.可以使用其他类似的方法来表示,比如可以说每个节点不是深色就是浅色的...,都必须包含相同数目的黑色节点
1.5 修正违规的情况
假若颜色的规则被违反了,遵循以下规则进行修正
1.5.1 改变节点的颜色
1.5.2 执行旋转操作
2.红黑树的效率
和一般的二叉搜索树类似...,红黑树的查找,插入和删除的时间复杂度是相同的,在红黑树中的查找时间和在普通二叉搜索树的时间几乎完全一样,区别仅在于在每个节点当中需要增加一点储存空间来储存红黑树的颜色
3.小结
3.1 保持二叉树的平衡是非常重要的