tanvir_cse's blog

need helpBinary search tree
By tanvir_cse, history, 8 years ago, In English

i want to use a bst for each node of segment tree, then i want to union left bst and right bst into root,,,but when i implement it , it works for root successfully that means it root bst contain all element that left and right bst have and contain the property of bst but the problem is it change the data in left and right child that means for next time if i want to use the left or right bst (not root) it's not the previous bst that means it change with the union operation.

im tried like that

t->bst= unite(t->l->bst ,t->r->bst);

i want to merge the left and right bst in root and also want to the and right bst remain same....

plz anyone explin me how can i do it... thanx in advance

  • Vote: I like it
  • -6
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
8 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it
  1. Persistent bst, treap for example(i dunno about other persistent bst-s, there might be some, but i am not sure).
  2. Idk if this fits ur problem, but sometimes following idea works:

U have LEFT, where all keys are <= K, RIGHT where all keys are > K. So u merge them in some root, remembering this K, and when u have to go down from this root u split it's bst in 2 by this K and assign left and right. So u kinda recalculate bsts ongoing.

Hope u've got the idea, if u didnt — feel free to ask, i'll try to explain better.

P.S. Englando is dead.

P.P.S. some grammatical changes

→ Reply