插入2-3樹

Question

我不知道我是否正確理解2-3樹的插入過程。說我有樹：

，我想插入值95到它，這會是正確的新樹？

Answer 1

是的，這是正確的。

插入95將放置3個孩子在最右葉（不允許）

 40 
    / \ 
    20  60, 80 
/\ / | \ 
10 30 50 70 90,95,100 <- not valid 

在葉的3個節點使95移動到父節點，但現在已經有在父3個節點：

 40 
    / \ 
    20  60,80,95 <- not valid 
/\ / | \ 
    10 30 50 70 90,100 

移動95向上使父節點分裂：

 40 
    / \ 
    20  80 
/\ / \ 
    10 30 60  95 
     /\ /\ 
     50 70 90 100 valid 

Answer 2

這是不正確。 2-3樹的高度是一致的，因此你將分裂父母而不是孩子。

Answer 3

我認爲你錯了。你違反2-3樹的一個事實：所有葉子都有相同的深度。 參考： http://pages.cs.wisc.edu/~vernon/cs367/notes/10.23TREE.html#operations

這裏是插入的痕跡我心目中：

請讓我知道這是不正確。