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) 

（编辑：湖南网）

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