浅谈二叉排序树（BST）

小魏同学嘻嘻 2023-07-12 原文

1.二叉排序树的定义

二叉排序树（也称二叉查找树）或者是一棵空树，或者是具有下列特性的二叉树：

若左子树非空，则左子树上所有结点的值均小于根结点的值。
若右子树非空，则右子树上所有结点的值均大于根结点的值。
左右子树也分别是一棵二叉排序树。

根据二叉排序树的定义，左子树结点值<根结点值<右子树结点值，所以，对二叉查找树进行中序遍历可以得到一个递增的有序序列。

2.二叉查找树的查找

二叉查找树的查找是从根结点开始，沿某个分支逐层向下比较的过程，若二叉排序树非空，先将给定值与根结点的关键字比较，若相等，则查找成功，若不等，如果小于根结点的关键字，则在根结点的左子树上查找，否则在根结点的右子树上查找，这显然是一个递归的过程。

二叉排序树的非递归查找算法：

BSTNode *BST_Search(BiTree T,ElemType key){
    while(T!=NULL&&key!=T->data){    //若树空或者等于根结点值，则结束循环
        if(key<T->data) T=T->lchild;    //小于，则在左子树上查找
        else T=T->rchild;
    }
    return T;
}

同理，递归算法如下：

BSTNode *BST_Search(BiTree T,ElemType key){
    if(T==null){
        return null;    //如果树为空，则返回null
    }
    if(key == T->data)    //如果key与根结点的值相等
        return T;
    if(key<T->data)
        return BST_Search(T->lchild,key);
    if(key>T->data)
        return BST_Search(T->rchild,key);
}

3.二叉排序树的插入：

二叉排序树作为一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找过程中，当书不存在关键字值等于给定值的特点时再进行插入的。

插入结点的过程如下：若原二叉排序树为空，则直接插入该结点，否则，若关键字k小于根结点值，则插入到左子树，若关键字k大于根结点值，则插入到右子树，插入的结点一定是一个新添加的叶节点，且是查找失败时查找路径上的访问的最后一个结点的左孩子或右孩子，过程如下图所示：

int BST_Insert(BiTree &T,KeyType k){
    if(T==NULL){
        T=(BiTree)malloc(sizeof(BSTNode));
        T->key=k;
        T->lchild=T->rchild=NULL;
        return 1;    //返回1，插入成功
    }
    else if(k==T->key){    //树中存在相同关键字的结点，插入失败
        return 0;
    }
    else if(k<T->key){
        return BST_Insert(T->lchild,k);
    }
    else{
        return BST_Insert(T->rchild,k);
    }
}

4.二叉排序树的构造：

void Creat_BST(BiTree &T,KeyType str[],int n){
    T=NULL;    //初始时T为空树
    int i=0;
    while(i<n){    //依次将每个关键字插入到二叉排序树中
        BST_Insert(T,str[i]);
        i++;
    }
}

5.二叉排序树的删除

在二叉排序树中删除一个结点时，不能把以该结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下，将因删除结点而断开的二叉链表重新连接起来，同时确保二叉排序树的性质不会丢失。

若被删除的结点z是叶子结点，则直接删除，不会破坏二叉排序树的性质。
若结点z只有一棵左子树或是右子树，则让z的子树成为z父结点的子树，替代z的位置。
若结点z有左、右两棵子树，则令z的直接后继或直接前驱替代z，然后从二叉排序树中删去这个直接后继（或者直接前驱），这样就转换成了第一或第二种情况。

6.二叉排序树的查找效率分析

二叉排序树的查找效率，主要取决于树的高度，若二叉排序树的左、右子树的高度之差的绝对值不超过1，则这样的二叉排序树称为平衡二叉树，它的平均查找长度为O(log2n)。若二叉排序树是一个只有左（右）孩子的单支树（类似于有序的单链表），则其平均查找长度为O(n)。

在最坏情况下，即构造二叉排序树的输入序列是有序的，则会形成一个倾斜的单支树，此时二叉排序树的性能显著变坏，树的高度也增加为元素个数n

在等概率下，上图的查找成功的平均查找长度为：

ASL = (1+2*2+3*4+4*2)/10 = 2.5

从查找过程看，二叉排序树与二分查找相似，就平均时间性能而言，二叉排序树上的查找和二分查找差不多，但二分查找的判定树唯一，而二叉排序树的查找不唯一，相同的关键字其输入顺序不同可能生成不同的二叉排序树。

就维护表的有序性而言，二叉排序树无序移动结点，只需修改指针即可完成插入部和删除操作，平均时间为O(log2n)。二分查找的对象是有序顺序表，若有插入和删除结点操作，所花的代价是O(n)；若有序表是动态查找表，则应选择二叉排序树作为其逻辑结构。

有关浅谈二叉排序树（BST）的更多相关文章

