Декартовы деревья. Операции над Декартовыми деревьями.

Определение

Декартово дерево (также известное как treap) — это структура данных, которая объединяет свойства бинарного дерева поиска (BST) и кучи (heap). В Декартовом дереве каждому узлу присваивается два значения: ключ и приоритет.

• Узлы организованы по ключам как в BST (для любого узла, ключи в левом поддереве меньше, а в правом — больше).
• Узлы организованы по приоритетам как в куче (приоритеты потомков всегда меньше приоритета родительского узла).

Операции

1. Вставка нового элемента начинается как в обычном BST, а затем восстанавливается свойство кучи с помощью вращений (ротаций).
2. Удаление
   • Элемент сначала переводиться в лист с помощью ротаций, сохраняя свойство кучи.
   • Лист удаляется стандартным способом.
3. Разделение
   • Разделяет дерево на два поддерева, используя ключ разделения.
   • Операция проводится рекурсивно и сохраняет свойства BST и кучи.
4. Слияние
   • Сливает два дерева, сохраняя свойства BST и кучи.
   • Выбирает корень с большим приоритетом и рекурсивно сливает поддеревья.

class Node:  
    def __init__(self, key):  
        self.key = key  
        self.left = None  
        self.right = None  
  
class CartesianTree:  
    def __init__(self):  
        self.root = None  
	  
    def insert(self, key):  
        self.root = self._insert(self.root, key)  
	  
    def remove(self, key):  
        self.root = self._remove(self.root, key)  
	  
    def split(self, key):  
        left_tree, right_tree = self._split(self.root, key)  
        return left_tree, right_tree  
	  
    def merge(self, other):  
        self.root = self._merge(self.root, other.root)  
	  
    def _insert(self, node, key):  
        if node is None:  
            return Node(key)  
        if key < node.key:  
            node.left = self._insert(node.left, key)  
            if node.left and node.left.key > node.key:  
                node = self._rotate_right(node)  
        elif key > node.key:  
            node.right = self._insert(node.right, key)  
            if node.right and node.right.key < node.key:  
                node = self._rotate_left(node)  
        return node  
	  
    def _rotate_right(self, node):  
        new_root = node.left  
        node.left = new_root.right  
        new_root.right = node  
        return new_root  
	  
    def _rotate_left(self, node):  
        new_root = node.right  
        node.right = new_root.left  
        new_root.left = node  
        return new_root  
	  
    def _remove(self, node, key):  
        if node is None:  
            return node  
        if key < node.key:  
            node.left = self._remove(node.left, key)  
        elif key > node.key:  
            node.right = self._remove(node.right, key)  
        else:  
            if node.left is None:  
                return node.right  
            if node.right is None:  
                return node.left  
            temp = self._find_min(node.right)  
            node.key = temp.key  
            node.right = self._remove(node.right, temp.key)  
        return node  
	  
	  
    def _find_min(self, node):  
        current = node  
        while current.left is not None:  
            current = current.left  
        return current  
	  
    def _split(self, node, key):  
        if node is None:  
            return None, None  
        if key < node.key:  
            left_subtree, right_subtree = self._split(node.left, key)  
            node.left = right_subtree  
            return left_subtree, node  
        else:  
            left_subtree, right_subtree = self._split(node.right, key)  
            node.right = left_subtree  
            return node, right_subtree  
	  
    def _merge(self, left, right):  
        if left is None:  
            return right  
        if right is None:  
            return left  
        if left.key < right.key:  
            left.right = self._merge(left.right, right)  
            return left  
        else:  
            right.left = self._merge(left, right.left)  
            return right