Treap / Randomized cartesian tree

A treap is a height balanced binary tree. It is used to store a sequence in a tree, which allows for various applications like searching. A Cartesian tree, in case of a sorted sequence, would be basically a linked list, making tree virtually useless. Treap is used to solve such cases by using random priority for each node. Thus treap is a balanced binary tree with heap properties.

Read this article to understand Treap in depth

Have a doubt or thought? Join the discussion now

This is a companion discussion topic for the original entry at