Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Fibonacci BSTs: a new balancing method for binary search trees

Autor
Roura, S.
Tipus d'activitat
Article en revista
Revista
Theoretical computer science
Data de publicació
2013-04-22
Volum
482
Pàgina inicial
48
Pàgina final
59
DOI
https://doi.org/10.1016/j.tcs.2012.11.027 Obrir en finestra nova
URL
http://www.sciencedirect.com/science/article/pii/S0304397512010572 Obrir en finestra nova
Resum
This paper presents a new method to balance binary search trees, which has the following properties. (i) The only information stored for the balance is the size of every subtree. (ii) Inserting or deleting an element can be done in the most traditional way: first, the element is recursively inserted (deleted) in (from) the appropriate subtree; afterwards, a single or double rotation takes place if necessary. (iii) Checking whether or not those rotations are required is computable in constant tim...
Paraules clau
Binary search trees, Constant time, Sub trees
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants