data structures - What is the best way to implement Tree : LinkedList - Array -

i preparing exam, 1 of questions came across : best way implement tree, linkedlist or array.

most likely: - array uses 1 address - linkedlist use 2 addresses.

using linkedlist, can insert value need (we manage memory), likey use o(n) access element, while in array o(1).

how should answer question ? or should subjective.

for binary search tree, answer array ( @ least extendable array, vector<> aren't limited fixed size). i'll analysis of common operations, assuming tree balanced.

query

in bst, nodes need have pointers left , right children , common have parent pointers. in array implementation, "pointers" can integer indexes array ( mean array store node objects). looking parent , children of node constant since indexing array constant. o(1). linked list implementation need store reference position ancestors/children are, requiring o(n) pass through list desired references.

search

starting @ root, array[0], searching o(log n) operation. searching call/get info of children per node, o(1) amount of work, o(log n) times, o(log n) search in array.

a linked list require o(n) pass through data required left/right pointers, , can done in o(log n) steps, producing o(n log n) search in linked-lists.

insert

arrays similar search, except require additional o(1) constant time pointer assignments. o(log n) insert.

linked-lists similar search routine, except additional o(n) time adjusting pointers, o(n log n)

delete

arrays similar search, except take more single o(log n) factor delete, since have traverse tree, still o(log n).

linked lists have o(n log n) plus more o(n log n) traversing up. o(n log n) linked lists well.

conclusion

the answer should evident :) plus arrays you'll benefit of better caching linked-lists. plus, derivatives of binary search trees, such heaps (usually min-heaps/max-heaps) commonly represented arrays,

i hope helps :)