孩子四岁了，还不会写红黑树怎么办？

昨日我司论坛上有同事发出了深刻的焦虑！

这孩子也太不让人省心了，为了帮助同事我们准备写篇入门文档。翻出算法导论。嗯！还好功底保持的不错，看完还是一如既往的：

言归正传，最近不管是项目还是我们自己做的一些服务端，多多少少都遇到过一些性能问题，这时很多优化就绕不开树这个经典的数据结构了。

聊到树，又不可避免得提二叉排序树(查找树/搜索树)，很多复杂的数据结构都是基于这个延伸而来。红黑树（Red Black Tree）其实就是一种自平衡的二叉查找树，典型用途是实现关联数组。

简介

二叉排序树又称二叉查找树 二叉搜索树，是指一棵空树或者具有下列性质的二叉树：

• 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 左、右子树也分别为二叉排序树；
• 没有键值相等的结点。

查找算法

在二叉排序树b中查找x的过程为：

• 若b是空树，则搜索失败，否则下一步;
• 若x等于b的根节点的数据域之值，则查找成功；否则下一步;
• 若x小于b的根节点的数据域之值，则搜索左子树；否则下一步;
• 查找右子树。

伪码：

// 实际代码要注意回溯，详见github
SearchBST(T, key)
{
  if(!T)  //查找不成功
    return false;
  else if (key == T->data.key)  //查找成功
    return true;
  else if (key < T->data.key) // 在左子树中继续查找
    return SearchBST(T->lchild);
  else // 在右子树中继续查找
    return SearchBST(T->rchild, key);
}

插入算法

向一个二叉搜索树b中插入一个节点s的算法，过程为：

• 若b是空树，则将s所指结点作为根节点插入，否则下一步;
• 若s->data等于b的根节点的数据域之值，则返回，否则下一步;
• 若s->data小于b的根节点的数据域之值，则把s所指节点插入到左子树中，否则下一步;
• 把s所指节点插入到右子树中（新插入节点总是叶子节点）。

伪码：

// 实际代码详见github
InsertBST(T, e)
{
    if(!T)
    {	    
        s = new BiTNode;
        s->data = e;
        s->lchild = s->rchild = NULL;
        T = s;	//s为新的根结点
    }
    else if(e.key == p->data.key)
        return ;//关键字等于e.key的数据元素
    
    if (e.key < p->data.key)
		InsertBST(p->lchild, e);	//将e插入左子树
    else 
		InsertBST(p->rchild, e);	//将e插入右子树
 }

删除算法

在二叉排序树中删去一个结点，分三种情况讨论：

• 若*p结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。
• 若*p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树（当*p是左子树）或右子树（当*p是右子树）即可，作此修改也不破坏二叉排序树的特性。
• 若*p结点的左子树和右子树均不空。在删去*p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整。比较好的做法是，找到*p的直接前驱（或直接后继）*s，用*s来替换结点*p，然后再删除结点*s。

PS：这部分有点繁琐，就不贴伪码了，有兴趣直接去看git上的源码。

效率

每个结点的Ci为该结点的层次数。最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和logn成正比O(log2(n))。最坏情况下，当先后插入的关键字有序时，构成的二叉排序树为一棵斜树，树的深度为n，其平均查找长度为(n + 1) / 2，也就是时间复杂度为O(n)，等同于顺序查找。

因此，如果希望对一个集合按二叉排序树查找，最好是把它构建成一棵平衡的二叉排序树（平衡二叉树）。

完整代码

请点击 https://github.com/wufy1992/DataStructure/blob/master/BinarySortTree/BinarySortTree.cpp 前往github