昨日我司论坛上有同事发出了深刻的焦虑!
这孩子也太不让人省心了,为了帮助同事我们准备写篇入门文档。翻出算法导论。嗯!还好功底保持的不错,看完还是一如既往的:
言归正传,最近不管是项目还是我们自己做的一些服务端,多多少少都遇到过一些性能问题,这时很多优化就绕不开树这个经典的数据结构了。
聊到树,又不可避免得提二叉排序树(查找树/搜索树),很多复杂的数据结构都是基于这个延伸而来。红黑树(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