This paper proposes succinct data structures for dynamic ordinal trees. Succinct data structures are the ones whose size are asymptotically the same as the information-theoretic lower bounds of data, and the lower bound for n-node trees is In - (O)(log n) bits. Data structures of this paper efficiently support various queries and update operations (insertion/deletion of nodes) to ordinal trees. There are two types of data structures; the one is of size 2n + O(n/log n) bits and supports all operations in O(log n) time, and the other is of size 2n + O(n log log n/log n) bits and supports most of the queries in O(log n/log log n) time, and update operations in amortized O(log n) time.%動的な順序木に対する簡潔データ構造を提案する.簡潔データ構造とは，サイズが表現するデータの情報理論的下限に漸近的に一致するデータ構造であり，n節点の順序木に対する下限は2n-(O)(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）均し時間で実現する.
展开▼
