6.9: Treaps

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.

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Random;

public class Treap1<K extends Comparable<K>, V> {
	public Treap1(boolean test) {
		this.test = test;
	}

	public Treap1() {}
	boolean test = false;
	static Random random = new Random(System.currentTimeMillis());

	class TreapNode {
		int priority = 0;
		K k;
		V val;
		TreapNode left, right;

		public TreapNode() {
			if (!test) {
				priority = random.nextInt();
			}
		}
	}

	TreapNode root = null;

	void insert(K k, V val) {
		root = insert(k, val, root);
	}

	TreapNode insert(K k, V val, TreapNode node) {
		TreapNode node2 = new TreapNode();
		node2.k = k;
		node2.val = val;
		if (node == null) {
			node = node2;
		} else if (k.compareTo(node.k) < 0) {

			node.left = insert(k, val, node.left);

		} else {

			node.right = insert(k, val, node.right);

		}

		if (node.left != null && node.left.priority > node.priority) {
			// left rotate
			TreapNode tmp = node.left;
			node.left = node.left.right;
			tmp.right = node;
			node = tmp;
		} else if (node.right != null && node.right.priority > node.priority) {
			// right rotate
			TreapNode tmp = node.right;
			node.right = node.right.left;
			tmp.left = node;
			node = tmp;
		}
		return node;
	}

	V find(K k) {
		return findNode(k, root);
	}

	private V findNode(K k, Treap1<K, V>.TreapNode node) {
		
		if (node == null)
			return null;
		if (k.compareTo(node.k) < 0) {
			return findNode(k, node.left);
		} else if (k.compareTo(node.k) > 0) {
			return findNode(k, node.right);
		} else {
			return node.val;
		}
	}
	
	static class Deleted {
		boolean success = false;
	}
	
	boolean delete(K k) {
		Deleted del = new Deleted();
		root = deleteNode(k, root, del);
		return del.success;
	}

	private Treap1<K, V>.TreapNode deleteNode(K k, Treap1<K, V>.TreapNode node, Deleted del) {
		 
		if (node == null) {
			return null;
		} else if (k.compareTo(node.k) < 0) {
			 node.left = deleteNode(k, node.left, del) ;
		} else if (k.compareTo(node.k) > 0) {
			node.right = deleteNode(k, node.right, del);
			
			// k.compareTo(node.k) == 0
		} else if ( node.left == null ) {
				del.success = true;
				return node.right;
		} else if ( node.right == null) {
			  del.success = true;
				return node.left;
		} else if (node.left !=null && node.right != null){
			/*
			// left rotate and all delete on left subtree
			TreapNode tmp = node.right;
			node.right = node.right.left;
		  tmp.left = node;
		  node = tmp;			
			node.left = deleteNode(k , node.left, del);
			*/
			 // more standard method ? doesn't disturb tree structure as much
			// find leftmost descendant of the right child node and replace contents
			TreapNode n2 = node.right;
			TreapNode previous2 = null;
			while (n2.left != null) {
				previous2 = n2;
				n2 = n2.left;
			}
			
			if (previous2 != null) {
				previous2.left = n2.right;
                //n2 has no parent link, orphaned
			} else {
				node.right = n2.right;
                //n2 has no parent link, orphaned
			}

			node.k = n2.k;
			node.val = n2.val;
			del.success = true;
            // once n2 out of scope, the orphaned node at n2 will be garbage collected, 
		}
		
		return node;
	}

	public static void main(String[] args) {
		LinkedList<Integer> dat = new LinkedList<Integer>();

		for (int i = 0; i < 15000; ++i) {
			dat.add(i);
		}
	
			testNumbers(dat, true); // no random priority balancing
			testNumbers(dat, false);
	}

	private static void testNumbers(LinkedList<Integer> dat,
			boolean test) {
		Treap1<Integer, Integer> treap = new Treap1<>(test);

		for (Integer integer : dat) {
			treap.insert(integer, integer);
		}

		long t1 = System.currentTimeMillis();
		Iterator<Integer> desc = dat.iterator();
		int found = 0;
		while (desc.hasNext()) {
			Integer j = desc.next();
			Integer i = treap.find(j);
			if (j.equals(i)) {
				++found;
			}
		}
		long t2 = System.currentTimeMillis();
		System.out.println("found = " + found + " in " + (t2 - t1));
		
		System.out.println("test delete");
		int deleted = 0;
		
		for (Integer integer : dat) {
			if (treap.delete(integer)) 
					++deleted;
		}
		System.out.println("Deleted = " + deleted);
		
	}
}