Treap / Randomized cartesian tree

data-structure
binary-tree
tree-data-structure
cartesian-tree
treap

(Team) #1

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 http://iq.opengenus.org/treap-randomized-cartesian-tree/