All geek questions in one place

Find algorithm in RBTREE in O (logn)

I need to find a data structure that I can do with the following actions:

  • Assembly (S, k) - O (nlogn)
  • Search (S, k) - O (logn)
  • Insert (S, k) - O (logn)
  • Delete (S, k) - O (logn)
  • Decrease-Upto (s, k, d) -O (logn) - this method should subtract d (d> 0) each node, which is equal to <= k

The obvious first choice was RedBlackTree.

However, I cannot come to a decision regarding Decrease-Upto in O (Logn). what happens if k is greater than the max key in the tree - in this case I have to update the whole tree.

Can anyone suggest another? maybe some tips?

+4
source share
1 answer

You can store additional value in each node of the tree, let’s call it delta. You add delta from node to the keys stored in your entire descendant to get the actual keys. Thus, in order to get the actual key value in a specific node, you sum all the delta from the root to this node and add this amount to the saved key.

To make Decrease-Upto , you simply change the deltas of the O (log n) nodes along one path from root.

You do not need to change the structure of the tree after this operation, because it does not change the order of the keys.

+4
source

Source: https://habr.com/ru/post/1300856/

More articles:


All Articles