treap not working expected when splitting on value that existed

[vbvg2008]

Repository commit

master

Python version (python --version)

any

Dependencies version (pip freeze)

any

Expected behavior

according to the docstring of treap's split function below, when we split a treap into two, the left treap should contain values less than split value, and the right should contain values greater or equal than split value.

def split(root: Node | None, value: int) -> tuple[Node | None, Node | None]:
    """
    We split current tree into 2 trees with value:
    Left tree contains all values less than split value.
    Right tree contains all values greater or equal, than split value
    """

Which means the expected return of following code should be:

root = interact_treap(None, "+1")
r1, r2 = split(root, 1)  # r1 should be None,  r2 should have value 1.

Actual behavior

However, the actual behavior of the same code is the opposite:

root = interact_treap(None, "+1")
r1, r2 = split(root, 1)  # r1 is 1, r2 is None when running the code

This can be fixed by either changing the docstring or by using <= instead of < in the if condition within split function.

[vbvg2008]

additional note: once you update the split function, erase function needs to change accordingly too, as it is currently relying on the wrong behavior of split

[utpalsavliya]

Solved the issue through the request #7899. Changed the docstring according to the standard implementation found on resources available online. More details in the pull request description. I suggest merging the request, or please provide feedback in case it is not merge-able. Also, please add hacktoberfest-accepted label, in case it is okay for merging :wink::smile: