0
$\begingroup$

How can I update values in Binary Search Tree without affecting its properties (all the nodes in the left subtree have values that are less than the value of the root node and all the nodes of the right subtree have values that are greater than the value of the root node).

I tried deleting and inserting the new Value, but It's an assignment and my teacher wants different solution with swaping nodes or rotations .

$\endgroup$
1
  • $\begingroup$ given any node in a BST, it can take values in range of its inorder predecessor to inorder successor while "maintaing its properties". $\endgroup$
    – Rinkesh P
    Commented Dec 21, 2022 at 8:00

2 Answers 2

1
$\begingroup$

I don't think that rotation and swapping of node value can fix the problem caused by an update. Consider the situation where the value of node $x$ decreases to $x'$. Let $y$ be the ancestor of $x$ closest to the root such that $y < x$. Assume that $x' < y < x$. Then before update, $x$ is in the right subtree of $y$ and after update, $x'$ must be on $y$'s left subtree but it is in the right subtree.

Rotation cannot fix that. Rotation is not meant to move a node to another subtree, but rather to change the parent-child relation of two nodes while ensuring that the symmetric order (BST property) is maintained if symmetric order holds prior to the rotation.

Swapping of node values is not going to fix this either, since node $x'$ should not be on $y$'s right subtree in the first place, so you cannot simply find another node that will take the place of $x'$ to fix the tree.

If your current solution is not acceptable, then I think the closest thing you can do is to detach $x'$, while ensuring that the subtree where it was removed is fixed and attaching it to a correct location in $y$'s subtree. Your delete and insert solution is a essentially a simulation of this detach-attach approach.

$\endgroup$
0
$\begingroup$

Deleting the value and inserting a new one is a valid way to update a value in a binary search tree. Its asymptotic running time is as good as any other solution.

$\endgroup$
3
  • $\begingroup$ I know but in the asignment we aren't allowed to to this , I need another solution . $\endgroup$
    – Raghad
    Commented Dec 20, 2022 at 19:33
  • $\begingroup$ @raghadhanoon, softwareengineering.meta.stackexchange.com/q/6166/34181 $\endgroup$
    – D.W.
    Commented Dec 20, 2022 at 19:36
  • $\begingroup$ I'll write the code by myself, I just need some hints $\endgroup$
    – Raghad
    Commented Dec 20, 2022 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.