1

そのため、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 ツリーを順番に走査する反復子を作成することです。祖先ノードを見つける目的は、祖先ノードが、その親ノードの正しい子であるリーフ ノードの順序どおりの後継ノードになることです。繰り返しますが、上記の例のように。

4

1 に答える 1

2

目的が単純に 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)

このリンクから取得したアルゴリズム。

于 2016-04-13T04:24:04.570 に答える