数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会学
时尚类
法律研究在数据结构中从 Max HBLT 中删除任意元素
从 Max 或 Min HBLT 中删除任意节点不是优先队列或 HBLT 的标准操作。如果我们要从 HBLT 中删除一个节点 K，则必须遵循以下规则。
从树中分离根为 K 的子树，并用节点 K 的子树的融合取代它。
更新从 K 到根的路径中的 s 值，并根据需要交换此路径上的子树以维护 HBLT 的属性。
要更新从 K 到根的 s 值，我们需要每个节点的父指针。该更新 s 值到上级节点的操作将在我们看到 s 值未更改时停止。更改后的 s 值必须形成递增序列。因为每个节点必须比前一个大 1。由于 max s 值为 O(log n)，并且所有 s 值均为正，因此在更新过程中遇到的最大 O(log n) 节点。每个节点更新值都采用 O(1) 的时间。所以删除一个任意节点的总体复杂度是 O(log n)
更新时间： 11-Aug-2020
166 次浏览量
广告