バイナリ検索ツリーを平衡に変更する

Question

辞書から何千もの単語を保存するために使用されるバイナリ検索データ構造を作成する方法を学びました。私が得ている問題は、データの追加と削除を数えるのに時間がかかることです。通常、カウントする100000語の場合、199263msまたは200秒。私は自己バランスをとることができるツリーを持つことが効率を改善し、操作をより速くすると言われました。

私の質問は、効率を上げるためにツリーの自動バランスをどのようにすることができるのですか。私は、ツリーの高さを短くするために、重複する単語を削除することによって、少し改善しました。

誰かが私にどのようにツリーを効率的にすることができ、どのように私がJavaでバランスの取れたツリーを実装できるかについて助言を与えることができます。バイナリツリーのバランスを取るために

Answer 1

、言葉がで読めば入れする必要はありません、これだけの拡張により、より良いため

BinaryTree balance(BinaryTree tree) 
{ 
    BinaryTree out = new BinaryTree(); 
    String[] values = tree.toArray(); //a sorted array 
    for(int i = Integer.highestOneBit(values.length); i > 0; i >>= 1) 
     for(int j = i; j <= values.length; j += i) 
      out.add(values[j - 1]); 
    return out; 
} 

に要素を追加し、新しいものを構築する方が簡単な場合がありツリーにとArrays.sort(Object[])は、あなたが実際にこのデータを使用しているもの（単にルックアップテーブル？）代わりにHashSet

を使用する方が速いかもしれによって

List<String> wordList = new LinkedList<String>(); 
BufferedReader reader = [...]; 
for(String line = reader.readLine(); line != null; line = reader.readLine()) 
    wordList.add(line); 
String[] words = wordList.toArray(new String[0]); 
Arrays.sort(words); 
BinaryTree tree = new BinaryTree(); 
for(int i = Integer.highestOneBit(words.length); i > 0; i >>= 1) 
    for(int j = i; j <= words.length; j += i) 
     out.add(words[j - 1]); 

速くなる可能性がある、すぐにソート

Set<String> dict = new HashSet<String>(); 
BufferedReader reader = [...]; 
for(String line = reader.readLine(); line != null; line = reader.readLine()) 
    dict.add(line); 

Answer 2

セルフバランスの赤/黒のツリーを調べる必要があります。ノードは、要素に加えて、色を格納し、それは黒/赤ツリーの特性を満たすようにツリーが変更されるたびに、ツリーをリバランス：

（Wikipedia :)

から

1. 各ノードは赤または黒のいずれかです。

2. 根は黒です。

3. すべての葉（NIL）は黒です。

4. ノードが赤の場合、その子は両方とも黒です。

5. 与えられたノードからその子孫NILノードまでのすべてのパス には、同じ数の黒ノードが含まれています。

は赤黒木を実装し始めるために、私はgithubの上 this example implementationを見て、赤、黒の木のthis explanationを読むことをお勧めします。