在2-3樹中找到正確的祖先

因此，我在2-3樹中找到正確的祖先時遇到了問題。在任意高度的2-3樹中，有幾個案例需要尋找。在2-3樹中找到正確的祖先

我的節點設計如下：

template<typename DataType> 
struct node{ 
    Node<DataType> *child1; //left-child 
    Node<DataType> *child2; //middle-child (3-node only) 
    Node<DataType> *child3; //right-child 
    Node<DataType> *extraChild; //for splitting purposes 

    Node<DataType> *parent; 

    DataType key1; //key1 <= key2 
    DataType key2; //key2 <= extraKey (only when node needs to be split) 
    DataType extraKey; //for splitting purposes 
};

是否有一個算法或類似找到合適的祖先節點的東西嗎？例如，假設我們正在尋找H的祖先（提供的樹的底部），從視覺的角度來看，顯然H的祖先是樹的根部H。但是這需要跳出4個父鏈接。樹可以是任意大小，這是問題。

我最終的目標是創建一個遍歷2-3樹的迭代器。尋找祖先節點的目的是，祖先節點將作爲其父節點的右側子節點的葉節點的有序後繼者。再如上面提供的例子。

來源

2016-04-13 Saggitori

如果目標只是按順序遍歷2-3樹，那麼您只需編寫一個從根開始的遞歸函數。

的算法如下：

traverse(Node n) 

    if n.left != null 
     traverse(n.left) 

    if n.middle != null 
     visit(n.key1) 
     traverse(n.middle) 
     visit(n.key2) 
    else 
     visit(n.key1) 

    if n.right != null 
     traverse(n.right)

Algorithm taken from this link.

來源

2016-04-13 04:24:04

不幸的是這並沒有回答我的問題。我並非試圖實現「一次性」順序遍歷。我正在創建一個在樹中的任何位置保存狀態的對象。從那個地方，對象將能夠移動到後繼者，並且如果沒有更多後繼者返回結束迭代器的過去，則返回null。 – Saggitori

然後你原來的文章中陳述的目標是不正確的：你不是試圖創建一個迭代器，它執行2-3樹的按順序遍歷。如果您特別需要查找滿足某些約束條件的最新父代（例如具有等效密鑰），那麼最有效的方法是隻通過您已創建的父鏈接進行爬網，它將隨着樹的大小以對數時間進行縮放。 –

確切地說，你提供的算法沒有考慮到。例如，如果我的迭代器在所提供的例子中是葉N，那麼後繼者應該是內部節點O.說「爬回父節點」是好的，它可以工作，但我需要能夠從範圍節點N.節點N不知道它是哪個孩子，或者它來自哪個分支。所有它知道的是它的父母是內部節點M.我需要通過回顧父母和比較值來停止O，但是重複這會變得危險。 – Saggitori

在2-3樹中找到正確的祖先

回答

相關問題