接着上节讲数据结构中的树，要理解树，最重要的是要理解：二叉排序树、平衡二叉树和红黑树。今天就来讨论这几种树。

二叉排序树

      概念：二叉排序树又叫二叉查找树、二叉搜索树、二叉检索树。二叉排序树是二叉树的一个特化，二叉排序树规定了每个结点的关键字均大于其左子树上所有的结点的关键字，同时小于或等于其右子树上所有结点的关键字。所以，从二叉排序树的根结点一直往左走，直到底，就可以得到最小值；从根结点一起往右走，直到底，就可以得到最大值。二叉排序树的这种特殊性质使得它在查找元素方面的时候特别方便，每一次查找都可以去掉一半的元素，因此查找的时间是O(logN)。

      二叉排序树的算法：

（1）二叉排序树的查找算法

typedef struct Node
{
int data;               //结点值
    struct Node *parent;    //父结点
    struct Node *lchild;    //左结点
    struct Node *rchild;   //右结点
}TREENODE;

TREENODE *Search(TREENODE *root,int value)
{
if(root!=NULL)
    {
if(root->data==value)
        {
return root;
        }
else
        {
if(value < root->data)
            {
                Search(root->lchild,value);  //如果查找值比结点值小，递归左子树
            }
else
            {
                Search(root->rchild,value);  //如果查找值比结点值大，递归右子树
            }
        }        
    }
return root;
}

（2）二叉排序树的插入算法

       二叉排序树的插入算法很简单：从根结点开始，遇到键值大的就往左，遇到键值小的就往右。一直到底，就为插入点。

（3）二叉排序树的删除算法
       二叉排序树的删除算法有点小复杂：根据所要删除的结点有两个子结点还是只有一个或者没有子结点会有不同的处理。

      <1> 有两个子结点的情况：找到右子树中值最小的一个结点，用它的值替代当前的结点值，然后再把这个值最小的结点删除，也就是有两个子结点的情况是用最小的一个大于当前结点的关键字的结点替代了当前的结点。

     <2> 只有一个结点或者没有子结点的情况就简单多了，如果还有子结点就把子结点的位置往上挪，然后把当前结点删除。

平衡二叉树

     概念：形态匀称的二叉树称为平衡二叉树，其严格定义是：一棵空树是平衡二叉树；若T是一棵非空二叉树，其左、右子树为TL和TR，令hl和hr分别为左、右子树的深度，当且仅当：（1）TL、TR都是平衡二叉树；（2）|hl-hr|≤1时，T是平衡二叉树。

     平衡二叉树的旋转：平衡二叉树，在删除一些结点后，破坏了树的平衡，这个时候需要对树进行调整，以维持树的平衡。此时，用来调整树的平衡的方法就是常说的树的旋转。

     AVL树：博客园这篇文章讲到：http://blog.csdn.net/do2jiang/article/details/5529770

红黑树

     概念：红黑树（Red-Black Tree）是一种自平衡二叉树。但需要注意的是，红黑树并不是平衡二叉树，恰恰相反，红黑树放松了平衡二叉树的某些要求，由于一定限度的“不平衡”，红黑树的性能得到了提升。它的应用非常广泛，如STL（标准模板库）的map和set容器的内存存储结构就是红黑树。

     如果一个结点没有了子结点，则称为叶子结点，因为它是在树的边缘上。在红黑树中，叶子被假定为null或空。由于红黑树也是二叉排序树，它们当中每一个结点的值都必须大于或等于在它的左子树中的所有结点，并且小于或等于在它的右子树中的所有结点。这确保红黑树能够快速地在树中查找出指定的值。

      满足下列条件的二叉排序树是红黑树：

     （1）每个结点要么是“红色”的，要么是“黑色”的。

     （2）所有的叶子结点都是空结点，并且是“黑色”的。

     （3）如果一个结点是“红色”的，那么它的两个子结点都是“黑色”的。

     （4）任一结点到其叶子结点的每条路径上都包含相同数目的“黑色”结点。

     （5）根结点永远是“黑色”的。

       有了上面几条规则，就可以保证整棵树的平衡，也就等于保证了搜索的时间为O(logN)。

       下面就一棵红黑树：

　相关文章：

　　　　　　　•　　C/C++ 一点笔记（1）

　　　　　　　•　　C/C++ 一点笔记（2）