技術問答
技術文章
iT 徵才
Tag
聊天室
2024 鐵人賽
登入/註冊
問答
文章
Tag
邦友
鐵人賽
搜尋
2024 iThome 鐵人賽
DAY
26
0
佛心分享-刷題不只是刷題
[30天LeetCode挑戰] 每天一點演算法,讓技巧融會貫通
系列 第
26
篇
[Day26] 2-3-4樹 筆記
16th鐵人賽
很懶欸
2024-10-10 18:04:48
63 瀏覽
分享至
2-3-4 樹筆記
基本定義
2-3-4 樹
是一種
自平衡多路搜尋樹(Balanced Multi-Way Search Tree)
,每個節點最多可以包含 2、3 或 4 個子節點,因此命名為 2-3-4 樹。
2-3-4 樹的節點有以下三種類型:
2-節點
:包含 1 個鍵與 2 個子節點。
3-節點
:包含 2 個鍵與 3 個子節點。
4-節點
:包含 3 個鍵與 4 個子節點。
鍵值大小順序規則
:
所有左子樹的鍵值小於父節點的第一個鍵值。
中間子樹的鍵值介於父節點的兩個鍵值之間。
右子樹的鍵值大於父節點的第二個鍵值。
特點
2-3-4 樹是一種
完全平衡樹
,所有葉節點在同一層,樹的高度盡量保持最低,以便在最壞情況下仍能保證
O(log n)
的操作效率。
與其他平衡樹相比,2-3-4 樹因其節點可以容納多個鍵值,所以在插入與刪除時,調整的次數比 AVL 樹或紅黑樹少。
操作時間複雜度
搜尋(Search)
:
O(log n)
插入(Insert)
:
O(log n)
刪除(Delete)
:
O(log n)
常見操作
插入(Insertion)
從根節點開始
:
若根節點是 4-節點,則先分裂根節點,將中間鍵值提升,然後繼續插入。
找到適當的子樹位置
:
按照鍵值大小找到合適的子樹進行遞迴搜索。
處理 4-節點
:
當遇到 4-節點時,將該節點進行分裂,將中間的鍵值提升到父節點(如果父節點也是 4-節點,則繼續分裂),將 4-節點分解為兩個 2-節點。
插入新鍵值
:
將新鍵值插入到合適的 2-節點或 3-節點中,保證節點內的鍵值順序正確。
刪除(Deletion)
找到要刪除的鍵值位置
:
若刪除的是葉節點的鍵值,直接刪除即可。
刪除內部節點的鍵值
:
用前驅或後繼鍵值替換要刪除的鍵值,然後在葉節點中刪除前驅或後繼鍵值。
處理 2-節點的鍵值不足
:
若刪除操作導致節點鍵值不足(2-節點變成 1-節點),則需要進行「鍵值借用」或「合併」操作。
鍵值借用
:從相鄰兄弟節點中借取一個鍵值,使當前節點成為 2-節點。
合併節點
:若兄弟節點是 2-節點,則將兄弟節點與父節點的鍵值合併,形成新的 3-節點或 4-節點。
節點分裂(Node Split)
當 4-節點插入新鍵值後無法容納更多的鍵值時,需要進行節點分裂:
將 4-節點中的中間鍵值提升到父節點。
4-節點分解為兩個 2-節點。
若父節點也是 4-節點,則繼續對父節點進行分裂,直到樹恢復平衡。
優缺點
優點
高度平衡
:所有葉節點都位於相同的深度,避免了退化成鏈表的情況。
操作簡單
:每個節點最多只有三個鍵值,可以有效地減少旋轉與調整次數。
穩定性高
:適合用於資料庫索引等需要大量查詢操作的場景。
缺點
節點需要儲存更多鍵值
:相較於二元搜尋樹,每個節點需要儲存更多鍵值與子節點指標,因此節點的記憶體消耗較大。
插入與刪除較為複雜
:當節點鍵值數過多時,可能需要進行多次分裂或合併操作。
使用場景
資料庫系統索引結構
:如 B 樹、B+ 樹等結構的基礎,用來提升資料庫查詢效能。
檔案系統管理
:用來建立檔案系統的層次結構,方便快速查找檔案或資料夾。
平衡樹管理
:適合用於鍵值數量較多且需要平衡操作的應用場景。
留言
追蹤
檢舉
上一篇
[Day25] 2-3樹 與 紅黑樹 筆記
下一篇
[Day27] 關於Heap的刷題筆記(1046)
系列文
[30天LeetCode挑戰] 每天一點演算法,讓技巧融會貫通
共
30
篇
目錄
RSS系列文
訂閱系列文
2
人訂閱
26
[Day26] 2-3-4樹 筆記
27
[Day27] 關於Heap的刷題筆記(1046)
28
[Day28] 2-3樹刷題筆記(701)
29
[Day29] LeetCode第938題 Range Sum of BST 刷題筆記
30
[Day30] LeetCode第1382題 Balance a Binary Search Tree 刷題筆記
完整目錄
直播研討會
{{ item.subject }}
{{ item.channelVendor }}
{{ item.webinarstarted }}
|
{{ formatDate(item.duration) }}
直播中
立即報名
尚未有邦友留言
立即登入留言
iThome鐵人賽
參賽組數
1064
組
團體組數
40
組
累計文章數
21834
篇
完賽人數
595
人
看影片追技術
看更多
{{ item.subject }}
{{ item.channelVendor }}
|
{{ formatDate(item.duration) }}
直播中
熱門tag
看更多
15th鐵人賽
16th鐵人賽
13th鐵人賽
14th鐵人賽
12th鐵人賽
11th鐵人賽
鐵人賽
2019鐵人賽
javascript
2018鐵人賽
python
2017鐵人賽
windows
php
c#
windows server
linux
css
react
vue.js
熱門問題
程式開發人員的電腦軟體是否受MIS管理
玩玩SQL~查詢當月排班各區間的班別~SQL改善完成!
VS Code 啟動好慢
Fortigate 防火牆政策設定問題
交換器設備
UPS加電池櫃以後確認的問題
網域內所有裝置密碼強度變更
請問有中國大陸用語轉台灣用語AI工具嗎?
Win11 耳機一邊沒有聲音
fortinet中文客服
熱門回答
程式開發人員的電腦軟體是否受MIS管理
交換器設備
如何將Windows 檔案總管內圖示放大?
玩玩SQL~查詢當月排班各區間的班別~SQL改善完成!
VS Code 啟動好慢
熱門文章
Day29 什麼?肛門也能下棋!
[ANNOUNCE] New Kafka PMC Member: Chia-Ping Tsai
Day 31 - 完賽 :)
Day 30 - 例外處理的幕後真相
[Day30] 噴殺蟲劑的房間要通風多久才能住進去
IT邦幫忙
×
標記使用者
輸入對方的帳號或暱稱
Loading
找不到結果。
標記
{{ result.label }}
{{ result.account }}