-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy pathBinarySearchTreeNode.java
More file actions
184 lines (158 loc) · 4.07 KB
/
BinarySearchTreeNode.java
File metadata and controls
184 lines (158 loc) · 4.07 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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
/*
* binary search tree implementation
*/
public class BinarySearchTreeNode {
int key;
int value;
int size;
BinarySearchTreeNode left;
BinarySearchTreeNode right;
public BinarySearchTreeNode(int k) {
key = k;
value = 1000; // default value;
left = null;
right = null;
}
// return the TreeNode have found
// return null if we find nothing
public BinarySearchTreeNode search0(BinarySearchTreeNode root, int target) {
if(root == null) { // not necessary
return root;
}
BinarySearchTreeNode cur = root;
while(cur != null) {
if(cur.key == target) {
return cur;
}
else if(cur.key > target) {
cur = cur.left;
}
else { // cur.key < target
cur = cur.right;
}
}
return cur;
}
// recursive search using tail recursion
public BinarySearchTreeNode search(BinarySearchTreeNode root, int target) {
if(root == null) {
return root;
}
if(root.key == target) {
return root;
}
else if(root.key > target) {
return search(root.left, target);
}
else {
return search(root.right, target);
}
}
// insert a specific key into the BST, return the root of the BST
// my first implementation is WRONG!!!!!!!!!!!
public BinarySearchTreeNode insertWrong(BinarySearchTreeNode root, int key) {
while(root != null) {
if(root.key == key) {
return root;
}
else if(root.key > key) {
root = root.left;
}
else {
root = root.right;
}
}
root = new BinarySearchTreeNode(key); // !!! it's wrong!!!!! since it not enough, didn't dereference
return root;
}
// This is the RIGHT version!!!!
public BinarySearchTreeNode insert0(BinarySearchTreeNode root, int key) {
if(root == null) {
root = new BinarySearchTreeNode(key);
return root;
}
BinarySearchTreeNode cur = root;
BinarySearchTreeNode pre = null;
while(cur != null) {
if(cur.key == key) { // already exist, just return root
return root;
}
else if(cur.key > key) {
pre = cur;
cur = cur.left;
}
else { // cur.key < key
pre = cur;
cur = cur.right;
}
}
// now cur == null, pre is the parent of null
if(pre.key > key) {
pre.left = new BinarySearchTreeNode(key);
}
else { // pre.key < key
pre.right = new BinarySearchTreeNode(key);
}
return root;
}
// insert using recursion. Elegant!!
// return the root after insertion
public BinarySearchTreeNode insert(BinarySearchTreeNode root, int key) {
if(root == null) {
return new BinarySearchTreeNode(key);
}
if(root.key == key) {
return root;
}
else if(root.key > key) {
root.left = insert(root.left, key);
}
else {
root.right = insert(root.right, key);
}
return root;
}
// delete the node in the BST, return the root after deletion
public BinarySearchTreeNode delete(BinarySearchTreeNode root, int key) {
if(root == null) {
return root;
}
// first, find target node
if(root.key > key) {
root.left = delete(root.left, key);
return root;
}
else if(root.key < key) {
root.right = delete(root.right, key);
return root;
}
// now root != null && root.key == key
if(root.left == null) {
return root.right;
}
else if(root.right == null) {
return root.left;
}
// now root has both left and right child, find the smallest element in right child and set it to replace the deleted position
if(root.right.left == null) { // !!!
root.right.left = root.left;
return root.right;
}
// now right child has both left and right child
BinarySearchTreeNode smallest = findandDeleteSmallest(root.right);
smallest.left = root.left;
smallest.right = root.right;
return smallest;
}
private BinarySearchTreeNode findandDeleteSmallest(BinarySearchTreeNode root) {
BinarySearchTreeNode cur = root;
BinarySearchTreeNode pre = null;
while(cur.left != null) {
pre = cur;
cur = cur.left;
}
// now cur is the left most node, pre is parent of cur
pre.left = cur.right;
return cur;
}
}