替罪羊树

✍ dations ◷ 2024-12-23 06:56:13 #树结构

替罪羊树是计算机科学中，一种基于部分重建的自平衡二叉搜索树。在替罪羊树上，插入或删除节点的平摊最坏时间复杂度是O(log n)，搜索节点的最坏时间复杂度是O(log n)。

在非平衡的二叉搜索树中，每次操作以后检查操作路径，找到最高的满足max(size(son_L),size(son_R))>alpha*size(this)的结点，重建整个子树。
这样就得到了替罪羊树，而被重建的子树的原来的根就被称为替罪羊节点。
常数alpha一般选择为0.7左右。
通过势能分析，至少对于只有插入操作的替罪羊树，单操作均摊复杂度为O(log n)。
删除操作可以通过设置“删除”标记完成，复杂度即为查找复杂度O(log n)。

相关

精子发生精子发生（英语：spermatogenesis）是有性生殖的雄性动物的睾丸中，生殖细胞从精原细胞一直发育到成熟的精子的过程。这一过程始于精原干细胞的有丝分裂，邻近生精小管的基底膜。繁殖
不当换位不当换位（illicit conversion）是一种形式谬误。换位法只能套用在直言命题的全称否定型（E型）和特称肯定型（I型），而不能用在全称肯定型（A型）和特称否定型（O型），套用在后者即是不当换位。形
烷基化反应烷基化是烷基由一个分子转移到另一个分子的过程。近现代产业中，在整个炼油过程中，烷基化可以将分子按照需要重组，增加产量，对油品应用是非常重要的一环。以标准的炼油过程来做说
用药假期药物假期（drug holiday）是指病患停止用药一段时间，可能从几天、几个月甚至到几年。有许多医疗方式中有包括药物假期在内，最有名的是人类免疫缺陷病毒治疗，有研究发现停药可以促进
鲟科鲟科是鲟形目下的一个科，其下有4属、27种鱼类，其中4种可能已经灭绝。鲟鱼生活在海洋和大的河流、湖泊中，体长最大的超过9米。其化石记录可追溯到2.45至2.08亿年前的三叠纪时期
眉山市眉山市（四川话拼音：Mi2shan1；本地发音：），简称眉，古称眉州，是中华人民共和国四川省下辖的地级市，位于四川省中部。市境北临成都市，东界资阳市、内江市，南接乐山市，西邻雅安市。地处四川盆
2019冠状病毒病文莱疫情2019冠状病毒病文莱疫情，介绍在2019冠状病毒病疫情中，在文莱发生的情况。截至2020年3月15日，文莱累计确诊37例新型冠状病毒肺炎病例。2020年3月9日，文莱卫生部（英语：Ministry of H
名仓刊名仓刊（日语：なぐらしおり、1893年11月23日 - 1953年11月7日）为大日本帝国陆军军人。最终阶级陆军中将。东京出身。1914年（大正3年）5月、陆军士官学校（26期）毕业。同年12月、任官
满宫辉仁亲王满宫辉仁亲王（みつのみやてるひとしんのう、1893年11月30日－1894年8月17日）、日本皇族明治天皇第五皇子。母为园祥子。1893年12月7日、宫内大臣土方久元子爵之名为命名作为告示
ElasticsearchElasticsearch是一个基于Lucene库的搜索引擎。它提供了一个分布式、支持多租户的全文搜索引擎，具有HTTP Web接口和无模式JSON文档。Elasticsearch是用Java开发的，并在Apache许