AVL木の辞書

Question

これまでのところ、私はこれをやって行くことができるかを確認するために、攻撃の計画を描いてきたし、これは私が持っているものです。

bool isEmpty() const - 、空の場合はtrue、falseを返します

ない場合

int getSize() - すでに辞書

void insert (String word) -insert辞書への単語であれば存在しない、他の更新に格納されているどのように多くの単語を返します。

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

void printSorted() -

void remove (String word)は、私は私がダウンして何をしたいの概念を持っている、と私は理解してノード

の怠惰な削除を-implements辞書順（指定）で、ツリー内の単語を印刷しますAVLツリーの仕組みしかし、実際にコードを書くことになると、私は完全に立ち往生しています。

Answer 1

まず、ファイル内の単語数をカウントするための対応するプログラムとともに、単純なバイナリツリー（バランシングなし）を実装します。それがうまくいくので、テストするものがあります。まだバランスをとることについて心配しないでください。それは本当に難しい部分です。

ここでは単純なバイナリツリーの挿入機能（未テスト）です：

/* 
* 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 tree insertion diagramを参照することをお勧めします。これは、実装する必要がある4つのローテーションと必要な場所を示しています。左部分木と右のサブツリーの高さの差は、あなたが決定するにはどうすればよい1.

よりも大きいときにノードのバランス係数は、他の言葉で範囲—の外に出たとき

回転が必要ですノードのバランス係数？さて、次のいずれかが動作します：

1. は、左の子の高さから、右の子の高さを差し引くことにより、任意のノードのバランス係数をノード構造に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); 
} 

は、鉛筆、単純な代数、常識である。

こちらがお役に立てば幸いです。