treap Algorithm

The treap algorithm is an ingenious data structure that combines two key elements - binary search trees and heaps - to create a highly efficient and balanced structure, which is also known as a Cartesian tree. It's called a treap because it combines the features of a tree and a heap. The treap algorithm is primarily used for maintaining a dynamic set of ordered elements, enabling efficient search, insertion, and deletion operations. The algorithm's power comes from its ability to maintain a balanced tree as elements are inserted or deleted, ensuring that the height of the tree is proportional to the number of elements stored. The treap data structure consists of nodes containing two values: a key and a priority. The key represents the element value, while the priority is a random number assigned to the node. The algorithm ensures that the tree remains a binary search tree according to the keys and a heap according to the priorities. The binary search tree property guarantees that all keys in a node's left subtree are smaller than the node's key, and all keys in the right subtree are larger. Meanwhile, the heap property ensures that a node's priority is higher than the priorities of its children. When performing insertion or deletion operations, the treap may need to be restructured using rotations to maintain both properties. As a result, the treap algorithm provides excellent average-case performance, with most operations having a time complexity of O(log n), where n is the number of nodes in the treap.
# flake8: noqa

from random import random
from typing import Tuple


class Node:
    """
    Treap's node
    Treap is a binary tree by value and heap by priority
    """

    def __init__(self, value: int = None):
        self.value = value
        self.prior = random()
        self.left = None
        self.right = None

    def __repr__(self):
        from pprint import pformat

        if self.left is None and self.right is None:
            return f"'{self.value}: {self.prior:.5}'"
        else:
            return pformat(
                {f"{self.value}: {self.prior:.5}": (self.left, self.right)}, indent=1
            )

    def __str__(self):
        value = str(self.value) + " "
        left = str(self.left or "")
        right = str(self.right or "")
        return value + left + right


def split(root: Node, value: int) -> Tuple[Node, Node]:
    """
    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
    """
    if root is None:  # None tree is split into 2 Nones
        return (None, None)
    elif root.value is None:
        return (None, None)
    else:
        if value < root.value:
            """
            Right tree's root will be current node.
            Now we split(with the same value) current node's left son
            Left tree: left part of that split
            Right tree's left son: right part of that split
            """
            left, root.left = split(root.left, value)
            return (left, root)
        else:
            """
            Just symmetric to previous case
            """
            root.right, right = split(root.right, value)
            return (root, right)


def merge(left: Node, right: Node) -> Node:
    """
    We merge 2 trees into one.
    Note: all left tree's values must be less than all right tree's
    """
    if (not left) or (not right):  # If one node is None, return the other
        return left or right
    elif left.prior < right.prior:
        """
        Left will be root because it has more priority
        Now we need to merge left's right son and right tree
        """
        left.right = merge(left.right, right)
        return left
    else:
        """
        Symmetric as well
        """
        right.left = merge(left, right.left)
        return right


def insert(root: Node, value: int) -> Node:
    """
    Insert element

    Split current tree with a value into left, right,
    Insert new node into the middle
    Merge left, node, right into root
    """
    node = Node(value)
    left, right = split(root, value)
    return merge(merge(left, node), right)


def erase(root: Node, value: int) -> Node:
    """
    Erase element

    Split all nodes with values less into left,
    Split all nodes with values greater into right.
    Merge left, right
    """
    left, right = split(root, value - 1)
    _, right = split(right, value)
    return merge(left, right)


def inorder(root: Node):
    """
    Just recursive print of a tree
    """
    if not root:  # None
        return
    else:
        inorder(root.left)
        print(root.value, end=" ")
        inorder(root.right)


def interactTreap(root, args):
    """
    Commands:
    + value to add value into treap
    - value to erase all nodes with value

        >>> root = interactTreap(None, "+1")
        >>> inorder(root)
        1 
        >>> root = interactTreap(root, "+3 +5 +17 +19 +2 +16 +4 +0")
        >>> inorder(root)
        0 1 2 3 4 5 16 17 19 
        >>> root = interactTreap(root, "+4 +4 +4")
        >>> inorder(root)
        0 1 2 3 4 4 4 4 5 16 17 19 
        >>> root = interactTreap(root, "-0")
        >>> inorder(root)
        1 2 3 4 4 4 4 5 16 17 19 
        >>> root = interactTreap(root, "-4")
        >>> inorder(root)
        1 2 3 5 16 17 19 
        >>> root = interactTreap(root, "=0")
        Unknown command
    """
    for arg in args.split():
        if arg[0] == "+":
            root = insert(root, int(arg[1:]))

        elif arg[0] == "-":
            root = erase(root, int(arg[1:]))

        else:
            print("Unknown command")

    return root


def main():
    """After each command, program prints treap"""
    root = None
    print(
        "enter numbers to create a tree, + value to add value into treap, "
        "- value to erase all nodes with value. 'q' to quit. "
    )

    args = input()
    while args != "q":
        root = interactTreap(root, args)
        print(root)
        args = input()

    print("good by!")


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    main()

LANGUAGE:

DARK MODE: