Treap
Table of Contents
Non-rotational treap (FHQ Treap) can be used to maintain sequence operations and balanced tree.
1. Split Operation
1.1. By Value
Suppose treap root cur and key value key, and we want to split treap into 2 parts \(\le key\) (treap A) and \(\gt key\) (treap B). Also, we assume the treap is already in order.
Consider the current root. If cur has value smaller than key, then we know that cur and its left child must belong to treap A. So we just need to figure out the part of right child that belongs to treap A, say it’s subtreap C. Then, we set cur’s right child to subtreap C, and that becomes treap A.
1.2. By Size/Rank
If we want to split by size or rank, we only need to know the size information.