Treap――堆和二叉树的完美结合，性价比极值的搜索树

大家好，今天和大家聊一个新的数据结构，叫做Treap。

Treap本质上也是一颗BST(平衡二叉搜索树)，和我们之前介绍的SBT是一样的。但是Treap维持平衡的方法和SBT不太一样，有些许区别，相比来说呢，Treap的原理还要再简单一些，所以之前在竞赛当中不允许使用STL的时候，我们通常都会手写一棵Treap来代替。

Treap的基本原理

既然是平衡二叉搜索树，关键点就在于平衡，那么重点自然是如何维护树的平衡。

在Treap当中，维护平衡非常简单，只有一句话，就是通过维护小顶堆的形式来维持树的平衡。Treap也正是因此得名，因为它是Tree和Heap的结合体。

我们来看下Treap当中节点的结构：

class TreapNode(TreeNode):     """     TreeNode: The node class of treap tree.     Paramters:          key: The key of node, can be treated as the key of dictionary         value: The value of node, can be treated as the value of dictionary         priority: The priority of node, specially for treap structure, describe the priority of the node in the treap.          lchild: The left child of node         rchild: The right child of node         father: The parent of node, incase that we need to remove or rotate the node in the treap, so we need father parameter to mark the address of the parent     """     def __init__(self, key=None, value=None, lchild=None, rchild=None, father=None, priority=None):         super().__init__(key, value, lchild, rchild, father)         self._priority = priority      @property     def priority(self):         return self._priority      @priority.setter     def priority(self, priority):         self._priority = priority      def __str__(self):         return 'key={}, value={}'.format(self.key, self.value) 

这里的TreeNode是我抽象出来的树结构通用的Node，当中包含key、value、lchild、rchild和father。TreapNode其实就是在此基础上增加了一个priority属性。

之所以要增加这个priority属性是为了维护它堆的性质，通过维护这个堆的性质来保持树的平衡。具体的操作方法，请往下看。

Treap的增删改查

插入

首先来讲Treap的插入元素的操作，其实插入元素的操作非常简单，就是普通BST插入元素的操作。唯一的问题是如何维持树的平衡。

我们前文说了，我们是通过维持堆的性质来保持平衡的，那么自然又会有一个新的问题。为什么维持堆的性质可以保证平衡呢?

答案很简单，因为我们在插入的时候，需要对每一个插入的Node随机附上一个priority。堆就是用来维护这个priority的，保证树根一定拥有最小的priority。正是由于这个priority是随机的，我们可以保证整棵树蜕化成线性的概率降到无穷低。

当我们插入元素之后发现破坏了堆的性质，那么我们需要通过旋转操作来维护。举个简单的例子，在下图当中，如果B节点的priority比D要小，为了保证堆的性质，需要将B和D进行互换。由于直接互换会破坏BST的性质，所以我们采取旋转的操作。

旋转之后我们发现B和D互换了位置，并且旋转之后的A和E的priority都是大于D的，所以旋转之后我们整棵树依然维持了性质。

右旋的情况也是一样的，其实我们观察一下会发现，要交换左孩子和父亲需要右旋，如果是要交换右孩子和父亲，则需要左旋。

整个插入的操作其实就是基础的BST插入过程，加上旋转的判断。

def _insert(self, node, father, new_node, left_or_right='left'):       """       Inside implement of insert node.       Implement in recursion.       Since the parameter passed in Python is reference, so when we add node, we need to assign the node to its father, otherwise the reference will lose outside the function.       When we add node, we need to compare its key with its father's key to make sure it's the lchild or rchild of its father.       """       if node is None:           if new_node.key < father.key:               father.lchild = new_node           else:               father.rchild = new_node           new_node.father = father           return       if new_node.key < node.key:           self._insert(node.lchild, node, new_node, 'left')           # maintain           if node.lchild.priority < node.priority:               self.rotate_right(node, father, left_or_right)       else:           self._insert(node.rchild, node, new_node, 'right')           # maintain           if node.rchild.priority < node.priority:               self.rotate_left(node, father, left_or_right) 

（编辑：核心网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!