Complexidade Espacial

[joao_magalhaess 0]

Alguém me sabe dizer onde posso encontrar informação acerca de complexidade espacial de estruturas como árvores binárias, árvores AVL, árvore vermelhas-pretas, etc...

Obrigado desde já

[josevellozo 0]

Nao sei se será isto mas cá vai:

AVL

Time complexity

in big O notation

              Average Worst case

Space O(n)         O(n)

Search O(log n) O(log n)

Insert O(log n) O(log n)

Delete O(log n) O(log n)

http://en.wikipedia.org/wiki/AVL_tree

Binary Search Tree

Time complexity

in big O notation

              Average Worst case

Space O(n)       O(n)

Search O(log n) O(n)

Insert O(log n) O(n)

Delete O(log n) O(n)

http://en.wikipedia.org/wiki/Binary_search_tree