CODEWITHSUNDEEP
algorithmbinary-search-tree
VibhorGupta
VibhorGupta

Reputation: 11

Update in O(log n) time

Is there any way to update the nodes of the balanced binary search tree in O(log n) time?

Suppose there is a balanced tree such that each node have an indexed object associated with it. So node 1 will point to object 1, node 2 will point to object 2 and so on.

If there are 100 nodes in the tree and if someone decided to delete the 2nd node then we have to update the remaining nodes such that node 3 will now be pointing to node 2, node 4 will now be pointing to node 3 and so on.

But this method will take O(n) time.

How can this be done in O(log n) time?

Upvotes: 0

Views: 197

Answers (2)

Michael S
Michael S

Reputation: 1865

That property sounds more like a linked list that a tree. But deletion in a binary search tree is O(h), the height of the tree. Since it's balanced this is O(log n).

Upvotes: 0

Bernhard Barker
Bernhard Barker

Reputation: 55619

If your tree is implemented such that each node has references to its children, i.e.:

class Node<T>
  Node leftChild
  Node rightChild
  T Data

(as opposed to an array or another way) all you have to do update these references (as outlined on Wikipedia for a Red-Black tree, for example).

This process will take O(log n) time, not O(n) time.

If you delete element 2 from the tree, node 2 will go along with it.

Upvotes: 1

Related Questions