資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究資料結構中的層級連結(2,4)樹
在本節中，我們將解釋如何透過引入層級連結，(2,4)樹能夠支援高效的指搜尋。本節中解釋的思想也適用於更一般的平衡高度樹類，表示為(a, b)樹，其中b ≥ 2a。
(2,4)樹定義為一種平衡高度搜索樹，其中所有葉子節點具有相同的深度，並且所有內部節點的度數為二、三或四。元素儲存在葉子節點中，內部節點僅儲存搜尋鍵以指導搜尋。由於每個內部節點的度數至少為二，因此(2,4)樹的高度為O(log n)，並且支援在O(log n)時間內進行搜尋。 (2,4)樹的一個重要特性是，由手指提供的插入和刪除操作的攤銷時間為O(1)（此屬性不適用於(2, 3)樹，在(2, 3)樹中，存在m次插入和刪除操作的序列需要Θ(m log m)時間）。此外，具有m個葉子節點的(2,4)樹可以拆分為大小為m1和m2的兩棵樹，攤銷時間為O(log min(m1, m2))。類似地，大小為m1和m2的兩棵(2,4)樹可以在攤銷時間O(log min(m1, m2))內連線（串聯）。
為了支援指搜尋，(2,4)樹透過層級連結進行增強，使得所有具有相同深度的節點都透過雙向連結串列連結在一起。下圖顯示了一個帶有層級連結的(2,4)樹。請記住，所有邊都表示雙向連結。在(2,4)樹的插入、刪除、拆分和連線過程中，額外的層級連結很容易維護。
為了完成從X到Y的指搜尋，我們首先檢查Y是否在X的左側或右側。假設Y在X的右側（不失一般性）。然後，我們訪問從X到根節點的路徑，同時檢查路徑上的節點V及其右側鄰居，直到確定Y包含在以V或V的右側鄰居為根的子樹中。然後終止向上搜尋，並在V和/或V的右側鄰居處分別啟動最多兩個向下搜尋y。在圖1中，從j到t的指搜尋過程中跟隨的指標用粗線表示。
O(log d)搜尋時間來自以下觀察：如果我們將向上搜尋推進到節點V的父節點，則Y位於V的右側鄰居的最左側子樹的右側，即d至少以迄今為止達到的高度呈指數增長。
在圖1中，我們從標記為“l n”的內部節點推進到標記為“h”的節點，因為從“s”我們知道Y位於以節點“q r”為根的子樹的右側。
層級連結(2,4)樹的構造可以直接推廣到層級連結(a, b)樹，該樹可以在外部儲存器中實現。透過選擇a = 2b和b，使得內部節點適合外部儲存器中的一個塊，我們實現了支援在O(1)記憶體傳輸中進行插入和刪除以及在O(logb n)記憶體傳輸中進行指搜尋的外部儲存器指搜尋樹。
515 次瀏覽
