performance - Get median from AVL tree? -

performance - Get median from AVL tree? -

if have avl tree, what's best way median it? median defined element index ceil(n/2) (index starts 1) in sorted list.

so if list was

1 3 5 7 8

the median 5. if list was

1 3 5 7 8 10

the median 5.

if can augment tree, think it's best allow each node know size (number of nodes) of subtree, (i.e. 1 + left.size + right.size). using this, best way can think of makes median searching o(lg n) time because can traverse comparing indexes.

is there improve way?

augmenting avl tree store subtree sizes best approach here if need optimize on median queries. takes time o(log n), pretty fast.

if you'll computing median huge number of times, potentially utilize augmented tree , cache median value can read in time o(1). each time insertion or deletion, might need recompute median in time o(log n), slow things downwards bit not impact asymptotic costs.

another alternative thread doubly-linked list through nodes in tree can navigate node successor or predecessor in constant time. if that, can store pointer median element, , on insertion or deletion, move pointer left or right appropriate. if delete median itself, can move pointer left or right you'd like. doesn't require augmentation , might bit faster, adds 2 pointers each node.

hope helps!

performance algorithm data-structures median avl-tree