Python中实现Treap中的查找、插入和删除

Treap 是一种特殊且有效的数据结构，结合了最大堆和二叉搜索树 (BST) 的品质。 Treap 中的每个节点都保留两个键值：一个用于保证堆属性，另一个用于维护顺序，就像 BST 一样。堆属性通常是通过在插入期间随机分配节点的优先级来定义的。这种组合提

关键组成部分

Key：这代表每个节点的主要值或数据。它与 BST 非常相似，遵循排序属性。
Priority优先级：当插入过程中随机分配优先级值时，将保留最大堆属性。它确保节点以更高的优先级占据树的顶部。

在 Treap 中的操作

插入：新节点会根据其键插入 Treap 的正确位置，同时优先保留最大堆属性。
删除：要从树中删除一个节点，需要找到具有目标键的节点，并重组树，以保留 BST 和最大堆属性。
搜索：在 Treap 中查找某个键时，会遵循 BST 属性，从而使搜索操作更有效。

1.插入操作
必须在保留二叉搜索树（BST）和最大堆（max-heap）属性的前提下，将一个带有键和随机选择的优先级的新节点插入到 Treap 中。

class Treap:  
    def _insert(self, node, key, priority):  
        if node is None:  
            return TreapNode(key, priority)  
  
        if key < node.key:  
            node.left = self._insert(node.left, key, priority)  
            if node.left.priority > node.priority:  
                node = self._rotate_right(node)  
        else:  
            node.right = self._insert(node.right, key, priority)  
            if node.right.priority > node.priority:  
                node = self._rotate_left(node)   
        return node  
    def insert(self, key):  
        priority = random.randint(1, 10**9)  
        self.root = self._insert(self.root, key, priority)

根据键值和优先级值，该递归函数会遍历 Treap，以确定新节点的理想位置。此外，它还会根据需要进行旋转，以保留最大堆属性。
要向 Treap 添加新键，请使用此公共方法。在生成一个随机优先级值后，运行 _insert 方法来添加新节点。

2.删除操作
找到包含目标键的节点、删除该节点、重组树以保留二进制搜索树（BST）和最大堆属性，是 Treap 中删除操作所涉及的步骤。

class Treap:  
    def _delete(self, node, key):  
        if node is None:  
            return node  
        if key < node.key:  
            node.left = self._delete(node.left, key)  
        elif key > node.key:  
            node.right = self._delete(node.right, key)  
        else:  
            if node.left is None:  
                return node.right  
            elif node.right is None:  
                return node.left  
            if node.left.priority > node.right.priority:  
                node = self._rotate_right(node)  
                node.right = self._delete(node.right, key)  
            else:  
                node = self._rotate_left(node)  
                node.left = self._delete(node.left, key)  
        return node  
    def delete(self, key):  
        self.root = self._delete(self.root, key)

_delete 是一个递归函数，用于在 Treap 中搜索包含目标键的节点，将其删除，并根据需要重新排列树以保留 Treap 的属性。
使用此公共方法可从 Treap 中删除包含特定键的节点。它修改 Treap 的根节点，并调用 _delete 方法。

3.搜索操作
在 Treap 中搜索时，需要根据二叉搜索树（BST）属性遍历树，以发现包含目标键的节点。

class Treap:  
    def _search(self, node, key):  
        if node is None or node.key == key:  
            return node  
        if key < node.key:  
            return self._search(node.left, key)  
        else:  
            return self._search(node.right, key)  
    def search(self, key):  
        return self._search(self.root, key)

递归函数 _search 使用二叉搜索树 (BST) 属性来浏览 Treap 并定位目标关键节点。如果找到节点，则返回该节点；否则，返回 None。
这就是公众在 Treap 中搜索键的方式。从 Treap 的根节点开始，运行 _search 函数，然后返回结果。

import random  
class TreapNode:  
    def __init__(self, key, priority):  
        self.key = key  
        self.priority = priority  
        self.left = None  
        self.right = None  
