二分探索木の特性

一、順序性

二分探索木は、探索表(Lookup Table)の一種の実装とみなすことができます。

二分探索木を使用する目的は、keyを検索することで即座にvalueを得ることです。minimum、maximum、successor(後継)、predecessor(前駆)、floor(床)、ceil(天井)、rank(順位が何番目の要素か)、select(順位がn番目の要素は誰か)などは、すべて二分探索木の順序性の表現です。

二、限界(制限)

二分探索木は時間性能において限界(局限性)を持っています。

下図のように、要素ノードが同じでも、2種類の異なる二分探索木を構成でき、どちらも定義を満たしています:

二分探索木は連結リストに退化する可能性があります。それに伴い、二分探索木の探索操作はこの木の高さに関係しますが、このときの木の高さはこの木のノード数 n と等しくなります。同時に、二分探索木の対応するアルゴリズムはすべて O(n) レベルに退化します。

その他の拡張