再回首数据结构—红黑树（一）

红黑树与AVL树一样同为二分搜索树，红黑树又称为是保持“黑平衡”的二叉树，红黑树最大高度为：2logn，红黑树由这么几个独特的特征：

1、每个节点或黑或红

2、根节点为黑色

3、每个叶子节点（最后的空节点）都为黑色

4、如果一个节点为红色，则他孩子节点全为黑色

5、从任意节点到叶子节点，经过的黑色节点为一样多的

6、所有红色节点都向左倾斜

在之前的二叉搜索树中我们在实现的节点结构中定义了用于存储元素的e、用于存放左子树的left、用于存放右子树的right等对象，而在AVL树中比二叉搜索树有所不同由于AVL需要维护左右子树的节点高度所以多了一个元素height用于存放节点的高度；

红黑树也是基于之前二叉搜索树变体而来的，在红黑树中节点也只比二叉搜索树多一个元素，二叉搜索树的节点由以下元素组成：

e ：用于存储节点元素

left：用于存储左子树

right：用于存储右子树

color：用于标志节点颜色，节点是红色或黑色

红黑树的代码定义：

type RBT struct {
    root    *RBTNode
    size    int
    compare Comparable
 }

 type RBTNode struct {
    e     interface{}
    left  *RBTNode
    right *RBTNode
    color bool
 }

根据红黑树的特性、定义可知：

1、大小为N的红黑树其高度不超过2logN

2、最坏情况下插入、查找元素的时间复杂度为：2logN

3、平均情况下插入、查找元素的平均复杂度为：logN

这里只简单介绍了红黑树的相关概念，下面将从代码实现的角度具体分析红黑树的实现；