treap

Documentation

Overview

Package treap implements a generic implicit treap (order-statistic tree).

What is a treap?

A treap is a randomised binary search tree that simultaneously satisfies two invariants: the binary search tree (BST) property on keys, and the heap property on random priorities. Because priorities are random the tree stays balanced in expectation, giving O(log n) height with high probability.

An "implicit" treap uses each node's subtree size as its implicit key rather than storing an explicit key. This makes the data structure a general-purpose ordered sequence: you can insert, delete, and access by 0-based position all in O(log n), with no key domain to worry about.

What this package provides

Treap is a sequence (not a map or set). It stores one element per node in insertion order, with subtree sizes as the implicit in-order keys.

All operations run in O(log n) expected time:

• Positional access: Treap.At, Treap.Front, Treap.Back
• Insert: Treap.InsertAfter, Treap.InsertBefore, Treap.PushBack, Treap.PushFront
• Delete: Treap.Remove
• Traversal: Treap.All

Callers may retain *Node pointers across mutations. A node pointer remains valid until it is passed to Treap.Remove. This enables O(1) external lookup (e.g. via a map keyed on some domain ID) followed by O(log n) InsertAfter or Remove — the primary use case this package is designed for.

Soft deletion (tombstones)

Treap.MarkDead marks a node as dead without removing it from the sequence. Dead nodes remain in the treap as position markers — useful when other nodes reference them as predecessors — but are excluded from Treap.Len, Treap.LiveAt, Treap.LiveRank, and Treap.All. A separate total-element count is available via Treap.TotalLen and positional access including dead nodes via Treap.At.

Index

• type Node
  • func Next[T any](n *Node[T]) *Node[T]
  • func (n *Node[T]) Alive() bool
  • func (n *Node[T]) Value() T
• type Treap
  • func New[T any]() *Treap[T]
  • func (r *Treap[T]) All() iter.Seq[T]
  • func (r *Treap[T]) At(i int) *Node[T]
  • func (r *Treap[T]) Back() *Node[T]
  • func (r *Treap[T]) Front() *Node[T]
  • func (r *Treap[T]) InsertAfter(v T, at *Node[T]) *Node[T]
  • func (r *Treap[T]) InsertBefore(v T, at *Node[T]) *Node[T]
  • func (r *Treap[T]) Len() int
  • func (r *Treap[T]) LiveAt(i int) *Node[T]
  • func (r *Treap[T]) LiveRank(n *Node[T]) int
  • func (r *Treap[T]) MarkDead(n *Node[T])
  • func (r *Treap[T]) PushBack(v T) *Node[T]
  • func (r *Treap[T]) PushFront(v T) *Node[T]
  • func (r *Treap[T]) Remove(n *Node[T])
  • func (r *Treap[T]) TotalLen() int

Types

type Node

type Node[T any] struct {
	// contains filtered or unexported fields
}

Node is a node in a Treap. Callers may hold *Node pointers across mutations: a node remains valid until it is passed to Treap.Remove.

func Next

func Next[T any](n *Node[T]) *Node[T]

Next returns the next node in sequence order (including dead nodes), or nil if n is the last node. O(log n) amortized. TODO: make this a method on Node?

func (*Node[T]) Alive

func (n *Node[T]) Alive() bool

Alive reports whether n has not been marked dead via Treap.MarkDead.

func (*Node[T]) Value

func (n *Node[T]) Value() T

Value returns the value stored in n.

type Treap

type Treap[T any] struct {
	// contains filtered or unexported fields
}

Treap is an implicit treap: a randomised binary search tree whose ordering key is the implicit in-order position of each node (derived from subtree sizes). All operations are O(log n) expected time.

func New

func New[T any]() *Treap[T]

New returns an empty Treap.

func (*Treap[T]) All

func (r *Treap[T]) All() iter.Seq[T]

All returns an iterator over live values in order, skipping dead nodes.

func (*Treap[T]) At

func (r *Treap[T]) At(i int) *Node[T]

At returns the node at 0-based position i among all nodes (including dead), or nil if i is out of range.

func (*Treap[T]) Back

func (r *Treap[T]) Back() *Node[T]

Back returns the last live node, or nil if the treap is empty.

func (*Treap[T]) Front

func (r *Treap[T]) Front() *Node[T]

Front returns the first live node, or nil if the treap is empty.

func (*Treap[T]) InsertAfter

func (r *Treap[T]) InsertAfter(v T, at *Node[T]) *Node[T]

InsertAfter inserts v immediately after at and returns its Node.

func (*Treap[T]) InsertBefore

func (r *Treap[T]) InsertBefore(v T, at *Node[T]) *Node[T]

InsertBefore inserts v immediately before at and returns its Node.

func (*Treap[T]) Len

func (r *Treap[T]) Len() int

Len returns the number of live (non-dead) elements.

func (*Treap[T]) LiveAt

func (r *Treap[T]) LiveAt(i int) *Node[T]

LiveAt returns the node at 0-based position i among live nodes only, or nil if i is out of range.

func (*Treap[T]) LiveRank

func (r *Treap[T]) LiveRank(n *Node[T]) int

LiveRank returns the 0-based position of n among live nodes. If n is dead the result is the position it would occupy if it were alive (i.e. the number of live nodes before n).

func (*Treap[T]) MarkDead

func (r *Treap[T]) MarkDead(n *Node[T])

MarkDead marks n as dead: it remains in the treap as a position marker but is excluded from Len, LiveAt, LiveRank, and All. Calling MarkDead on an already-dead node is a no-op. O(log n) due to the parent-pointer walk that updates liveSize up to the root.

func (*Treap[T]) PushBack

func (r *Treap[T]) PushBack(v T) *Node[T]

PushBack appends v at the end and returns its Node.

func (*Treap[T]) PushFront

func (r *Treap[T]) PushFront(v T) *Node[T]

PushFront prepends v at the front and returns its Node.

func (*Treap[T]) Remove

func (r *Treap[T]) Remove(n *Node[T])

Remove removes n from the treap. n must belong to this treap.

func (*Treap[T]) TotalLen

func (r *Treap[T]) TotalLen() int

TotalLen returns the total number of nodes, including dead ones.