class Treap:  
    def __init__(self):  
        self.root = None  
    def _rotate_left(self, node):  
        new_root = node.right  
        node.right = new_root.left  
        new_root.left = node  
        return new_root  
    def _rotate_right(self, node):  
        new_root = node.left  
        node.left = new_root.right  
        new_root.right = node  
        return new_root  
  def _insert(self, node, key, priority):  
        if node is None:  
            return TreapNode(key, priority)  
        if key < node.key:  
            node.left = self._insert(node.left, key, priority)  
            if node.left.priority > node.priority:  
                node = self._rotate_right(node)  
        else:  
            node.right = self._insert(node.right, key, priority)  
            if node.right.priority > node.priority:  
                node = self._rotate_left(node)  
        return node  
    def insert(self, key):  
        priority = random.randint(1, 10**9)  
        self.root = self._insert(self.root, key, priority)  
    def _delete(self, node, key):  
        if node is None:  
            return node  
        if key < node.key:  
            node.left = self._delete(node.left, key)  
        elif key > node.key:  
            node.right = self._delete(node.right, key)  
        else:  
            if node.left is None:  
                return node.right  
            elif node.right is None:  
                return node.left  
  
            if node.left.priority > node.right.priority:  
                node = self._rotate_right(node)  
                node.right = self._delete(node.right, key)  
            else:  
                node = self._rotate_left(node)  
                node.left = self._delete(node.left, key)  
        return node  
    def delete(self, key):  
        self.root = self._delete(self.root, key)  
    def _search(self, node, key):  
        if node is None or node.key == key:  
            return node  
        if key < node.key:  
            return self._search(node.left, key)  
        else:  
            return self._search(node.right, key)  
    def search(self, key):  
        return self._search(self.root, key)  
    def inorder_traversal(self, node, result):  
        if node:  
            self.inorder_traversal(node.left, result)  
            result.append(node.key)  
            self.inorder_traversal(node.right, result)  
    def inorder(self):  
        result = []  
        self.inorder_traversal(self.root, result)  
        return result  
treap = Treap()  
treap.insert(5)  
treap.insert(2)  
treap.insert(8)  
treap.insert(1)  
treap.insert(4)  
treap.insert(7)  
treap.insert(9)  
print("Inorder traversal:", treap.inorder())    
treap.delete(5)  
print("Inorder traversal after deleting 5:", treap.inorder())    
result = treap.search(7)  
if result:  
    print("Key 7 found in the Treap.")  
else:  
    print("Key 7 not found in the Treap.")

输出：
Inorder traversal: [1, 2, 4, 5, 7, 8, 9]
Inorder traversal after deleting 5: [1, 2, 4, 7, 8, 9]
Key 7 found in the Treap.

优势

Treaps 默认保留了平衡结构，确保搜索、插入和删除等操作的平均时间复杂度为 O(log N)。这能很好地帮助动态数据集。
Treaps 的平衡系统允许有效的插入和删除操作。与某些自平衡 BST 相比，包含随机优先级可降低最坏情况下效率下降的可能性。
Treaps 适应性强，可用于各行各业。任务调度、随机算法和优先级队列都是需要探索和确定优先级的应用实例。
与其他某些平衡树结构相比，Treaps 的实现非常简单。简洁的代码就能实现插入、删除和搜索等基本操作。

缺点

随机优先级的标准会严重影响 Treaps 的有效性。在实践中，可能很难生成真正的随机优先级，而优先级确定不当会影响树的平衡和有效性。
由于依赖于随机优先级，Treaps 具有非确定性行为。生成的优先级可能会导致同一组键产生多种树形结构。因此，分析和调试可能会变得更加困难。
要保证在多线程环境下正确执行操作可能并不容易。对 Treap 的并发访问需要同步技术，从而使实现复杂化。
树状结构在许多情况下都很有效，但有时只是最佳选择。其他数据结构，如 AVL 或红黑树，在特定情况下可能会提供更可靠、更一致的性能。

时间和空间复杂性
对于高效的插入、删除和搜索操作，Treaps 的时间复杂度为 O（log N）。如果在节点中存储密钥优先级对，则最坏情况下的空间复杂度（N 为 Treap 中的密钥数）为 O(N)。由于 Treap 兼具性能和简单性，因此非常适合需要优先级和有序存储的各种应用。

结论
Treaps 是一种有趣且适应性强的数据结构，结合了 Max Heaps 和二叉搜索树 (BST) 的优点。它们具有一致的结构，非常适合不断添加和删除数据块的动态数据集。这种平衡确保了搜索、插入和删除操作的平均时间复杂度为 O（log N），这对于有效的数据处理至关重要。Treaps 在删除和插入方面的有效性是其最显著的优势之一。Treaps 依靠插入时分配给每个节点的随机优先级，这与某些自平衡 BST 不同，后者在最坏情况下可能会出现性能问题。通过自然平衡树，这种随机化降低了出现异常情况的可能性，确保了可靠的性能。

Treaps 因其适应性强，在许多不同领域都非常有用。它们在优先级和排序至关重要的情况下表现出色。例如，它们可用于优先队列、随机算法和工作调度。由于其实现相对简单，程序员可以利用它们来寻找管理优先排序数据的有效方法。此外，在多线程环境下，很难保证操作的准确性。并发访问需要同步技术，这可能会增加实现的难度。

Treaps 提供了一种平衡、适应性强、操作有效的数据结构，但在使用时需要根据每个应用的独特要求和特点进行仔细评估。在某些情况下，其他数据结构（如 AVL 或红黑树）可能会提供更稳定、更可预测的性能。