Python高级算法与数据组织:操纵treap实现双索引之一

  • 首页
  • 大发体育手机版
  • 产品中心
  • 行业动态
  • 最新新闻
  • 当前位置:大发体育手机版 > 最新新闻 >

    Python高级算法与数据组织:操纵treap实现双索引之一

    人气:186 发表时间:2021-09-16

    \

    前线介绍的堆组织只能对数据进走片面排序,也就是它只能清新片面元素的排序,例如从根节点起程,沿着左孩子或右孩子前走,吾们能得知所遍历的元素肯定是递添(幼堆)或是递减(大堆)有关,但是吾们无法得知左子树与右子树两片面节点的排序有关。

    在许众行使场景下,吾们不光必要堆的特性,例如快速清新数据最大值或最幼值,同时还必要清新元素的排序新闻,所以本节吾们望望如何实现鱼和熊掌如何兼得。倘若吾们有一系列数据,它的元素由两片面构成,一片面对答商品的名称,其类型为字符串,一片面对答商品的货存数目,类型为整形,吾们既必要将商品按照其名称排序,同时吾们又必要快速查询现在货存最幼的商品,吾们如何设计响答的算法和数据组织来已足云云特性呢。

    举个例子,如下图:

    从上图望,它对答元素字符串是排序二叉树,所以根节点左子树对答元素的字符串都幼于根字符串,同时右子树对答的字符串都大于根节点字符串,同时每个元素还对答着响答商品的货存数目,吾们必要及时掌握现在货存最少的商品,云云才能在其耗尽之前敏捷补货。但是从上图能够望到,要保证字符串的排序性就得殉国对于商品数目的幼堆性质,例如上图中water对答的货存与wine对答的货存违背了幼堆的性质,现在题目是如何在保证字符串排序的情况下,确保数目同时能已足幼堆性质。

    最先吾们先定义一下数据组织:

    class Node:     def __init__(self, key: str, priority: float):         self._key = key         self._priority = priority         self._left: Node = None         self._right: Node = None         self._parent: Node = None      @property     def left(self):         return self._left      @property     def right(self):         return self._right      @property     def parent(self):         return self._parent      @left.setter     def left(self, node):         self._left = node         if node is not None:             node.parent = self      @right.setter     def right(self, node):         self._right = node         if node is not None:             node.parent = self      @parent.setter     def parent(self, node):         self._parent = node      def is_root(self) -> bool:         if self.parent is None:             return True         return False      def __repr__(self):         return "({}, {})".format(self._key, self._priority)      def __str__(self):         repr_str: str = ""         repr_str += repr(self)         if self.parent is not None:             repr_str += " parent: " + repr(self.parent)         else:             repr_str += " parent: None"          if self.left is not None:             repr_str += " left: " + repr(self.left)         else:             repr_str += " left: None"          if self.right is not None:             repr_str += " right: " + repr(self.right)         else:             repr_str += " right: None"          return repr_str  class Treap:     def  __init__(self):         self.root : Node = None 

    现在题目是,当上图所示的矛盾显眼前,吾们如何调整,使得字符串照样保持排序性质,同时货存数值能已足幼堆性质。吾们必要按照几栽情况采取迥异操作,最先望第一栽,如下图:

    从上图望到,一栽情况是父节点与左孩子在数值上违背了堆的性质,此时吾们实走一栽叫右旋转操作,其步骤是,1,Beer节点反时针旋转,替换其父节点;2,父节点Cabbage顺时针旋转,成为Beer的右孩子节点;3,正本Beer的右孩子节点转折为Cabbage的左孩子节点;完善后效果如下图所示:

    能够望到,此时字符串照样保持排序二叉树性质,同时数值对答的幼堆性质也得到了已足。吾们望望代码实现:

    class Treap:     def __init__(self):         self._root: Node = None      def right_rotate(self, x: Node):         if x is None or x.is_root() is True:             return          y = x.parent         if y.left != x:  # 必须是左孩子才能右旋转             return          p = y.parent         if p is not None:  # 实走右旋转             if p.left == y:                 p.left = x             else:                 p.right = x         else:             self._root = x          y.left = x.right         x.right = y 

    接下来吾们组织一些数据测试一下上面的实现是否准确:

    def setup_right_rotate():     flour: Node = Node("Flour", 10)     cabbage: Node = Node("Cabbage", 77)     beer: Node = Node("Beer", 76)     bacon: Node = Node("Bacon", 95)     butter: Node = Node("Butter", 86)      flour.parent = None     flour.left = cabbage     flour.right = None     cabbage.left = beer       beer.left = bacon     beer.right = butter      return flour, beer  def print_treap(n: Node):     if n is None:         return      print(n)     print_treap(n.left)     print_treap(n.right)  treap = Treap() root, x , cabbage = setup_right_rotate() print("---------before right rotate---------:") print_treap(root) treap.right_rotate(x) print("-------after right rotate-------") print_treap(root) 

    上面代码实走后输出内容如下:

    ---------before right rotate---------: (Flour, 10) parent: None left: (Cabbage, 77) right: None (Cabbage, 77) parent: (Flour, 10) left: (Beer, 76) right: (Eggs, 129) (Beer, 76) parent: (Cabbage, 77) left: (Bacon, 95) right: (Butter, 86) (Bacon, 95) parent: (Beer, 76) left: None right: None (Butter, 86) parent: (Beer, 76) left: None right: None (Eggs, 129) parent: (Cabbage, 77) left: None right: None -------after right rotate------- (Flour, 10) parent: None left: (Beer, 76) right: None (Beer, 76) parent: (Flour, 10) left: (Bacon, 95) right: (Cabbage, 77) (Bacon, 95) parent: (Beer, 76) left: None right: None (Cabbage, 77) parent: (Beer, 76) left: (Butter, 86) right: (Eggs, 129) (Butter, 86) parent: (Cabbage, 77) left: None right: None (Eggs, 129) parent: (Cabbage, 77) left: None right: None 

    对比右旋转前后输出的二叉树望,旋转后的二叉树打印新闻实在跟上面吾们旋转后对答的图像是相反的。接下来吾们实现左旋转,先把上图中cabbage节点对答的值改成75,云云它与父节点就违背了幼堆性质:

    吾们要做的是:1,把cabbage节点向“左”旋转到beer的位置;2,beer的父节点竖立为cabbage;3:beer的右孩子竖立为cabbage的左孩子;4,cabbage的左孩子变成beer;左旋转后二叉树答该成形如下:

    从上图望,左旋转后,字符串照样保持二叉树排序性,同时数值的排放也按照幼堆原则,吾们望响答的代码实现:

    class Treap:    ...      def left_rotate(self, x : Node):         if x is None or x.is_root() is True:             return          y = x.parent         if y.right is not x: # 只有右孩子才能左旋转             return          p = y.parent         if p is not None:             if p.left is y:                 p.left = x             else:                 p.right = x         else:             self._root = x          y.right = x.left         x.left = y 

    为了测试上面代码实现,吾们最先把cabbage的值修改,然后调用上面代码:

    cabbage._priority = 75 print("-------before left rotate--------") print_treap(root) treap.left_rotate(cabbage) print("-------after left rotate---------") print_treap(root) 

    代码运走后输出效果为:

    -------before left rotate-------- (Flour, 10) parent: None left: (Beer, 76) right: None (Beer, 76) parent: (Flour, 10) left: (Bacon, 95) right: (Cabbage, 75) (Bacon, 95) parent: (Beer, 76) left: None right: None (Cabbage, 75) parent: (Beer, 76) left: (Butter, 86) right: (Eggs, 129) (Butter, 86) parent: (Cabbage, 75) left: None right: None (Eggs, 129) parent: (Cabbage, 75) left: None right: None -------after left rotate--------- (Flour, 10) parent: None left: (Cabbage, 75) right: None (Cabbage, 75) parent: (Flour, 10) left: (Beer, 76) right: (Eggs, 129) (Beer, 76) parent: (Cabbage, 75) left: (Bacon, 95) right: (Butter, 86) (Bacon, 95) parent: (Beer, 76) left: None right: None (Butter, 86) parent: (Beer, 76) left: None right: None (Eggs, 129) parent: (Cabbage, 75) left: None right: None 

    输出效果的描述与上图左旋转后的效果是相反的。由于Treap相对于元素的key是排序二叉树,所以在给定一个字符串后,吾们很容易查询字符串是否在Treap中,其内心就是排序二叉树的搜索,其实现吾们一时无视。

    固然查询很浅易,但是插入节点则稍微麻烦,由于插入后,新节点与其父节点能够会违背幼堆性质,所以在完善插入后,吾们还需操纵上面实现的左旋转或右旋转来进走调整。

    【编辑保举】

    鸿蒙官方战略配相符共建——HarmonyOS技术社区 python Django轻量级saas管理平台实战演练 MongoDB数据库快速实战-测试工程师必备技能-幼强测试-课件已更新 关于python实现知识管理的一些思想 主机托管数据中央市场移向边缘 Flask操纵SQLite数据库

    返回顶部