作者:
easonc (eason)
2016-02-14 22:30:57有個小問題想請教各位
2-3 tree 的 top-down insertion 要怎麼做呢?
我在做台大電機丙資結的第10題看到的
我知道做top down 的insertion是由root開始往下走,
遇到full的node就split,然後繼續往下走,重複這個過程。
當order是偶數(node滿的時候會有奇數把key,如:2-3-4tree),
split可以把正中間的key往上放,
比中間的key大的key分在右邊的node,
比較小的key分在左邊的node;
可是當order是奇數(node滿的時候有偶數把key),就不能這樣做了
以這一題來說,他要我們用top down的方式依序insert{10,9,8,7,...}
等key到一個2-3 tree。
首先,依序insert 10,9,tree變成:1個node,稱這個node為N,
N裡面有9和10。
接著insert 8,發現N已經full了,所以應該split N,
這時候N應該怎麼split呢?覺得卡卡的,想問問大家,謝謝各位~