我讀的書CLRS,我們有M路B樹,其中m爲偶數。但是有沒有B樹是m的奇數,如果有的話,我們該如何修改本書給出的代碼。m-way B-tree可以奇怪嗎?
0
A
回答
0
由M路B樹我假設你的意思是B樹,每個內部節點被允許最多有米以下的兒童。根據CLRS對B樹的定義:
節點對於它們可以包含的鍵的數量有上限和下限。我們用一個固定的整數t≥2表示這些邊界,稱爲B樹的最小度數:...一個內部節點最多可以有2t兒童。
所以兒童的最大數量將始終是甚至 - 由這個定義不能是奇數。
但是,這不是B樹的唯一定義。有許多定義略有差異,最終對整體性能沒有什麼影響。這可能會導致混淆。有一些B樹定義允許奇數上限和那些沒有的上限。 CLRS的定義確實爲孩子們不要奇上限內部節點的數量。然而,B樹的另一個正式定義是Knuth [1998](The Art of Computer Programming,Volume 3(Second ed。),Addison-Wesley,ISBN 0-201-89685-0)。 Knuth的定義確實允許奇數上限。儘管CLRS列舉了t≥2的形式(t,2t)的所有最小最大樹範圍,但Knuth枚舉了k≥2的形式(ceil(k/2),k)的所有樹界。
Knuth Order, k | (min,max) | CLRS Degree, t
---------------|-------------|---------------
0 | - | –
1 | – | –
2 | – | –
3 | (2,3) | –
4 | (2,4) | t = 2
5 | (3,5) | –
6 | (3,6) | t = 3
7 | (4,7) | –
8 | (4,8) | t = 4
9 | (5,9) | –
10 | (5,10) | t = 5
因此,例如,一個2-3 tree,(2,3),是B樹Knuth的順序3.但由於它具有奇數上限它不是有效的CLRS樹。
更改代碼並不容易,因爲B樹根據變量t有很多代碼。其中最大的變化將是裏面:B-TREE分裂孩子(X,I),你需要找到一種方式來分割孩子奇數兒童(偶數鍵)爲節點y
和z
。這兩個結果節點中的一個將比另一個擁有更多的密鑰。如果您正在尋找代碼,我建議您在Internet上查找使用類似於Knuth的定義的B樹的實現(例如,搜索「Knuth Order B-tree」)。
相關問題
- 1. BetterAuthorizationSample奇怪嗎?
- 2. 有人可以解釋以下奇怪的函數聲明嗎?
- 3. Navbar很奇怪嗎?
- 4. 奇怪的Visual Studio行爲?這可以改變嗎?
- 5. 使用tee的奇怪:任何人都可以解釋嗎?
- 6. 有人可以解釋AlarmManeger的這種奇怪的行爲嗎?
- 7. 奇怪的JavaScript數組行爲。它可以修復嗎?
- 8. @ font-family,奇怪的字體名稱 - 我可以重命名嗎?
- 9. 有人可以解釋這種奇怪的toString行爲嗎?
- 10. 奇怪的PHP的oop行爲,有人可以解釋嗎?
- 11. JFrame打印很奇怪嗎?
- 12. List.rev表現奇怪嗎?
- 13. decltype(*&fun)很奇怪嗎?
- 14. 奇怪的可可錯誤?
- 15. 可可子類奇怪
- 16. 奇怪的可轉位styping
- 17. JFrame以奇怪的背景
- 18. 混合「索引式」btree結構 - PostgreSQL可以做到這一點嗎?
- 19. 可可方法奇怪可用性
- 20. 有人可以解釋這個奇怪的Pygame導入約定嗎?
- 21. 任何人都可以解釋這個奇怪的蟒龜出現嗎?
- 22. 有人可以解釋這個奇怪的Python/Django導入行爲嗎?
- 23. 任何人都可以在jQuery中解釋這種奇怪的行爲嗎?
- 24. 任何人都可以向我解釋這個浮點奇怪嗎?
- 25. 有人可以在GWT中解釋這個奇怪的字符串事情嗎?
- 26. 任何人都可以解釋MariaDB的這種奇怪的行爲嗎?
- 27. Node.js套接字可以處理多個寫入消息嗎?奇怪的錯誤
- 28. 有人可以在Javascript中解釋這種奇怪的行爲嗎?
- 29. UIWebView中的奇怪WebKit錯誤 - 可以抓住這個錯誤嗎?
- 30. 奇怪的PHP字符串比較效果,這可以做得更好嗎?
甚麼_m_會出現什麼問題?您嘗試了哪些變化,是否遇到了一個問題? (有人會相信2-3樹和_ [2-4樹](https://www.cs.purdue.edu/homes/ayg/CS251/slides/chap13a.pdf)?) – greybeard