I have the following code for splitting Treap, but I noticed the priorities of the nodes keep changing and I'm not sure how to ensure they remain unchanged. Kindly note priorities are randomly assigned, and we can assume they won't be equal. Once I figure this out, I need to implement the same for merging 2 Treaps.
def split(self, threshold: KT) -> List[Treap[KT, VT]]:
left_treap = TreapMap()
right_treap = TreapMap()
self._split_helper(self.root, threshold, left_treap, right_treap)
return [left_treap, right_treap]
def _split_helper(self, node: Optional[TreapNode], threshold: KT,
left_treap: TreapMap, right_treap: TreapMap) -> None:
if node is None:
return
if node.key < threshold:
left_treap.insert(node.key, node.value)
elif node.key >= threshold:
right_treap.insert(node.key, node.value)
self._split_helper(node.left_child, threshold, left_treap, right_treap)
self._split_helper(node.right_child, threshold, left_treap, right_treap)