how can i return the median of a threaded binary search tree in constant time?

Question

I'm having a trouble with understanding how to implement and find the median of a threaded binary search tree in constant time.

The tree consists of a worker's id and name.

The given details are given:

In a binary search tree with n nodes, There are n+1 left and right pointers with the value NIL. For every node z in the tree we make the following change: If left[z]=NIL then left[z] obtains the value of tree-predecessor(z); And if right[z]=NIL then right[z] obtains the value of tree-successor(z).

Basically, from what I understand it's a doubly threaded binary search tree.

I am not sure how to return the median in a constant time.

What I know is that if we want to return the median in O(n) in a regular binary search tree, then it is obtained using Morris in-order traversal and then easily calculated if the number of nodes is even or odd.

However, how can it be calculated in constant time?

I already done the traversal with in-order,post-order,pre-order using a linear time with the number of elements in it.

Please help me, stuck on it for quite a while.

thank you very much

Answer 1

If by 'threaded binary search tree' you mean 'balanced binary tree'.

Easy. Return the root!

https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

The key feature of a balanced binary tree is that you are balancing nodes on the left and right as you modify the tree, keeping half of them on the left, and half on the right ;-) The median then is always at the root of the tree. So trick question ;-)

If you mean something else - you likely cannot find it in constant time. If you have to wander through the tree to almost any degree hunting around, that will almost have to depend on how big the tree is, and so not be constant.

Answer 2

For a size-balanced binary search tree of odd size, the root node represents the median.

For a size-balanced binary search tree of even size, the approach depends on your definition of the median. In case you simply average the two central values, you would have average the root value with its neighboring value on the larger subtree's side. In a linked tree finding that neighbor is a constant-time operation.

The difficult part here is keeping the tree size-balanced (weight-balanced). Most tree balancing algorithms balance the height instead, which is uninteresting here. Weight-balancing algorithms typically keep the left and right weights within some factor of each other, but here we want the weight difference to be zero or one.

AFAIK this is easy to do given O(n) insertions (e.g. by rebuilding the tree after each insertion).

Answer 3

for sake of simplicity, we'll assume that the median is the value at the ceil(n/2) index of the inorder traversal(1-indexed). at the head of the tree add a pointer to the median node & count of the number of nodes (n). maintenance: on every node insertion/deletion hold the old n in a temp variable, increment n by one and then check if the median, ( ceil(n/2)), index value has changed. if it grew by 1 set the median's successor as the median if it got smaller by 1 set the median's predecessor as the median This way you can simply return the median in constant time.