資料結構
網路
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 次瀏覽量
廣告