6

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

 7 months ago
source link: https://www.jdon.com/72448.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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 或红黑树）可能会提供更稳定、更可预测的性能。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK