Re: [理工] 資結 2-3-4樹問題求解

[A4P8T6X9 (殘廢的名偵探)]

※ 引述《oklp1415 (天生我材)》之銘言：
: 問題是這樣的:
: http://ppt.cc/zS~j
: 想請問一下這題有辦法套公式求解嗎??
: 想詢問這題的詳解是怎麼的解答，感覺好難啊!!
: 已看過相關定義跟公式還是沒頭緒~"~

因為 2-3 tree 的外部點都在同一個高度 (這是定義)
又他只有 2 node(一個 key) 跟 3 node(兩個 key)
且根據他的 insert 可以推出，必定是下面先滿才會擠上去。

所以我們可以先全部都畫 2 node，

         O
        / \
       O   O
      / \ / \
     O  O O  O
    / \/ \/\/ \
   O  OO OOOO  O

恩，圖很難畫 ...

數一數會發現少一個 node，這時後因為只能從下面先擠，所以多的 node 100% 在底層，
所以底下那一層會有 9 個，這時後基本上就做完了，不過怕死可以在去分配 key 看看可
不可以，多畫一個的外部點的 父點必須是 2 key的，之後剩下的都補給外部點，所以 OK
以上。

參考看看 ~

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.24.32
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1407934307.A.4D2.html
推 oklp1415: 問一下，為何底層會是9各?符合二元樹的特性的話不應是8?
→ A4P8T6X9: 因為都只畫 2 node 的話，只有15個 node阿。
→ oklp1415: 那底下那一層會有 9 個  是指??
倒數第二層有一個是 3node的，所以最後一層會有三個 node，在一起。就會從8變成9拉
※ 編輯: A4P8T6X9 (140.112.24.32), 08/13/2014 21:46:19
→ oklp1415: 喔喔!!看成你畫的圖...就是那樣的題型...