Shulou(Shulou.com)06/01 Report--

This article introduces you how to analyze the balanced binary search tree Treap, the content is very detailed, interested friends can refer to, hope to be helpful to you.

Today I'm going to talk to you about a new data structure called Treap.

Treap is essentially a BST (balanced binary search tree), the same as the SBT we introduced earlier. However, the method of maintaining balance in Treap is not quite the same as that in SBT, and there is a slight difference. In comparison, the principle of Treap is simpler, so when STL is not allowed in competitions, we usually write a Treap instead.

The basic principle of Treap

Since it is a balanced binary search tree, the key point is balance, so the focus is naturally on how to maintain the balance of the tree.

In Treap, maintaining balance is very simple, there is only one sentence, that is, to maintain the balance of the tree in the form of a small top heap. That's why Treap gets its name, because it's a combination of Tree and Heap.

Let's take a look at the structure of the nodes in 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)

The TreeNode here is a general Node of my abstract tree structure, including key, value, lchild, rchild, and father. TreapNode actually adds a priority attribute to this.

The reason for adding this priority attribute is to maintain the nature of the heap and to maintain the balance of the tree by maintaining the nature of the heap. For the specific method of operation, please read on.

Addition, deletion, modification and search of Treap

insert

First of all, let's talk about the operation of inserting elements in Treap. In fact, the operation of inserting elements is very simple, which is the operation of ordinary BST inserting elements. The only problem is how to keep the balance of the tree.

As we said earlier, we maintain the balance by maintaining the nature of the heap, so naturally there will be a new problem. Why does maintaining the nature of the heap ensure balance?

The answer is simple, because when we insert, we need to randomly attach a priority to each inserted Node. The heap is used to maintain this priority, ensuring that the tree root must have the smallest priority. Because the priority is random, we can ensure that the probability of the whole tree becoming linear is infinitely low.

When we insert an element and find that it destroys the nature of the heap, we need to maintain it through a rotation operation. To take a simple example, in the following figure, if the priority of node B is smaller than that of D, B and D need to be interchanged in order to ensure the nature of the heap. Since direct swapping destroys the nature of BST, we take a rotation operation.

After rotation, we find that B and D exchange positions, and the priority of An and E is greater than D after rotation, so we still maintain the properties of the whole tree after rotation.

The situation of right-handed rotation is the same. In fact, if we take a look, we will find that right-handed is needed to exchange left children and fathers, and left-handed if you want to exchange right-handed children and fathers.

The whole insertion operation is actually the basic BST insertion process, plus rotation judgment.

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) 前面的逻辑就是BST的插入，也就是和当前节点比大小，决定插入在左边还是右边。注意一下，这里我们在插入完成之后，增加了maintain的逻辑，其实也就是比较一下，刚刚进行的插入是否破坏了堆的性质。可能有些同学要问我了，这里为什么只maintain了一次?有可能插入的priority非常小，需要一直旋转到树根不是吗? 的确如此，但是不要忘了，我们这里的maintain逻辑并非只调用一次。随着整个递归的回溯，在树上的每一层它其实都会执行一次maintain逻辑。所以是可以保证从插入的地方一直维护到树根的。 查询 查询很简单，不用多说，就是BST的查询操作，没有任何变化。 def _query(self, node, key, backup=None): if node is None: return backup if key < node.key: return self._query(node.lchild, key, backup) elif key >

Node.key: return self._query (node.rchild, key, backup) return node def query (self, key, backup=None): "" Return the result of query a specific node, if not exists return None "" return self._query (self.root, key, backup)

Delete

The deletion operation is a little more troublesome, because priority maintenance is involved, but the logic is not difficult to understand, just keep in mind the nature of the heap.

First of all, there are two very simple cases, one is that the node to be deleted is the leaf node, which is easy to figure out, deleting it will not affect any other nodes, just delete it. The second case is the chain node, that is, it has only one child, so deleting it will not cause a change, just passing its child to its father, and the nature of the entire heap and BST will not be affected.

Apart from these two cases, there is no way to delete it directly, because it will inevitably affect the nature of the heap. A clever way to do this is to rotate the node to be deleted, rotate it into a leaf node or a chain node, and then delete it.

In the process, we need to compare the priorities of its two children to ensure that the nature of the heap is not compromised.

Def _ delete_node (self, node, father, key, child='left'): "" Implement function of delete node. Defined as a private function that only can be called inside. "" If node is None: return if key

< node.key: self._delete_node(node.lchild, node, key) elif key >

Node.key: self._delete_node (node.rchild, node, key, 'right') else: # if it is chain node The case of leaf nodes also includes if node.lchild is None: self.reset_child (father, node.rchild, child) elif node.rchild is None: self.reset_child (father, node.lchild) Child) else: # decide whether to turn left or right based on the priority of the two children < node.rchild.priority: node = self.rotate_right (node, father, child) self._delete_node (node.rchild, node, key) 'right') else: node = self.rotate_left (node, father, child) self._delete_node (node.lchild, node, key) def delete (self, key): "" Interface of delete method face outside. " Self._delete_node (self.root, None, key, 'left')

Modify

The operation of modification is also very simple. We can directly find the corresponding node and modify its value.

Rotation

Let's also paste the code for the rotation operation. In fact, the logic here is the same as the rotation operation described in SBT before, and the code is basically the same:

Def reset_child (self, node, child, left_or_right='left'): "" Reset the child of father, since in Python all the instances passed by reference, so we need to set the node as a child of its father node. "" If node is None: self.root = child self.root.father = None return if left_or_right = 'left': node.lchild = child else: node.rchild = child if child is not None: child.father = node def rotate_left (self, node, father, left_or_right): "Left rotate operation of Treap. Example: d /\ A B /\ E C After rotate: B /\ D C /\ An E "" Rchild = node.rchild node.rchild = rchild.lchild if rchild.lchild is not None: rchild.lchild.father = node rchild.lchild = node node.father = rchild self.reset_child (father Rchild, left_or_right) return rchild def rotate_right (self, node, father, left_or_right): "Right rotate operation of Treap. Example: d /\ A B /\ E C After rotate: a /\ E D /\ C B "" lchild = node.lchild node.lchild = lchild.rchild if lchild.rchild is not None: lchild.rchild.father = node lchild.rchild = node node.father = lchild self.reset_child (father Lchild, left_or_right) return lchild

The only thing to note here is that since all references are stored in Python, we have to overwrite the values in the parent node after the rotation operation to take effect. It is responsible for us to modify the reference to node, but the old address stored in father does not take effect.

On how to analyze and balance the binary search tree Treap to share here, I hope the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.