123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149 |
- import java.util.ArrayList;
- import java.util.List;
-
- class BinTree<T extends Comparable> {
-
- public Node first = new Node();
-
- public void insert(T elem) {
- first.insert(elem);
- }
-
- public void remove(T elem) {
- first = remove(elem, first);
- }
- public Node remove(T elem, Node n) {
- if (n == null) return null;
-
- if (elem.compareTo(n.elem) < 0) {
- n.left = remove(elem, n.left);
- if (n.left != null) n.left.parent = n;
- } else if (elem.compareTo(n.elem) < 0) {
- n.right = remove(elem, n.right);
- if (n.right != null) n.right.parent = n;
- } else {
- if (n.left == null) {
- Node p = n.parent;
- n = n.right;
- if (n != null) n.parent = p;
- } else if (n.right == null) {
- Node p = n.parent;
- n = n.left;
- if (n != null) n.parent = p;
- } else {
- n.elem = n.right.findSmallest();
- n.right = remove(n.elem, n.right);
- n.right.parent = n;
- }
- }
- return n;
- }
-
- public Node search(T elem) {
- return first.search(elem);
- }
-
- public T findSmallest() {
- return first.findSmallest();
- }
-
- public T findBiggest() {
- return first.findBiggest();
- }
-
- public List<Node> findSimilar(T str) throws Exception {
- if (!(str instanceof String))
- throw new Exception("findSimilar only works on string trees");
-
- List<Node> similar = new ArrayList<>();
-
- for (String s: SpellUtils.similarWords((String)str)) {
- Node n = this.search((T)s);
- if (n != null)
- similar.add(n);
- }
-
- // Deduplicate
- List<Node> exists = new ArrayList<>();
- List<Node> res = new ArrayList<>();
- for (Node n: similar) {
- if (!exists.contains(n)) {
- exists.add(n);
- res.add(n);
- }
- }
-
- return res;
- }
-
- class Node {
- public Node left = null;
- public Node right = null;
- public Node parent;
-
- public T elem;
-
- public Node(Node parent) {
- this.parent = parent;
- }
- public Node() {
- this.parent = null;
- }
-
- public void insert(T elem) {
- if (this.elem == null) {
- this.elem = elem;
-
- } else if (this.elem.compareTo(elem) > 0) {
- if (this.left == null) {
- this.left = new Node(this);
- }
-
- this.left.insert(elem);
-
- } else {
- if (this.right == null) {
- this.right = new Node(this);
- }
-
- this.right.insert(elem);
- }
- }
-
- public T findSmallest() {
- if (this.left != null)
- return this.left.findSmallest();
- else
- return this.elem;
- }
-
- public T findBiggest() {
- if (this.right != null)
- return this.right.findBiggest();
- else
- return this.elem;
- }
-
- public Node search(T elem) {
- int cmp = this.elem.compareTo(elem);
- if (cmp == 0)
- return this;
- else if (cmp > 0 && this.left != null)
- return this.left.search(elem);
- else if (this.right != null)
- return this.right.search(elem);
- else
- return null;
- }
-
- public int depth() {
- int d = 0;
- Node n = this.parent;
- while (n != null) {
- d += 1;
- n = n.parent;
- }
- return d;
- }
- }
- }
|