Entry getPrecedingEntry(final Object key) {
	Entry p = this.root;
	if (p==null) {
		return null;
	}

	while (true) {
	    final int cmp = this.compare(key, p.key);
            if (cmp > 0) {
		if (p.right != null) {
			p = p.right;
		} else {
			return p;
		}
	    } else {
		if (p.left != null) {
		    p = p.left;
		} else {
		    Entry parent = p.parent;
		    Entry ch = p;
		    while (parent != null && ch == parent.left) {
			ch = parent;
			parent = parent.parent;
		    }
		    return parent;
		}
	    }
	}
    }