5

これまで私は攻撃の計画を立てて、これをどのように実行できるかを確認してきました。これが私が持っているものです。

bool isEmpty() const-空の場合はtrueを返し、そうでない場合はfalseを返します

int getSize()-辞書に保存されている単語の数を返します

void insert (String word)-まだ存在しない場合は辞書に単語を挿入し、そうでない場合は更新します。

boolfind(String word, WordNode & x)-単語が存在する場合はtrueを返し、データをxに配置します。

void printSorted()-ツリー内の単語を辞書式順序で出力します（指定）

void remove (String word)-ノードの遅延削除を実装します

私は自分がやりたいことの概念を持っており、AVL木がどのように機能するかを理解しています。しかし、実際にコードを書くことになると、私は完全に行き詰まります。誰かが私が始めるのを手伝ってくれるでしょうか？

4

1 に答える 1

2

ファイル内の単語をカウントするための対応するプログラムとともに、単純なバイナリ ツリー (つまり、バランス調整なし) を実装することから始めます。それを機能させて、テストするものを用意します。まだバランスについて心配する必要はありません。それは本当に難しい部分です。

単純なバイナリ ツリーの挿入関数 (未テスト) は次のとおりです。

/*
 * Insert a new key into a binary tree, or find an existing one.
 *
 * Return the new or existing node whose key is equal to the one requested.
 * Update *node with the new (sub)tree root.
 */
Node *insert(Node **node, String key)
{
    if (*node == NULL) {
        *node = new Node(key);
        return *node;
    }

    if (key < (*node)->key)
        return insert(&(*node)->left, key);

    if (key > (*node)->key)
        return insert(&(*node)->right, key);

    return *node;
}

単純なバイナリ ツリーが機能してテストされたら、挿入関数を再実装して、AVL アルゴリズムの心臓部であるバランシングを実行します。

AVL ツリーの不変条件を知ることから始めます。

  • ノードのバランス係数 (左の子の高さと右の子の高さの差) は、-1、0、または +1 のいずれかです。
  • 順序トラバーサルは、辞書の順序を生成します。

ウィキペディアのAVL ツリー挿入図を参照することをお勧めします。これは、実装する必要がある 4 つのローテーションと、それらが必要な場所を示しています。

ノードのバランス係数が範囲外になった場合、つまり、左側のサブツリーと右側のサブツリーの高さの差が 1 より大きい場合、回転が必要です。

ノードのバランス係数をどのように決定しますか? さて、次のいずれかが機能します。

  1. Node 構造体にメンバーを追加heightし、左の子の高さから右の子の高さを引いて、特定のノードのバランス係数を決定します。
  2. balanceノード構造にメンバーを追加します。これを理解するのは少し難しいかもしれませんが、より単純なコードが得られます (私はそう思います)。
  3. 走査によって木の高さとバランスを計算します。これは非効率的であり、AVL の目的を無効にします。ただし、理解しやすく、バグが発生しにくいです。

3 番目のアプローチから始めることをお勧めします。これにより、バランシング コードをより早くテストできます。

「高さ」と「バランス係数」の意味を明確にするために、それらを計算する関数を次に示します。

int height(Node *node)
{
    if (node == NULL)
        return -1;
    return std::max(height(node->left), height(node->right)) + 1;
}

int balanceFactor(Node *node)
{
    assert(node != NULL);
    return height(node->right) - height(node->left);
}

高さまたはバランス係数を段階的に更新する方法を理解するには、紙、鉛筆、単純な代数、および常識が必要です。

これが役立つことを願っています！

于 2011-07-24T21:47:22.340 に答える