0

AVL ツリーを実装しようとしていますが、各ノードの親を挿入して追跡する最良の方法がわかりません。これは教育的なものなので、「ブーストを使用する」ことを提案しないでください:)

これはコンパイルされますが、その正確性や最善の方法であるとは確信していません。具体的にはこれ

insert(someNumber,root,root);

また、リバランスしてツリーを上に移動するときに、高さの部分をやり直します。

このように挿入します

myTree.insert(someNumber);

これが方法です。ここで 2 番目のパラメーターを何にすべきかわかりません。私は NULL だと思っていたでしょうが、コンパイラはそれを好みません (関数定義が異なります)。

void Tree::insert(int someNumber){
    insert(someNumber,root,root);
}

ここに私のインサートがあります

void Tree::insert(int someNumber,Node*& subTreeRoot,Node*& parent){
    if(subTreeRoot==NULL)
    {
        subTreeRoot = new Node(someNumber,parent);
        if(subTreeRoot->myParent)   
    }
    else if (someNumber<subTreeRoot->myNumber)
    {
        if((subTreeRoot->right==NULL)||((subTreeRoot->left!=NULL)&&(subTreeRoot->right!=NULL)))
            subTreeRoot->height++;
        insert(someNumber,subTreeRoot->left,subTreeRoot);
    }
    else
    {
        if((subTreeRoot->left==NULL)||((subTreeRoot->left!=NULL)&&(subTreeRoot->right!=NULL)))
            subTreeRoot->height++;
        insert(someNumber,subTreeRoot->right,subTreeRoot);
    }
}

-

4

2 に答える 2

1

教育のためにこれを行っているので、いくつかのケースを手作業で作成し、それらを次の形式のテストにコーディングすることをお勧めします。

 Insert(6);
 Insert(11);
 // ...
 Insert(3);

 Node test = root;
 assert(root->height == 3);
 assert(root->value == 6);
 test = root->right;
 assert( ... );

数字は完全に構成されています。

この意志

  1. コードが機能しているかどうかについての感覚以上のものを提供します。(ヒント: コードが機能しているかどうかわからない場合は、おそらく機能していません)
  2. 何が問題なのかを理解するための場所を提供します。
  3. テストの習慣を身につけてください。最初にコードを書くよりも 2 倍のコード (テスト + コード) を書く方が速いという直感に反する人もいますが、試してみてください。加えて、より多くのコードを書く = より多くの練習。
于 2010-08-06T00:23:55.273 に答える
0

ツリーとノードの違いは何ですか? (ツリーはルート ノードの単なるプレース ホルダーであり、それ以上のものではありません。ノードには 2 つのサブツリーがあると言われることがあります。ツリーとノードも同じです。1 つのクラスで十分です。)

必要なときにいつでも高さを計算してみませんか? プログラミングと証明がはるかに簡単です。パフォーマンスに問題がある場合は、いつでも関数を変更してキャッシュされた値を返すことができます。

ノードはそれが親であることを認識すべきではありません (私の意見では)。したがって、挿入関数には親パラメーターが必要です。新しいノードを作成したら、親子の深さを比較して、回転を行う必要があるかどうかを確認します。ローテーションのプログラミングはトリッキーです: 試して、デバッグして、テストしてください!

Node::insert(int number,Node * parent)
{
  //code
  left=new node(number);
  if (parent->left->depth() > parent->right->depth()+1)
    parent->rotate_tree_or_something();
  //
}
于 2010-08-06T00:28:53.250 に答える