使用 Python 实现 Treap 的搜索、插入和删除

2024年8月29日 | 阅读 7 分钟

引言

Treap 是一种特殊且有效的数据结构，它结合了最大堆 (Max Heap) 和二叉搜索树 (BST) 的特性。Treap 中的每个节点都维护两个关键值：一个用于保证堆的性质，另一个用于维护顺序，类似于 BST。堆的性质通常是通过在插入时为节点随机分配优先级来定义的。这种组合使得 Treap 能够以预期的 O(log N) 时间复杂度进行快速的搜索、插入和删除操作。

Treap 的关键组成部分

键 (Key)： 这是每个节点的主要值或数据。它遵循 BST 的顺序属性。
优先级 (Priority)： 在插入时随机分配优先级值，以维护最大堆的性质。它确保具有更高优先级的节点位于树的顶部。

Treap 中的操作

插入 (Insertion)： 新节点会根据其键插入到 Treap 的正确位置，并通过优先级来维护最大堆的性质。
删除 (Deletion)： 要从树中删除节点，需要找到具有目标键的节点，然后重构树，以保留 BST 和最大堆的属性。
搜索 (Search)： 在 Treap 中搜索特定键时，会遵循 BST 的属性，从而使搜索操作高效。

1. 插入操作

在 Treap 中插入一个具有键和随机优先级的新节点，同时保留二叉搜索树 (BST) 和最大堆 (max-heap) 的属性。

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. 删除操作

Treap 中的删除步骤包括：找到包含目标键的节点，删除该节点，然后重新组织树以保留二叉搜索树 (BST) 和最大堆的属性。

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.

优点

Treap 默认保持平衡结构，确保搜索、插入和删除等操作的平均时间复杂度为 O(log N)。这对于动态数据集非常有用。
Treap 的平衡系统允许进行高效的插入和删除操作。与某些自平衡 BSTs 不同，Treap 通过随机优先级降低了最坏情况下的效率下降的可能性。
Treap 具有适应性，并在各个行业中使用。任务调度、随机算法和优先级队列是需要高效查询和优先级的应用的例子。
与其他一些平衡树结构相比，Treap 的实现相对简单。简洁的代码即可实现插入、删除和搜索等基本操作。

缺点

其随机优先级的质量显著影响 Treap 的有效性。在实践中，生成真正随机的优先级可能很困难，而糟糕的优先级可能影响树的平衡和效率。
Treap 由于依赖随机优先级而具有非确定性的行为。生成的优先级可能导致同一组键产生不同的树结构。这可能会使分析和调试变得更加困难。
在多线程环境中，可能难以保证操作的正确执行。对 Treap 的并发访问需要同步机制，从而使实现复杂化。
Treap 在许多情况下都很有效，但并非总是最佳选择。在特定情况下，AVL 或红黑树等其他数据结构可能提供更可靠和一致的性能。

时间和空间复杂度

Treap 为高效的插入、删除和搜索操作提供了 O(log N) 的时间复杂度。如果节点存储键-优先级对，则最坏情况下的空间复杂度为 O(N)，其中 N 是 Treap 中的键的数量。Treap 结合了性能和简洁性，非常适合需要优先级和有序存储的各种应用。

结论

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

Treap 由于其适应性，在许多不同的领域都有应用。它们在需要优先级和排序的场景中表现出色。例如，它们被用于优先级队列、随机算法和任务调度。对于那些寻找有效方法来管理优先排序数据并对其进行排序的程序员来说，它们也是一种选择，因为它们的实现相对简单。此外，在多线程环境中，很难保证操作的准确性。并发访问需要同步机制，这可能会使实现更加复杂。Treap 提供了平衡且适应性强的数据结构，并且操作效率高，但其使用需要根据每个应用程序的独特需求和特征进行仔细评估。在某些情况下，AVL 或红黑树等其他数据结构可能提供更一致和可预测的性能。

下一个主题implicitly_wait Driver 方法 - Selenium Python

使用 Python 实现 Treap 的搜索、插入和删除

引言

Treap 的关键组成部分

Treap 中的操作

1. 插入操作

2. 删除操作

3. 搜索操作

优点

缺点

时间和空间复杂度

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Python 问题

使用 Python 实现 Treap 的搜索、插入和删除

引言

Treap 的关键组成部分

Treap 中的操作

1. 插入操作

2. 删除操作

3. 搜索操作

优点

缺点

时间和空间复杂度

结论

相关帖子

Python 位运算符

Python Contextvars 模块

Python LastPass 模块

Python 中的字符串镜像字符

Python YAML 解析器

Python 开发者的高级 Python 概念

Python 中的括号平衡

Python 数组 vs. 列表

使用 Python 进行有限自动机算法模式搜索

CPython 是什么

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器