package edu.princeton.cs.algs4.growingtree.demos;

/**
 * Randomized Binary Search Tree Deletion Operator
 * @author Josh Israel
 */

import edu.princeton.cs.algs4.growingtree.framework.NodeProperties;
import edu.princeton.cs.algs4.growingtree.interfaces.IAlgorithmNode;
import edu.princeton.cs.algs4.growingtree.interfaces.IDeleteOperator;
import edu.princeton.cs.algs4.growingtree.interfaces.IDeletingNode;

public class RandomizedBSTDeletion<P extends NodeProperties> implements IDeleteOperator<P> {
	
	private void joinLR(IDeletingNode<P> d) {
		IAlgorithmNode<P> left = d.getLeft();
		IAlgorithmNode<P> right = d.getRight();
		if (left == null || right == null) {
			d.successorHibbardDelete();
			return;
		}

		double ratio = (double) left.getNodeProperties().getSize() / (left.getNodeProperties().getSize() + right.getNodeProperties().getSize());
		boolean promoteLeft = StdRandom.bernoulli(ratio);
		if (promoteLeft)  {
			d.rotateRight();
			joinLR(d);
		}
		else {
			d.rotateLeft();
			joinLR(d);
        }
    }
	
	@Override
	public void doDelete(IAlgorithmNode<P> root, IDeletingNode<P> node) {
		joinLR(node);
	}

}