這棵樹的名字是什麼？

我正在尋找這個簡單的樹的名字，這是一個非常簡單的二叉搜索樹的泛化。這棵樹的名字是什麼？

這是描述。樹的每個節點都有固定數量的最大密鑰MI和最小數量的密鑰數量爲1的密鑰。每個節點都有MI + 1個子節點的外部鏈接，或多或少像一棵B樹。子節點只包含父節點的兩個臨近鍵的間隔中的鍵，同樣也像B樹一樣。

不同之處在於插入和刪除是如何工作的。

插入：

我們從根開始。

如果我們正在檢查節點中有空間，因爲它沒有MI密鑰，所以它沒有滿，我們將我們的密鑰添加到正確的位置。

如果節點已滿，我們檢查孩子。如果這個範圍內沒有孩子，我們只用我們的鑰匙創建一個。等等。

刪除：

上刪除，如果我有一個節點實例「ACE」，我需要刪除「E」，但在「C」和「E」之間的間隔有一個孩子，我得到了孩子的最大元素，並將其替換爲「E」（我可能需要在這裏遞減，因爲移除元素可能需要將另一個元素從孩子移到父母）。它比這更復雜一點，但通常需要將子元素從子項移動到擁有已刪除鍵的節點。

我知道這是非常非正式的指定，但我無法找到似乎是一個二叉樹的普遍化的名稱。

來源

2011-01-28 antirez

你說一個節點可以有MI密鑰，但是你在插入時提到了「孩子」。請說明如何選擇兒童作爲其重要信息。 – marcog 2011-01-28 14:30:14

@margoc：我想我已經提到過，如果當前節點已滿，我們會轉到在由我們已有的兩個鍵定界的範圍內鏈接的子項。因此，如果MI是4，並且我已經在根節點「A C M Z」中，並且我要添加「E」，我創建了嘗試去A-C範圍內鏈接的子節點。如果沒有，我創建它。 – antirez 2011-01-28 16:00:35

我認爲你的算法是針對非自平衡的「多路樹」。看看here。

B樹因此是一個自平衡的變體。術語不完全一致。維基百科使用相同名稱的感覺是不同的（相當於多元），但我已經在足夠多的地方看到了上述解釋。

來源

2011-01-29 11:47:03 simeonz

也許這是k-ary tree。

來源

2011-01-28 12:45:47

它肯定是K-tree樹，但這是一個通用術語，我認爲，問題在於理解我描述的插入/刪除算法是否被視爲特殊樹。 – antirez 2011-01-28 16:01:20

這棵樹的名字是什麼？

回答

相關問題