×

Updating almost complete trees or one level makes all the difference. (English) Zbl 0729.68013

Theoretical aspects of computer science, Proc. 7th Annu. Symp., STACS ’90, Rouen/Fr. 1990, Lect. Notes Comput. Sci. 415, 188-194 (1990).
Summary: [For the entire collection see Zbl 0728.00020.]
An almost complete (or 2-complete) tree is a binary search tree in which any two external nodes are no more than two levels apart. While complete binary search trees have an amortized update cost of \(\Theta\) (n), we demonstrate that almost complete binary search trees have an amortized update cost of \(0(\log^ 2n)\). Thus, they are an attractive alternative for those situations that require fast retrieval, that is, log n\(+0(1)\) comparisons, and have few updates.

MSC:

68P10 Searching and sorting
68P05 Data structures

Citations:

Zbl 0728.00020