動的簡潔順序木

摘要

動的な順序木に対する簡潔データ構造を提案する．簡潔データ構造とは，サイズが表現するデータの情報理論的下限に漸近的に一致するデータ構造であり，n節点の順序木に対する下限は2n-θ（log n）ビットである．本論文のデータ構造は順序木に対する様々な問合せと，木構造の変更（節点の追加·削除）を効率よく実現する．2つのデータ構造があり，1つはサイズが2n+O（n/log n)ビットで全ての演算をO（log n)時間で行える．もう1つはサイズが2n+O（n log log n/log n）ビットで多くの演算をO（log n/log log n）時間，木構造の変更をO(log n）均し時間で実現する．