バイナリツリーは、バイナリツリーがソート順でデータを保持するため、メモリが制限されているハッシュテーブルよりも優先される必要があります。バイナリツリーであるというトレードオフは、ハッシュテーブルの場合に一定の時間挿入およびルックアップと比較して、O（ログn）検索および挿入を有する。バイナリツリーを使用したディクショナリの実装
私は私のアドレス帳（いつもソートされた）を実装するためにバイナリツリーを選択するのかしらと思っていましたが、キーの外観はどうでしょうか？名前と番号のペアに値するでしょうか？
BTree！=バイナリツリー。私はあなたが後者を意味すると仮定します。
あなたのアドレス帳がどのように見えるかは、実行する検索によって異なります。あなたの名前が与えられた人の住所を見つけるには、キーは名前で、アドレス/番号は値です。
アドレスから名前にルックアップしたい場合は、キーと値を逆にするだけです。双方向ルックアップが必要な場合は、アドレス帳ごとに2つのツリーが必要です。
バイナリツリーベースのディクショナリは、<map>のヘッダーにstd::mapというC++標準ライブラリで提供されています。プログラミング演習が必要な場合を除き、あなた自身をロールバックしないでください。 std::mapは、パフォーマンスと機能面で非常に苦戦しています。
私はキーが単なる名前だと思います。数値が値です。あなたは名前で検索します、そうですか？
また、パフォーマンスを向上させたい場合は、AVLツリーを使用してください。そのようにして、すべてのサブツリーは同じ（±1）深さを持ちます。
アドレス帳のようなものを考えると、データの使用方法（ルックアップ）は、データがどのように（物理的にメモリに）格納されるかを優先する必要があります。
名前がキーの場合、その名前はどのように保存されますか？ 「First Last」、「Last、First」などがあります。これは検索の実行方法に影響します。番号で検索したい場合（電話番号の入力を開始し、連絡先をポップアップにするなど）
アドレス帳をどのように使用するかについて考えてみることをお勧めします。要求を完全に理解する前に間違って実装に縛られることはありません。
これを考えると、私はboost::multi_indexを見るでしょう。このライブラリは、データを一度格納し、それに対して任意の数の "検索キー"を提供するために使用できる一連のデータ構造を提供します。このような場合は非常に便利です。
辞書型のtrieとデータ構造のバイナリツリーは良い選択です。それはまた、名前のクリティカルビットツリー、基数ツリーまたはパトリシアツリーとも呼ばれます。ハッシュキーを使った単純なトライは、ハットを使って左と右を定義するカートトライですが、データ構造はまだバイナリツリーです。 3つのトライがありますが、データ構造はBツリーから来ており、3つのリーフがあります。
BTree！=バイナリツリー –
ソートされたデータは、限られたメモリ状況にどのように関連していますか？さらに、あなたのAddressbookが常にソートされていれば、ソートされていないコンテナを使うのはどうでしょう？あなたは本当にあなたの要件とあなたの問題の両方を定義する必要があります（あなたの質問に関して：私たちはどのように知っていますか？特定の番号の名前または特定の名前の番号を参照したいですか？） – Grizzly
スマートフォン以外の携帯電話と同じように名前を入力して番号を取得します。 – keeda