ruby-on-rails - 需要帮助最大化多个相似对象中的 3 个因素并适当排序 - 2
我需要用任何语言编写一个算法，根据3个因素对数组进行排序。我以度假村为例(如Hipmunk)。假设我想去度假。我想要最便宜的地方、最好的评论和最多的景点。但是，显然我找不到在所有3个中都排名第一的方法。Example(assumingthereare20importantattractions):ResortA:$150/night...98/100infavorablereviews...18of20attractionsResortB:$99/night...85/100infavorablereviews...12of20attractionsResortC:$120/night
ruby-on-rails - 在具有 ActiveRecord 条件的相关模型中按字段排序 - 2
我正在尝试按Rails相关模型中的字段进行排序。我研究的所有解决方案都没有解决如果相关模型被另一个参数过滤？元素模型classItem相关模型:classPriority我正在使用where子句检索项目:@items=Item.where('company_id=?andapproved=?',@company.id,true).all我需要按相关表格中的“位置”列进行排序。问题在于，在优先级模型中，一个项目可能会被多家公司列出。因此，这些职位取决于他们拥有的company_id。当我显示项目时，它是针对一个公司的，按公司内的职位排序。完成此任务的正确方法是什么？感谢您的帮助。PS-我
ruby - 按数字(从大到大)然后按字母(字母顺序)对对象集合进行排序 - 2
我正在构建一个小部件来显示奥运会的奖牌数。我有一个“国家”对象的集合，其中每个对象都有一个“名称”属性，以及奖牌计数的“金”、“银”、“铜”。列表应该排序:1.首先是奖牌总数2.如果奖牌相同，按类型分割(金>银>铜，即2金>1金+1银)3.如果奖牌和类型相同，则按字母顺序子排序我正在用ruby做这件事，但我想语言并不重要。我确实找到了一个解决方案，但如果感觉必须有更优雅的方法来实现它。这是我做的:使用加权奖牌总数创建一个虚拟属性。因此，如果他们有2个金牌和1个银牌，加权总数将为“3.020100”。1金1银1铜为“3.010101”由于我们希望将奖牌数排序为最高的，因此列表按降序排
ruby-on-rails - 在不重新查询数据库的情况下重新排序 Rails 中的事件记录？ - 2
例如，假设我有一个名为Products的模型，并且在ProductsController中，我有以下代码用于product_listView以显示已排序的产品。@products=Product.order(params[:order_by])让我们想象一下，在product_listView中，用户可以使用下拉菜单按价格、评级、重量等进行排序。数据库中的产品不会经常更改。我很难理解的是，每次用户选择新的order_by过滤器时，rails是否必须查询，或者rails是否能够以某种方式缓存事件记录以在服务器端重新排序？有没有一种方法可以编写它，以便在用户排序时rails不会重新查询结果
ruby - 在 Ruby 中实现二叉树 - 2
我一直在尝试在Ruby中实现BinaryTree类，但我得到了stackleveltoodeep错误，尽管我似乎没有在该特定代码段中使用任何递归:1.classBinaryTree2.includeEnumerable3.4.attr_accessor:value5.6.definitialize(value=nil)7.@value=value8.@left=BinaryTree.new#stackleveltoodeephere9.@right=BinaryTree.new#andhere10.end11.12.defempty?13.(self.value==nil)?true:
ruby-on-rails - 如何对对象数组进行排序？ - 2
我有一个对象如下:[{:id=>2,:fname=>"Ron",:lname=>"XXXXX",:photo=>"XXX"},{:id=>3,:fname=>"Dain",:lname=>"XXXX",:photo=>"XXXXXXX"},{:id=>1,:fname=>"Bob",:lname=>"XXXXXX",:photo=>"XXXX"}]我想按fname排序，不区分大小写，所以它会导致编号:1,3,2我该如何排序？我正在尝试:@people.sort!{|x,y|y[:fname]x[:fname]}但这没有任何效果。最佳答案
ruby - 使用自定义排序首选项对数组进行排序？ - 2
有人可以告诉我如何根据自定义字符串对嵌套数组进行排序吗？比如有没有办法排序:[['Red','Blue'],['Green','Orange'],['Purple','Yellow']]“橙色”、“黄色”，然后是“蓝色”？最终结果如下所示:[['Green','Orange'],['Purple','Yellow'],['Red','Blue']]它不是按字母顺序排序的。我很想知道我是否可以定义要排序的值以实现上述目标。最佳答案 sort_by对于这种排序总是非常方便:a=[['Red','Blue'],['Green','Ora
Ruby 将对象插入现有的已排序对象数组 - 2
我有以下现有的Dog对象数组，它们按age属性排序:classDogattr_accessor:agedefinitialize(age)@age=ageendenddogs=[Dog.new(1),Dog.new(4),Dog.new(10)]我现在想插入一条新的狗记录，并将它放在数组中的正确位置。假设我想插入这个对象:another_dog=Dog.new(8)我想把它插入到数组中，让它成为数组中的第三项。这是一个人为的示例，旨在演示我特别想如何将一个项目插入到现有的有序数组中。我意识到我可以创建一个全新的数组并重新对所有对象进行排序，但这不是我的目标。谢谢!
ruby - 如何排序不是简单的哈希(哈希的哈希) - 2
我有一个这样的哈希{55=>{:value=>61,:rating=>-147},89=>{:value=>72,:rating=>-175},78=>{:value=>64,:rating=>-155},84=>{:value=>90,:rating=>-220},95=>{:value=>39,:rating=>-92},46=>{:value=>97,:rating=>-237},52=>{:value=>73,:rating=>-177},64=>{:value=>69,:rating=>-167},86=>{:value=>68,:rating=>-165},53=>{:va
ruby - 根据值然后键对ruby中的哈希进行排序 - 2
如何在ruby中先根据值然后根据键对散列进行排序？例如h={4=>5,2=>5,7=>1}将排序为[[7,1],[2,5],[4,5]]我可以根据值进行排序h.sort{|x,y|x[1]y[1]}但我不知道如何根据值进行排序，然后在值相同时键入最佳答案 h.sort_by{|k,v|[v,k]}这使用了Array的事实混入Comparable并定义逐元素。注意上面等价于h.sort_by{|el|el.reverse}相当于h.sort_by(&:reverse)这可能会或可能不会更具可读性。如果你知道Hashes一般都是先

浅谈二叉排序树（BST）

有关浅谈二叉排序树（BST）的更多相关文章

随机推荐