木構造アルゴリズム

共通のプレフィックスを共有することで文字列を効率的に格納するツリーベースのデータ構造です。ルートからリーフへの各パスは単語またはキーを表します。オートコンプリート、スペルチェック、IPルーティングテーブル、辞書実装で優れており、キーの長さmに対してO(m)の操作を実現します。

木の中で2つの与えられたノードの祖先である最も深いノードを見つけます。計算生物学（種の進化）、ネットワークルーティング、バージョン管理システムでの応用を持つ木クエリの基本操作です。様々なアルゴリズムが異なる時間-空間のトレードオフを提供します。

1962年にAdelson-VelskyとLandisによって発明された最初の自己平衡二分探索木です。回転を通じて高さのバランスを維持し、O(log n)の操作を保証します。赤黒木よりも厳格なバランシングは、データベースやファイルシステムなどの検索が多いアプリケーションに理想的です。