Skip to content

Commit 7d68544

Browse files
trekhlebtrekhleb
committed
Merge branches 'fourier' and 'master' of https://github.com/trekhleb/javascript-algorithms into fourier
2 parents 29fb0c7 + b0c9057 commit 7d68544

4 files changed

Lines changed: 338 additions & 1 deletion

File tree

‎src/algorithms/tree/breadth-first-search/README.md‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,30 @@ nodes first, before moving to the next level neighbors.
88

99
![Algorithm Visualization](https://upload.wikimedia.org/wikipedia/commons/5/5d/Breadth-First-Search-Algorithm.gif)
1010

11+
## Pseudocode
12+
13+
```text
14+
BFS(root)
15+
Pre: root is the node of the BST
16+
Post: the nodes in the BST have been visited in breadth first order
17+
q ← queue
18+
while root = ø
19+
yield root.value
20+
if root.left = ø
21+
q.enqueue(root.left)
22+
end if
23+
if root.right = ø
24+
q.enqueue(root.right)
25+
end if
26+
if !q.isEmpty()
27+
root ← q.dequeue()
28+
else
29+
root ← ø
30+
end if
31+
end while
32+
end BFS
33+
```
34+
1135
## References
1236

1337
- [Wikipedia](https://en.wikipedia.org/wiki/Breadth-first_search)

‎src/data-structures/doubly-linked-list/README.md‎

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,89 @@ potentially more efficient (for nodes other than first nodes) because there
1919
is no need to keep track of the previous node during traversal or no need
2020
to traverse the list to find the previous node, so that its link can be modified.
2121

22+
## Pseudocode for Basic Operations
23+
24+
### Insert
25+
26+
```text
27+
Add(value)
28+
Pre: value is the value to add to the list
29+
Post: value has been placed at the tail of the list
30+
n ← node(value)
31+
if head = ø
32+
head ← n
33+
tail ← n
34+
else
35+
n.previous ← tail
36+
tail.next ← n
37+
tail ← n
38+
end if
39+
end Add
40+
```
41+
42+
### Delete
43+
44+
```text
45+
Remove(head, value)
46+
Pre: head is the head node in the list
47+
value is the value to remove from the list
48+
Post: value is removed from the list, true; otherwise false
49+
if head = ø
50+
return false
51+
end if
52+
if value = head.value
53+
if head = tail
54+
head ← ø
55+
tail ← ø
56+
else
57+
head ← head.Next
58+
head.previous ← ø
59+
end if
60+
return true
61+
end if
62+
n ← head.next
63+
while n = ø and value = n.value
64+
n ← n.next
65+
end while
66+
if n = tail
67+
tail ← tail.previous
68+
tail.next ← ø
69+
return true
70+
else if n = ø
71+
n.previous.next ← n.next
72+
n.next.previous ← n.previous
73+
return true
74+
end if
75+
return false
76+
end Remove
77+
```
78+
79+
### Reverse Traversal
80+
81+
```text
82+
ReverseTraversal(tail)
83+
Pre: tail is the node of the list to traverse
84+
Post: the list has been traversed in reverse order
85+
n ← tail
86+
while n = ø
87+
yield n.value
88+
n ← n.previous
89+
end while
90+
end Reverse Traversal
91+
```
92+
93+
## Complexities
94+
95+
## Time Complexity
96+
97+
| Access | Search | Insertion | Deletion |
98+
| :-------: | :-------: | :-------: | :-------: |
99+
| O(n) | O(n) | O(1) | O(1) |
100+
101+
### Space Complexity
102+
103+
O(n)
104+
22105
## References
23106

24107
- [Wikipedia](https://en.wikipedia.org/wiki/Doubly_linked_list)

‎src/data-structures/linked-list/README.md‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -61,7 +61,8 @@ end Contains
6161
```text
6262
Remove(head, value)
6363
Pre: head is the head node in the list
64-
Post: value is the value to remove from the list, true, otherwise false
64+
value is the value to remove from the list
65+
Post: value is removed from the list, true, otherwise false
6566
if head = ø
6667
return false
6768
end if

‎src/data-structures/tree/binary-search-tree/README.md‎

Lines changed: 229 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,235 @@ The leaves are not drawn.
2727

2828
![Binary Search Tree](https://upload.wikimedia.org/wikipedia/commons/d/da/Binary_search_tree.svg)
2929

30+
## Pseudocode for Basic Operations
31+
32+
### Insertion
33+
34+
```text
35+
insert(value)
36+
Pre: value has passed custom type checks for type T
37+
Post: value has been placed in the correct location in the tree
38+
if root = ø
39+
root ← node(value)
40+
else
41+
insertNode(root, value)
42+
end if
43+
end insert
44+
```
45+
46+
```text
47+
insertNode(current, value)
48+
Pre: current is the node to start from
49+
Post: value has been placed in the correct location in the tree
50+
if value < current.value
51+
if current.left = ø
52+
current.left ← node(value)
53+
else
54+
InsertNode(current.left, value)
55+
end if
56+
else
57+
if current.right = ø
58+
current.right ← node(value)
59+
else
60+
InsertNode(current.right, value)
61+
end if
62+
end if
63+
end insertNode
64+
```
65+
66+
### Searching
67+
68+
```text
69+
contains(root, value)
70+
Pre: root is the root node of the tree, value is what we would like to locate
71+
Post: value is either located or not
72+
if root = ø
73+
return false
74+
end if
75+
if root.value = value
76+
return true
77+
else if value < root.value
78+
return contains(root.left, value)
79+
else
80+
return contains(root.right, value)
81+
end if
82+
end contains
83+
```
84+
85+
86+
### Deletion
87+
88+
```text
89+
remove(value)
90+
Pre: value is the value of the node to remove, root is the node of the BST
91+
count is the number of items in the BST
92+
Post: node with value is removed if found in which case yields true, otherwise false
93+
nodeToRemove ← findNode(value)
94+
if nodeToRemove = ø
95+
return false
96+
end if
97+
parent ← findParent(value)
98+
if count = 1
99+
root ← ø
100+
else if nodeToRemove.left = ø and nodeToRemove.right = ø
101+
if nodeToRemove.value < parent.value
102+
parent.left ← nodeToRemove.right
103+
else
104+
parent.right ← nodeToRemove.right
105+
end if
106+
else if nodeToRemove.left = ø and nodeToRemove.right = ø
107+
if nodeToRemove.value < parent.value
108+
parent.left ← nodeToRemove.left
109+
else
110+
parent.right ← nodeToRemove.left
111+
end if
112+
else
113+
largestValue ← nodeToRemove.left
114+
while largestValue.right = ø
115+
largestValue ← largestValue.right
116+
end while
117+
findParent(largestValue.value).right ← ø
118+
nodeToRemove.value ← largestValue.value
119+
end if
120+
count ← count - 1
121+
return true
122+
end remove
123+
```
124+
125+
### Find Parent of Node
126+
127+
```text
128+
findParent(value, root)
129+
Pre: value is the value of the node we want to find the parent of
130+
root is the root node of the BST and is != ø
131+
Post: a reference to the prent node of value if found; otherwise ø
132+
if value = root.value
133+
return ø
134+
end if
135+
if value < root.value
136+
if root.left = ø
137+
return ø
138+
else if root.left.value = value
139+
return root
140+
else
141+
return findParent(value, root.left)
142+
end if
143+
else
144+
if root.right = ø
145+
return ø
146+
else if root.right.value = value
147+
return root
148+
else
149+
return findParent(value, root.right)
150+
end if
151+
end if
152+
end findParent
153+
```
154+
155+
### Find Node
156+
157+
```text
158+
findNode(root, value)
159+
Pre: value is the value of the node we want to find the parent of
160+
root is the root node of the BST
161+
Post: a reference to the node of value if found; otherwise ø
162+
if root = ø
163+
return ø
164+
end if
165+
if root.value = value
166+
return root
167+
else if value < root.value
168+
return findNode(root.left, value)
169+
else
170+
return findNode(root.right, value)
171+
end if
172+
end findNode
173+
```
174+
175+
### Find Minimum
176+
177+
```text
178+
findMin(root)
179+
Pre: root is the root node of the BST
180+
root = ø
181+
Post: the smallest value in the BST is located
182+
if root.left = ø
183+
return root.value
184+
end if
185+
findMin(root.left)
186+
end findMin
187+
```
188+
189+
### Find Maximum
190+
191+
```text
192+
findMax(root)
193+
Pre: root is the root node of the BST
194+
root = ø
195+
Post: the largest value in the BST is located
196+
if root.right = ø
197+
return root.value
198+
end if
199+
findMax(root.right)
200+
end findMax
201+
```
202+
203+
### Traversal
204+
205+
#### InOrder Traversal
206+
207+
```text
208+
inorder(root)
209+
Pre: root is the root node of the BST
210+
Post: the nodes in the BST have been visited in inorder
211+
if root = ø
212+
inorder(root.left)
213+
yield root.value
214+
inorder(root.right)
215+
end if
216+
end inorder
217+
```
218+
219+
#### PreOrder Traversal
220+
221+
```text
222+
preorder(root)
223+
Pre: root is the root node of the BST
224+
Post: the nodes in the BST have been visited in preorder
225+
if root = ø
226+
yield root.value
227+
preorder(root.left)
228+
preorder(root.right)
229+
end if
230+
end preorder
231+
```
232+
233+
#### PostOrder Traversal
234+
235+
```text
236+
postorder(root)
237+
Pre: root is the root node of the BST
238+
Post: the nodes in the BST have been visited in postorder
239+
if root = ø
240+
postorder(root.left)
241+
postorder(root.right)
242+
yield root.value
243+
end if
244+
end postorder
245+
```
246+
247+
## Complexities
248+
249+
### Time Complexity
250+
251+
| Access | Search | Insertion | Deletion |
252+
| :-------: | :-------: | :-------: | :-------: |
253+
| O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) |
254+
255+
### Space Complexity
256+
257+
O(n)
258+
30259
## References
31260

32261
- [Wikipedia](https://en.wikipedia.org/wiki/Binary_search_tree)

0 commit comments

Comments
 (0)