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 root.left;
} 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);
}
}
Y2xhc3MgQmluU2VhcmNoVHJlZSB7CiAgcHVibGljIHN0YXRpYyBjbGFzcyBOb2RlIHsKICAgIHByaXZhdGUgQ29tcGFyYWJsZSB2YWx1ZTsKICAgIHByaXZhdGUgTm9kZSBsZWZ0OwogICAgcHJpdmF0ZSBOb2RlIHJpZ2h0OwogICAgcHJpdmF0ZSBOb2RlKENvbXBhcmFibGUgdmFsdWUpIHsKICAgICAgdGhpcy52YWx1ZSA9IHZhbHVlOwogICAgICB0aGlzLmxlZnQgPSB0aGlzLnJpZ2h0ID0gbnVsbDsKICAgIH0KICAgIHB1YmxpYyBTdHJpbmcgdG9TdHJpbmcoKSB7CiAgICAgIHJldHVybiAiTm9kZSgiICsgdmFsdWUgKyAiKSI7IAogICAgfQogICAgcHJpdmF0ZSBzdGF0aWMgdm9pZCB0b1N0cmluZyhTdHJpbmdCdWlsZGVyIGJ1ZiwgTm9kZSByb290KSB7CiAgICAgIGlmIChyb290ID09IG51bGwpCiAgICAgICAgcmV0dXJuOwogICAgICB0b1N0cmluZyhidWYsIHJvb3QubGVmdCk7CiAgICAgIGJ1Zi5hcHBlbmQocm9vdC52YWx1ZSk7CiAgICAgIGJ1Zi5hcHBlbmQoIiAiKTsKICAgICAgdG9TdHJpbmcoYnVmLCByb290LnJpZ2h0KTsKICAgIH0KICAgIHByaXZhdGUgc3RhdGljIE5vZGUgaW5zZXJ0KENvbXBhcmFibGUgdmFsdWUsIE5vZGUgcm9vdCkgewogICAgICBpZiAocm9vdCA9PSBudWxsKQogICAgICAgIHJldHVybiBuZXcgTm9kZSh2YWx1ZSk7CiAgICAgIGludCBjbXAgPSByb290LnZhbHVlLmNvbXBhcmVUbyh2YWx1ZSk7CiAgICAgIGlmIChjbXAgPCAwKQogICAgICAgIHJvb3QucmlnaHQgPSBpbnNlcnQodmFsdWUsIHJvb3QucmlnaHQpOyAKICAgICAgZWxzZQogICAgICAgIHJvb3QubGVmdCA9IGluc2VydCh2YWx1ZSwgcm9vdC5sZWZ0KTsKICAgICAgcmV0dXJuIHJvb3Q7CiAgICB9CiAgICBwcml2YXRlIHN0YXRpYyBOb2RlIHJlbW92ZShDb21wYXJhYmxlIHZhbHVlLCBOb2RlIHJvb3QpIHsKICAgICAgaWYgKHJvb3QgPT0gbnVsbCkKICAgICAgICByZXR1cm4gbnVsbDsKICAgICAgaW50IGNtcCA9IHJvb3QudmFsdWUuY29tcGFyZVRvKHZhbHVlKTsKICAgICAgaWYgKGNtcCA9PSAwKSB7CiAgICAgICAgaWYgKHJvb3QubGVmdCA9PSBudWxsKQogICAgICAgICAgcmV0dXJuIHJvb3QucmlnaHQ7CiAgICAgICAgaWYgKHJvb3QucmlnaHQgPT0gbnVsbCkKICAgICAgICAgIHJldHVybiByb290LmxlZnQ7CiAgICAgICAgTm9kZSBuID0gc2VhcmNoTGFyZ2VzdE5vZGUocm9vdC5sZWZ0KTsKICAgICAgICBuLnJpZ2h0ID0gcm9vdC5yaWdodDsKICAgICAgICByZXR1cm4gcm9vdC5sZWZ0OwogICAgICB9IGVsc2UgaWYgKGNtcCA8IDApCiAgICAgICAgcm9vdC5yaWdodCA9IHJlbW92ZSh2YWx1ZSwgcm9vdC5yaWdodCk7IAogICAgICBlbHNlCiAgICAgICAgcm9vdC5sZWZ0ID0gcmVtb3ZlKHZhbHVlLCByb290LmxlZnQpOwogICAgICByZXR1cm4gcm9vdDsKICAgIH0KICAgIHByaXZhdGUgc3RhdGljIE5vZGUgc2VhcmNoTGFyZ2VzdE5vZGUoTm9kZSByb290KSB7CiAgICAgIGlmIChyb290LnJpZ2h0ID09IG51bGwpCiAgICAgICAgcmV0dXJuIHJvb3Q7CiAgICAgIHJldHVybiBzZWFyY2hMYXJnZXN0Tm9kZShyb290LnJpZ2h0KTsKICAgIH0KICB9CgogIHByaXZhdGUgTm9kZSByb290Tm9kZTsKICBwdWJsaWMgQmluU2VhcmNoVHJlZSgpIHsKICAgIHJvb3ROb2RlID0gbnVsbDsKICB9CiAgcHVibGljIHZvaWQgaW5zZXJ0KENvbXBhcmFibGUgdmFsdWUpIHsKICAgIHJvb3ROb2RlID0gTm9kZS5pbnNlcnQodmFsdWUsIHJvb3ROb2RlKTsKICB9CiAgcHVibGljIHZvaWQgcmVtb3ZlKENvbXBhcmFibGUgdmFsdWUpIHsKICAgIHJvb3ROb2RlID0gTm9kZS5yZW1vdmUodmFsdWUsIHJvb3ROb2RlKTsKICB9CiAgcHVibGljIFN0cmluZyB0b1N0cmluZygpIHsKICAgIFN0cmluZ0J1aWxkZXIgYnVmID0gbmV3IFN0cmluZ0J1aWxkZXIoKTsKICAgIGJ1Zi5hcHBlbmQoIlsiKTsKICAgIE5vZGUudG9TdHJpbmcoYnVmLCByb290Tm9kZSk7CiAgICBidWYuYXBwZW5kKCJdIik7CiAgICByZXR1cm4gYnVmLnRvU3RyaW5nKCk7CiAgfQp9CgpjbGFzcyBNYWluIHsKICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB7CiAgICBCaW5TZWFyY2hUcmVlIHRyZWUxID0gbmV3IEJpblNlYXJjaFRyZWUoKTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgMTA7IGkrKykgewogICAgICB0cmVlMS5pbnNlcnQoKGludCkoTWF0aC5yYW5kb20oKSAqIDEwMCkpOwogICAgfQogICAgU3lzdGVtLm91dC5wcmludGxuKHRyZWUxKTsKICAgIAogICAgQmluU2VhcmNoVHJlZSB0cmVlMiA9IG5ldyBCaW5TZWFyY2hUcmVlKCk7CiAgICB0cmVlMi5pbnNlcnQoMjApOwogICAgdHJlZTIuaW5zZXJ0KDMwKTsKICAgIHRyZWUyLmluc2VydCgxMCk7CiAgICB0cmVlMi5yZW1vdmUoMjApOwogICAgU3lzdGVtLm91dC5wcmludGxuKHRyZWUyKTsKICB9Cn0K