-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathBinarySearchTree.java
More file actions
137 lines (110 loc) · 3.35 KB
/
BinarySearchTree.java
File metadata and controls
137 lines (110 loc) · 3.35 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
/*
* File: BinarySearchTree.java
* Date: Dec 21, 2016
* Student: Devang Doshi | UCID: dbd24
* Course: Programming, Data Structure, and Alogrithms | Section: CS50581
* Desc: Implementation of Binary Search Tree.
/**
*
* @author Devang
*/
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class BinarySearchTree<E extends Comparable<? super E>> extends BinaryTree<E> {
public Node<E> getRoot(){
return root;
}
@Override
public void insert(E data) {
Node<E> newNode = new Node<E>(data);
if (root == null) {
root = newNode;
} else {
InsertHelper(root, newNode);
}
}
private void InsertHelper(Node<E> node, Node<E> newNode) {
int compareResult = node.data.compareTo(newNode.data);
if (compareResult <= 0) {
if (node.right == null) {
node.right = newNode;
} else {
InsertHelper(node.right, newNode);
}
} else {
if (node.left == null) {
node.left = newNode;
} else {
InsertHelper(node.left, newNode);
}
}
}
@Override
public void remove(E key) {
root = RemoveHelper(root, key);
}
private E findMinimum(Node<E> node) {
if (node.left == null) return node.data;
return findMinimum(node.left);
}
private Node<E> RemoveHelper(Node<E> node, E key) {
int compareResult = node.data.compareTo(key);
if (compareResult < 0) {
node.right = RemoveHelper(node.right, key);
} else if (compareResult > 0) {
node.left = RemoveHelper(node.left, key);
} else {
if (node.left == null) {
return node.right;
} else if (node.right == null) {
return node.left;
}
E minValue = findMinimum(node.right);
node.data = minValue;
RemoveHelper(node.right, minValue);
}
return node;
}
@Override
public boolean search(E key) {
return SearchHelper(this.root, key);
}
private boolean SearchHelper(Node<E> node, E key) {
if (node == null) return false;
int compareResult = node.data.compareTo(key);
if (compareResult == 0) return true;
return compareResult < 0 ? SearchHelper(node.right, key) : SearchHelper(node.left, key);
}
public class BinarySearchTreeIterator implements Iterator<E> {
private List<E> elements = new ArrayList<E>();
private int index = 0;
public BinarySearchTreeIterator(BinarySearchTree<E> tree)
{
InOrder(tree.getRoot());
}
private void InOrder(Node<E> node) {
if (node == null) return;
InOrder(node.left);
elements.add(node.data);
InOrder(node.right);
}
@Override
public boolean hasNext() {
return (index < elements.size());
}
@Override
public E next() {
if(!hasNext()) return null;
E temp = elements.get(index);
index++;
return temp;
}
@Override
public void remove() {
}
}
public Iterator<E> iterator() {
return new BinarySearchTreeIterator(this);
}
}