PYTHON ДЕКАРТОВО ДЕРЕВО

Декартово дерево (Treap) -- это комбинированная структура данных, которая объединяет в себе две структуры: бинарное дерево поиска (binary search tree) и кучу (heap). Используется для быстрого выполнения операций вставки, удаления и поиска элементов.

Достоинством декартова дерева является возможность настройки приоритетов, что позволяет оптимизировать обычные операции бинарного дерева поиска.

Основными операциями над декартовым деревом являются: вставка, удаление, нахождение k-того по величине элемента, поиск элемента и объединение двух деревьев.

import randomclass TreapNode:    def __init__(self, key):        self.key = key        self.priority = random.randint(1, 100)        self.left = None        self.right = Noneclass Treap:    def __init__(self):        self.root = None    def split(self, treap, key):        if treap is None:            return None, None        if treap.key <= key:            left, right = self.split(treap.right, key)            treap.right = left            return treap, right        else:            left, right = self.split(treap.left, key)            treap.left = right            return left, treap    def merge(self, t1, t2):        if t1 is None:            return t2        if t2 is None:            return t1        if t1.priority > t2.priority:            t1.right = self.merge(t1.right, t2)            return t1        else:            t2.left = self.merge(t1, t2.left)            return t2    def insert(self, key):        left, right = self.split(self.root, key)        self.root = self.merge(self.merge(left, TreapNode(key)), right)    def erase(self, key):        l, r = self.split(self.root, key-1)        m, r = self.split(r, key)        self.root = self.merge(l, r)    def search(self, key):        cur = self.root        while cur is not None and cur.key != key:            if cur.key < key:                cur = cur.right            else:                cur = cur.left        return cur is not None