| Brief Description | ||
It is a dynamic data structure for fast search, insert, and delete. Also referred to in the literature as "Symmetric binary B-trees". The data structure was invented by Bayer [1]. It was named and studied in-depth by Guibas and Sedgewick [2]. Andersson [3] introduced a simpler-to-use variant, called as AA-trees by Weiss [4]. | ||
| Type of Data | ||
Values from a Totally Ordered Set | ||
| Operations and their time complexities | ||
| Operation | Time Complexity | Reference |
| SEARCH | Theta(log N) | [2] |
| INSERT | Theta(log N) | [2] |
| DELETE | Theta(log N) | [2] |
| References | ||
|
[1] Bayer, R.
Symmetric binary B-trees: Data Structure and maintenance algorithms. Acta Informatica, 1(3):173-189, 1972. [2] Guibas, L.J., Sedgewick, R. A dichromatic framework for balanced trees. Proc. of IEEE Symposium on Foundations of Computer Science, 8-21, 1978. [3] Andersson, A. Balanced Search Trees made simple. Proc. of Workshops on Algorithms and Data Structures, LNCS Vol. 709, 60-71, 1993. [4] Weiss, M.A. Algorithms, Data structures and Problem Solving with C++. Addison Wesley, 1996. | ||
| Last update | ||
| Jan 20, 2004. | ||
| Copyright | ||
| This DS entry is copyrighted by Giri Narasimhan. There are no restrictions on its use by non-profit institutions as long as its content is in no way modified and this statement is not removed. Usage by and for commercial entities requires a license agreement (Email to giri@cs.fiu.edu). | ||