Search

Text Color

Margin Size

Font Type

Enable Dyslexic Font

6.9: Treaps

Last updated

Apr 29, 2021
Save as PDF
- 6.8: B Trees
- 6.10: References

Wikibooks - Data Structures
Wikipedia

$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$

$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$

$\newcommand{\id}{\mathrm{id}}$ $\newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $\newcommand{\range}{\mathrm{range}\,}$

$\newcommand{\RealPart}{\mathrm{Re}}$ $\newcommand{\ImaginaryPart}{\mathrm{Im}}$

$\newcommand{\Argument}{\mathrm{Arg}}$ $\newcommand{\norm}[1]{\| #1 \|}$

$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\id}{\mathrm{id}}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\kernel}{\mathrm{null}\,}$

$\newcommand{\range}{\mathrm{range}\,}$

$\newcommand{\RealPart}{\mathrm{Re}}$

$\newcommand{\ImaginaryPart}{\mathrm{Im}}$

$\newcommand{\Argument}{\mathrm{Arg}}$

$\newcommand{\norm}[1]{\| #1 \|}$

$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$\newcommand{\Span}{\mathrm{span}}$ $\newcommand{\AA}{\unicode[.8,0]{x212B}}$

$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$

$\newcommand{\vectorC}[1]{\textbf{#1}}$

$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$

$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$

$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$

$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$

$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$

$\newcommand{\avec}{\mathbf a}$

$\newcommand{\bvec}{\mathbf b}$

$\newcommand{\cvec}{\mathbf c}$

$\newcommand{\dvec}{\mathbf d}$

$\newcommand{\dtil}{\widetilde{\mathbf d}}$

$\newcommand{\evec}{\mathbf e}$

$\newcommand{\fvec}{\mathbf f}$

$\newcommand{\nvec}{\mathbf n}$

$\newcommand{\pvec}{\mathbf p}$

$\newcommand{\qvec}{\mathbf q}$

$\newcommand{\svec}{\mathbf s}$

$\newcommand{\tvec}{\mathbf t}$

$\newcommand{\uvec}{\mathbf u}$

$\newcommand{\vvec}{\mathbf v}$

$\newcommand{\wvec}{\mathbf w}$

$\newcommand{\xvec}{\mathbf x}$

$\newcommand{\yvec}{\mathbf y}$

$\newcommand{\zvec}{\mathbf z}$

$\newcommand{\rvec}{\mathbf r}$

$\newcommand{\mvec}{\mathbf m}$

$\newcommand{\zerovec}{\mathbf 0}$

$\newcommand{\onevec}{\mathbf 1}$

$\newcommand{\real}{\mathbb R}$

$\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$

$\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$

$\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$

$\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$

$\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$

$\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$

$\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$

$\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$

$\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$

$\newcommand{\laspan}[1]{\text{Span}\{#1\}}$

$\newcommand{\bcal}{\cal B}$

$\newcommand{\ccal}{\cal C}$

$\newcommand{\scal}{\cal S}$

$\newcommand{\wcal}{\cal W}$

$\newcommand{\ecal}{\cal E}$

$\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$

$\newcommand{\gray}[1]{\color{gray}{#1}}$

$\newcommand{\lgray}[1]{\color{lightgray}{#1}}$

$\newcommand{\rank}{\operatorname{rank}}$

$\newcommand{\row}{\text{Row}}$

$\newcommand{\col}{\text{Col}}$

$\renewcommand{\row}{\text{Row}}$

$\newcommand{\nul}{\text{Nul}}$

$\newcommand{\var}{\text{Var}}$

$\newcommand{\corr}{\text{corr}}$

$\newcommand{\len}[1]{\left|#1\right|}$

$\newcommand{\bbar}{\overline{\bvec}}$

$\newcommand{\bhat}{\widehat{\bvec}}$

$\newcommand{\bperp}{\bvec^\perp}$

$\newcommand{\xhat}{\widehat{\xvec}}$

$\newcommand{\vhat}{\widehat{\vvec}}$

$\newcommand{\uhat}{\widehat{\uvec}}$

$\newcommand{\what}{\widehat{\wvec}}$

$\newcommand{\Sighat}{\widehat{\Sigma}}$

$\newcommand{\lt}{<}$

$\newcommand{\gt}{>}$

$\newcommand{\amp}{&}$

$\definecolor{fillinmathshade}{gray}{0.9}$

The invariant in a binary tree is that left is less than right with respect to insertion keys. e.g. for a key with order, ord(L) < ord(R). This doesn't dictate the relationship of nodes however, and left and right rotation does not affect the above. Therefore another order can be imposed. If the order is randomised, it is likely to counteract any skewness of a plain binary tree e.g. when inserting an already sorted input in order.

Below is a java example implementation, including a plain binary tree delete code example.

001import java.util.Iterator;
002import java.util.LinkedList;
003import java.util.Random;
004 
005public class Treap1<K extends Comparable<K>, V> {
006    public Treap1(boolean test) {
007        this.test = test;
008    }
009 
010    public Treap1() {}
011    boolean test = false;
012    static Random random = new Random(System.currentTimeMillis());
013 
014    class TreapNode {
015        int priority = 0;
016        K k;
017        V val;
018        TreapNode left, right;
019 
020        public TreapNode() {
021            if (!test) {
022                priority = random.nextInt();
023            }
024        }
025    }
026 
027    TreapNode root = null;
028 
029    void insert(K k, V val) {
030        root = insert(k, val, root);
031    }
032 
033    TreapNode insert(K k, V val, TreapNode node) {
034        TreapNode node2 = new TreapNode();
035        node2.k = k;
036        node2.val = val;
037        if (node == null) {
038            node = node2;
039        } else if (k.compareTo(node.k) < 0) {
040 
041            node.left = insert(k, val, node.left);
042 
043        } else {
044 
045            node.right = insert(k, val, node.right);
046 
047        }
048 
049        if (node.left != null && node.left.priority > node.priority) {
050            // left rotate
051            TreapNode tmp = node.left;
052            node.left = node.left.right;
053            tmp.right = node;
054            node = tmp;
055        } else if (node.right != null && node.right.priority > node.priority) {
056            // right rotate
057            TreapNode tmp = node.right;
058            node.right = node.right.left;
059            tmp.left = node;
060            node = tmp;
061        }
062        return node;
063    }
064 
065    V find(K k) {
066        return findNode(k, root);
067    }
068 
069    private V findNode(K k, Treap1<K, V>.TreapNode node) {
070         
071        if (node == null)
072            return null;
073        if (k.compareTo(node.k) < 0) {
074            return findNode(k, node.left);
075        } else if (k.compareTo(node.k) > 0) {
076            return findNode(k, node.right);
077        } else {
078            return node.val;
079        }
080    }
081     
082    static class Deleted {
083        boolean success = false;
084    }
085     
086    boolean delete(K k) {
087        Deleted del = new Deleted();
088        root = deleteNode(k, root, del);
089        return del.success;
090    }
091 
092    private Treap1<K, V>.TreapNode deleteNode(K k, Treap1<K, V>.TreapNode node, Deleted del) {
093          
094        if (node == null) {
095            return null;
096        } else if (k.compareTo(node.k) < 0) {
097             node.left = deleteNode(k, node.left, del) ;
098        } else if (k.compareTo(node.k) > 0) {
099            node.right = deleteNode(k, node.right, del);
100             
101            // k.compareTo(node.k) == 0
102        } else if ( node.left == null ) {
103                del.success = true;
104                return node.right;
105        } else if ( node.right == null) {
106              del.success = true;
107                return node.left;
108        } else if (node.left !=null && node.right != null){
109            /*
110            // left rotate and all delete on left subtree
111            TreapNode tmp = node.right;
112            node.right = node.right.left;
113          tmp.left = node;
114          node = tmp;           
115            node.left = deleteNode(k , node.left, del);
116            */
117             // more standard method ? doesn't disturb tree structure as much
118            // find leftmost descendant of the right child node and replace contents
119            TreapNode n2 = node.right;
120            TreapNode previous2 = null;
121            while (n2.left != null) {
122                previous2 = n2;
123                n2 = n2.left;
124            }
125             
126            if (previous2 != null) {
127                previous2.left = n2.right;
128                //n2 has no parent link, orphaned
129            } else {
130                node.right = n2.right;
131                //n2 has no parent link, orphaned
132            }
133 
134            node.k = n2.k;
135            node.val = n2.val;
136            del.success = true;
137            // once n2 out of scope, the orphaned node at n2 will be garbage collected, 
138        }
139         
140        return node;
141    }
142 
143    public static void main(String[] args) {
144        LinkedList<Integer> dat = new LinkedList<Integer>();
145 
146        for (int i = 0; i < 15000; ++i) {
147            dat.add(i);
148        }
149     
150            testNumbers(dat, true); // no random priority balancing
151            testNumbers(dat, false);
152    }
153 
154    private static void testNumbers(LinkedList<Integer> dat,
155            boolean test) {
156        Treap1<Integer, Integer> treap = new Treap1<>(test);
157 
158        for (Integer integer : dat) {
159            treap.insert(integer, integer);
160        }
161 
162        long t1 = System.currentTimeMillis();
163        Iterator<Integer> desc = dat.iterator();
164        int found = 0;
165        while (desc.hasNext()) {
166            Integer j = desc.next();
167            Integer i = treap.find(j);
168            if (j.equals(i)) {
169                ++found;
170            }
171        }
172        long t2 = System.currentTimeMillis();
173        System.out.println("found = " + found + " in " + (t2 - t1));
174         
175        System.out.println("test delete");
176        int deleted = 0;
177         
178        for (Integer integer : dat) {
179            if (treap.delete(integer)) 
180                    ++deleted;
181        }
182        System.out.println("Deleted = " + deleted);
183         
184    }
185}

Support Center

How can we help?