Syntax highlight example

Материал из Институт биоинформатики
Перейти к: навигация, поиск
  1. from random import randint
  2.  
  3.  
  4. class CartesianTree:
  5.     """
  6.     Example of Cartesian Tree implementation in Python
  7.     """
  8.     def __init__(self, x, y, priority, left=None, right=None):
  9.         self.x = x
  10.         self.y = y
  11.         self.priority = priority
  12.         self.left = left
  13.         self.right = right
  14.  
  15.     @staticmethod
  16.     def merge(left, right):
  17.         if left is None:
  18.             return right
  19.         if right is None:
  20.             return left
  21.         if left.priority > right.priority:
  22.             new_right = CartesianTree.merge(left.right, right)
  23.             return CartesianTree(left.x, left.y, left.priority, left.left, new_right)
  24.         else:
  25.             new_left = CartesianTree.merge(left, right.left)
  26.             return CartesianTree(right.x, right.y, right.priority, new_left, right.right)
  27.  
  28.     @staticmethod
  29.     def split(node, k):
  30.         if node is None:
  31.             return None, None
  32.         elif k > node.x:
  33.             t1, t2 = CartesianTree.split(node.right, k)
  34.             node.right = t1
  35.             return node, t2
  36.         else:
  37.             t1, t2 = CartesianTree.split(node.left, k)
  38.             node.left = t2
  39.             return t1, node
  40.  
  41.     @staticmethod
  42.     def add(node, x, y):
  43.         left, right = CartesianTree.split(node, x)
  44.         node = CartesianTree(x, y, randint(-100000, 100000))
  45.         return CartesianTree.merge(CartesianTree.merge(left, node), right)