-
Notifications
You must be signed in to change notification settings - Fork 0
/
BinarySearchTree.js
166 lines (155 loc) · 6.46 KB
/
BinarySearchTree.js
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
/**
* Is a tree like data structure
**Rules**
*It starts with a root node
*each node ca have at most 2 nodes
*descreasing items are placed in the left
*Ascending items are placed at the right
*it uses divide and conquer mode of operation
log node = 2^height
**Tpes**
*Balanced:
*each node has 2 siblings
*it is O(log N)
*Unbalanced:
*each node has unqual siblings
*it is O(N)
*/
class Node{
constructor(value){
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor(){
this.root = null;
}
insert(value){
const node = new Node(value)
if(this.root === null) this.root = node;
else{
let currentNode = this.root;
while (true) {
if(value < currentNode.value){
//Left
if(!currentNode.left){
currentNode.left = node;
return this;
}
currentNode = currentNode.left;
}else{
//Right
if(!currentNode.right){
currentNode.right = node;
return this;
}
currentNode = currentNode.right;
}
}
}
}
lookup(value){
if(!this.root) return false;
let currentNode = this.root;
while(currentNode){
if(value < currentNode.value){
//Left
currentNode = currentNode.left
}else if(value > currentNode.value){
//Right
currentNode = currentNode.right
}else if(value === currentNode.value){
return currentNode
}
}
return false
}
remove(value) {
if (!this.root) {
return false;
}
let currentNode = this.root;
let parentNode = null;
while(currentNode){
if(value < currentNode.value){
parentNode = currentNode;
currentNode = currentNode.left;
} else if(value > currentNode.value){
parentNode = currentNode;
currentNode = currentNode.right;
} else if (currentNode.value === value) {
//We have a match, get to work!
//Option 1: No right child:
if (currentNode.right === null) {
if (parentNode === null) {
this.root = currentNode.left;
} else {
//if parent > current value, make current left child a child of parent
if(currentNode.value < parentNode.value) {
parentNode.left = currentNode.left;
//if parent < current value, make left child a right child of parent
} else if(currentNode.value > parentNode.value) {
parentNode.right = currentNode.left;
}
}
//Option 2: Right child which doesnt have a left child
} else if (currentNode.right.left === null) {
currentNode.right.left = currentNode.left;
if(parentNode === null) {
this.root = currentNode.right;
} else {
//if parent > current, make right child of the left the parent
if(currentNode.value < parentNode.value) {
parentNode.left = currentNode.right;
//if parent < current, make right child a right child of the parent
} else if (currentNode.value > parentNode.value) {
parentNode.right = currentNode.right;
}
}
//Option 3: Right child that has a left child
} else {
//find the Right child's left most child
let leftmost = currentNode.right.left;
let leftmostParent = currentNode.right;
while(leftmost.left !== null) {
leftmostParent = leftmost;
leftmost = leftmost.left;
}
//Parent's left subtree is now leftmost's right subtree
leftmostParent.left = leftmost.right;
leftmost.left = currentNode.left;
leftmost.right = currentNode.right;
if(parentNode === null) {
this.root = leftmost;
} else {
if(currentNode.value < parentNode.value) {
parentNode.left = leftmost;
} else if(currentNode.value > parentNode.value) {
parentNode.right = leftmost;
}
}
}
return true;
}
}
}
}
function traverse(node){
const tree = {node:node.value}
tree.left = node.left === null ? null : traverse(node.left)
tree.right = node.right === null ? null : traverse(node.right)
return tree
}
const tree = new BinarySearchTree();
tree.insert(9)
tree.insert(4)
tree.insert(6)
tree.insert(20)
tree.insert(170)
tree.insert(15)
tree.insert(1)
//console.log(JSON.stringify(traverse(tree.root)))
console.log(tree.lookup(20))
console.log(tree.remove(170))