简介

Treap是一种比较方便实现的平衡二叉树。顾名思义，Treap = Tree + Heap，既有二叉搜索树的性质，又有堆的性质。Treap属于笛卡尔树的一种，因此也可以使用笛卡尔树的 $O(n)$ 方法构造。

Treap的思想是在二叉搜索树的基础上，给每一个节点一个随机的权重 $priority$ ，然后根据一些手段在不破坏二叉搜索树性质的前提下将所有节点根据权重进行重新组织，使得权重满足堆的性质。由于权重的随机性，所以可以认为Treap能够在增删操作之下的相对平衡，不会退化成链。

实现

实现Treap的关键在于如何在保持二叉搜索树的前提下进行节点的重组。主要方法有两种：旋转法和分裂法，一般使用较多的是旋转法，Python代码如下：

import random


class TreapNode:
    def __init__(self, key: int):
        self.size = 1
        self.key = key
        self.fix = random.randint(, 1000)
        self.children = [None, None]

    def rotate(self, towards: int):
        y = self.children[1 ^ towards]
        self.children[1 ^ towards] = y.children[towards]
        y.children[towards] = self
        # 不要忘记maintain
        # 应该先maintain x再maintain y，层次已经发生变化
        self.push_up()
        y.push_up()
        self = y

    def push_up(self):
        self.size = 1
        if self.children[] != None:
            self.size += self.children[].size
        if self.children[1] != None:
            self.size += self.children[1].size


class Treap:
    def __init__(self):
        self.root = None

    def _insert(self, node, key):
        if node is None:
            return TreapNode(key)
        d =  if node.key > key else 1
        node.children[d] = self._insert(node.children[d], key)
        if node.children[d].fix > node.fix:
            node.rotate(1 ^ d)
				# 不要忘记！
        node.push_up()
        return node

    def insert(self, key):
        self.root = self._insert(self.root, key)

    def _delete(self, node, key: int):
        if node is None:
            return node
        if node.key != key:
            d =  if node.key > key else 1
            node.children[d] = self._delete(node.children[d], key)
        else:
            if node.children[] is None:
                node = node.children[1]
            elif node.children[1] is None:
                node = node.children[]
            else:
                # 跟堆一样，找一个fix小的儿子代替自己
                towards = 1 if node.children[].fix < node.children[1].fix else 
                node.rotate(towards)
                node.children[towards] = self._delete(
                    node.children[towards], key)
				# 不要忘记最后一步！
        if node != None:
            node.push_up()
        return node

    def delete(self, key: int):
        self.root = self._delete(self.root, key)

    def _kth(self, node, k: int):
        if node is None:
            return - 1
        left_size =  if not node.children[] else node.children[].size

        if left_size + 1 == k:
            return node.key
        return self._kth(node.children[1], k - 1 - left_size)

    def kth(self, k: int):
        return self._kth(self.root, k)

ITPub博客

数据结构：Treap

简介

实现

最新文章