class BinSearchTree {
public static class Node {
private Node left;
private Node right;
this.value = value;
this.left = this.right = null;
}
return "Node(" + value + ")";
}
private static void toString(StringBuilder buf, Node root) {
if (root == null)
return;
toString(buf, root.left);
buf.append(root.value);
buf.append(" ");
toString(buf, root.right);
}
private static Node insert
(Comparable value, Node root
) { if (root == null)
return new Node(value);
int cmp = root.value.compareTo(value);
if (cmp < 0)
root.right = insert(value, root.right);
else
root.left = insert(value, root.left);
return root;
}
private static Node remove
(Comparable value, Node root
) { if (root == null)
return null;
int cmp = root.value.compareTo(value);
if (cmp == 0) {
if (root.left == null)
return root.right;
if (root.right == null)
return root.left;
Node n = searchLargestNode(root.left);
n.right = root.right;
return n;
} else if (cmp < 0)
root.right = remove(value, root.right);
else
root.left = remove(value, root.left);
return root;
}
private static Node searchLargestNode(Node root) {
if (root.right == null)
return root;
return searchLargestNode(root.right);
}
}
private Node rootNode;
public BinSearchTree() {
rootNode = null;
}
rootNode = Node.insert(value, rootNode);
}
rootNode = Node.remove(value, rootNode);
}
StringBuilder buf = new StringBuilder();
buf.append("[");
Node.toString(buf, rootNode);
buf.append("]");
return buf.toString();
}
}
class Main {
public static void main
(String[] args
) { BinSearchTree tree1 = new BinSearchTree();
for (int i = 0; i < 10; i++) {
tree1.
insert((int)(Math.
random() * 100)); }
BinSearchTree tree2 = new BinSearchTree();
tree2.insert(20);
tree2.insert(30);
tree2.insert(10);
tree2.remove(20);
}
}
Y2xhc3MgQmluU2VhcmNoVHJlZSB7CiAgcHVibGljIHN0YXRpYyBjbGFzcyBOb2RlIHsKICAgIHByaXZhdGUgQ29tcGFyYWJsZSB2YWx1ZTsKICAgIHByaXZhdGUgTm9kZSBsZWZ0OwogICAgcHJpdmF0ZSBOb2RlIHJpZ2h0OwogICAgcHJpdmF0ZSBOb2RlKENvbXBhcmFibGUgdmFsdWUpIHsKICAgICAgdGhpcy52YWx1ZSA9IHZhbHVlOwogICAgICB0aGlzLmxlZnQgPSB0aGlzLnJpZ2h0ID0gbnVsbDsKICAgIH0KICAgIHB1YmxpYyBTdHJpbmcgdG9TdHJpbmcoKSB7CiAgICAgIHJldHVybiAiTm9kZSgiICsgdmFsdWUgKyAiKSI7IAogICAgfQogICAgcHJpdmF0ZSBzdGF0aWMgdm9pZCB0b1N0cmluZyhTdHJpbmdCdWlsZGVyIGJ1ZiwgTm9kZSByb290KSB7CiAgICAgIGlmIChyb290ID09IG51bGwpCiAgICAgICAgcmV0dXJuOwogICAgICB0b1N0cmluZyhidWYsIHJvb3QubGVmdCk7CiAgICAgIGJ1Zi5hcHBlbmQocm9vdC52YWx1ZSk7CiAgICAgIGJ1Zi5hcHBlbmQoIiAiKTsKICAgICAgdG9TdHJpbmcoYnVmLCByb290LnJpZ2h0KTsKICAgIH0KICAgIHByaXZhdGUgc3RhdGljIE5vZGUgaW5zZXJ0KENvbXBhcmFibGUgdmFsdWUsIE5vZGUgcm9vdCkgewogICAgICBpZiAocm9vdCA9PSBudWxsKQogICAgICAgIHJldHVybiBuZXcgTm9kZSh2YWx1ZSk7CiAgICAgIGludCBjbXAgPSByb290LnZhbHVlLmNvbXBhcmVUbyh2YWx1ZSk7CiAgICAgIGlmIChjbXAgPCAwKQogICAgICAgIHJvb3QucmlnaHQgPSBpbnNlcnQodmFsdWUsIHJvb3QucmlnaHQpOyAKICAgICAgZWxzZQogICAgICAgIHJvb3QubGVmdCA9IGluc2VydCh2YWx1ZSwgcm9vdC5sZWZ0KTsKICAgICAgcmV0dXJuIHJvb3Q7CiAgICB9CiAgICBwcml2YXRlIHN0YXRpYyBOb2RlIHJlbW92ZShDb21wYXJhYmxlIHZhbHVlLCBOb2RlIHJvb3QpIHsKICAgICAgaWYgKHJvb3QgPT0gbnVsbCkKICAgICAgICByZXR1cm4gbnVsbDsKICAgICAgaW50IGNtcCA9IHJvb3QudmFsdWUuY29tcGFyZVRvKHZhbHVlKTsKICAgICAgaWYgKGNtcCA9PSAwKSB7CiAgICAgICAgaWYgKHJvb3QubGVmdCA9PSBudWxsKQogICAgICAgICAgcmV0dXJuIHJvb3QucmlnaHQ7CiAgICAgICAgaWYgKHJvb3QucmlnaHQgPT0gbnVsbCkKICAgICAgICAgIHJldHVybiByb290LmxlZnQ7CiAgICAgICAgTm9kZSBuID0gc2VhcmNoTGFyZ2VzdE5vZGUocm9vdC5sZWZ0KTsKICAgICAgICBuLnJpZ2h0ID0gcm9vdC5yaWdodDsKICAgICAgICByZXR1cm4gbjsKICAgICAgfSBlbHNlIGlmIChjbXAgPCAwKQogICAgICAgIHJvb3QucmlnaHQgPSByZW1vdmUodmFsdWUsIHJvb3QucmlnaHQpOyAKICAgICAgZWxzZQogICAgICAgIHJvb3QubGVmdCA9IHJlbW92ZSh2YWx1ZSwgcm9vdC5sZWZ0KTsKICAgICAgcmV0dXJuIHJvb3Q7CiAgICB9CiAgICBwcml2YXRlIHN0YXRpYyBOb2RlIHNlYXJjaExhcmdlc3ROb2RlKE5vZGUgcm9vdCkgewogICAgICBpZiAocm9vdC5yaWdodCA9PSBudWxsKQogICAgICAgIHJldHVybiByb290OwogICAgICByZXR1cm4gc2VhcmNoTGFyZ2VzdE5vZGUocm9vdC5yaWdodCk7CiAgICB9CiAgfQoKICBwcml2YXRlIE5vZGUgcm9vdE5vZGU7CiAgcHVibGljIEJpblNlYXJjaFRyZWUoKSB7CiAgICByb290Tm9kZSA9IG51bGw7CiAgfQogIHB1YmxpYyB2b2lkIGluc2VydChDb21wYXJhYmxlIHZhbHVlKSB7CiAgICByb290Tm9kZSA9IE5vZGUuaW5zZXJ0KHZhbHVlLCByb290Tm9kZSk7CiAgfQogIHB1YmxpYyB2b2lkIHJlbW92ZShDb21wYXJhYmxlIHZhbHVlKSB7CiAgICByb290Tm9kZSA9IE5vZGUucmVtb3ZlKHZhbHVlLCByb290Tm9kZSk7CiAgfQogIHB1YmxpYyBTdHJpbmcgdG9TdHJpbmcoKSB7CiAgICBTdHJpbmdCdWlsZGVyIGJ1ZiA9IG5ldyBTdHJpbmdCdWlsZGVyKCk7CiAgICBidWYuYXBwZW5kKCJbIik7CiAgICBOb2RlLnRvU3RyaW5nKGJ1Ziwgcm9vdE5vZGUpOwogICAgYnVmLmFwcGVuZCgiXSIpOwogICAgcmV0dXJuIGJ1Zi50b1N0cmluZygpOwogIH0KfQoKY2xhc3MgTWFpbiB7CiAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewogICAgQmluU2VhcmNoVHJlZSB0cmVlMSA9IG5ldyBCaW5TZWFyY2hUcmVlKCk7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IDEwOyBpKyspIHsKICAgICAgdHJlZTEuaW5zZXJ0KChpbnQpKE1hdGgucmFuZG9tKCkgKiAxMDApKTsKICAgIH0KICAgIFN5c3RlbS5vdXQucHJpbnRsbih0cmVlMSk7CiAgICAKICAgIEJpblNlYXJjaFRyZWUgdHJlZTIgPSBuZXcgQmluU2VhcmNoVHJlZSgpOwogICAgdHJlZTIuaW5zZXJ0KDIwKTsKICAgIHRyZWUyLmluc2VydCgzMCk7CiAgICB0cmVlMi5pbnNlcnQoMTApOwogICAgdHJlZTIucmVtb3ZlKDIwKTsKICAgIFN5c3RlbS5vdXQucHJpbnRsbih0cmVlMik7CiAgfQp9Cgo=