#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/advanced-trees/treap-insert-and-delete

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/advanced-trees/treap-insert-and-delete

Repovive

Treap Insert and Delete - Advanced Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Treap Insert and Delete

Using split and merge

Insert and delete are built from split and merge:

Insert key k:

(left, right) := split(root, k)
newNode := createNode(k, randomPriority())
root := merge(merge(left, newNode), right)

Delete key k:

(left, mid) := split(root, k)
(toDelete, right) := split(mid, k + 1)
root := merge(left, right)

Both operations are $O(\log n)$ expected. The simplicity of split/merge makes treaps easy to implement correctly.