Skip to content

Commit 2db7ce3

Browse files
BIO2CSBIO2CS
committed
Adding Sorting and BST
0 parents  commit 2db7ce3

File tree

10 files changed

+494
-0
lines changed

10 files changed

+494
-0
lines changed

‎BinarySearchTree/BST.java‎

Lines changed: 173 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,173 @@
1+
package BinarySearchTree;
2+
3+
import java.util.ArrayList;
4+
import java.util.LinkedList;
5+
import java.util.List;
6+
import java.util.Queue;
7+
8+
public class BST {
9+
TreeNode root;
10+
11+
public BST() {
12+
}
13+
14+
public void Insert(int key) {
15+
TreeNode node = new TreeNode(key);
16+
TreeNode pre = null, runner = root;
17+
while (runner != null) {
18+
pre = runner;
19+
if (runner.key == key) {
20+
return;
21+
}
22+
if (key < runner.key) {
23+
runner = runner.left;
24+
}
25+
else {
26+
runner = runner.right;
27+
}
28+
}
29+
node.parent = pre;
30+
if (pre == null) {
31+
root = node;
32+
}
33+
else if (pre.key < key){
34+
pre.right = node;
35+
}
36+
else {
37+
pre.left = node;
38+
}
39+
}
40+
41+
public TreeNode search(int key) {
42+
TreeNode runner = root;
43+
while (runner != null) {
44+
if (key == runner.key) {
45+
return runner;
46+
}
47+
if (key < runner.key) {
48+
runner = runner.left;
49+
}
50+
else {
51+
runner = runner.right;
52+
}
53+
}
54+
return null;
55+
}
56+
57+
public TreeNode getMinNode(TreeNode x) {
58+
if (x == null) {
59+
return null;
60+
}
61+
TreeNode runner = x;
62+
while (runner.left != null) {
63+
runner = runner.left;
64+
}
65+
return runner;
66+
}
67+
68+
public TreeNode getMaxNode(TreeNode x) {
69+
if (x == null) {
70+
return null;
71+
}
72+
TreeNode runner = x;
73+
while (runner.right != null) {
74+
runner = runner.right;
75+
}
76+
return runner;
77+
}
78+
79+
public TreeNode getSuccessor(TreeNode x) {
80+
if (x == null) return null;
81+
if (x.right != null) {
82+
return getMinNode(x.right);
83+
}
84+
TreeNode p = x.parent;
85+
while (p != null && x == p.right) {
86+
x = p;
87+
p = p.parent;
88+
}
89+
return p;
90+
}
91+
92+
public TreeNode getPredecessor(TreeNode x) {
93+
if (x == null) return null;
94+
if (x.left != null) {
95+
return getMaxNode(x.left);
96+
}
97+
TreeNode p = x.parent;
98+
while (p != null && x == p.left) {
99+
x = p;
100+
p = p.parent;
101+
}
102+
return p;
103+
}
104+
105+
public void delete(TreeNode x) {
106+
if (x == null) return;
107+
TreeNode splicedNode = null;
108+
//case 1: x is leaf node;
109+
if (x.left == null && x.right == null) {
110+
splicedNode = x;
111+
}
112+
//case 2: x has only one child;
113+
else if (x.left == null || x.right == null) {
114+
splicedNode = x;
115+
}
116+
//case 3: x has two children;
117+
else {
118+
splicedNode = getSuccessor(x);
119+
}
120+
TreeNode childOfSplicedNode = null;
121+
if (splicedNode.left != null) {
122+
childOfSplicedNode = splicedNode.left;
123+
}
124+
else {
125+
childOfSplicedNode = splicedNode.right;
126+
}
127+
if (childOfSplicedNode != null) {
128+
childOfSplicedNode.parent = splicedNode.parent;
129+
}
130+
if (splicedNode.parent == null) {
131+
root = childOfSplicedNode;
132+
}
133+
else {
134+
if (splicedNode == splicedNode.parent.left) {
135+
splicedNode.parent.left = childOfSplicedNode;
136+
}
137+
else {
138+
splicedNode.parent.right = childOfSplicedNode;
139+
}
140+
}
141+
if (splicedNode != x) {
142+
x.key = splicedNode.key;
143+
}
144+
}
145+
146+
public void printTree() {
147+
Queue<TreeNode> queue = new LinkedList<TreeNode>();
148+
queue.offer(root);
149+
int parent = 1, children = 0;
150+
List<Integer> list = new ArrayList<Integer>();
151+
while (!queue.isEmpty()) {
152+
TreeNode front = queue.poll();
153+
list.add(front.key);
154+
if (front.left != null) {
155+
queue.offer(front.left);
156+
children++;
157+
}
158+
if (front.right != null) {
159+
queue.offer(front.right);
160+
children++;
161+
}
162+
if (--parent == 0) {
163+
for (Integer d : list) {
164+
System.out.print(d + " ");
165+
}
166+
System.out.println();
167+
list = new ArrayList<Integer>();
168+
parent = children;
169+
children = 0;
170+
}
171+
}
172+
}
173+
}

‎BinarySearchTree/TestClient.java‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package BinarySearchTree;
2+
3+
public class TestClient {
4+
5+
public static void main(String[] args) {
6+
//using example on page 263 in CLRS
7+
BST bst = new BST();
8+
bst.Insert(15);
9+
bst.Insert(5);
10+
bst.Insert(3);
11+
bst.Insert(12);
12+
bst.Insert(10);
13+
bst.Insert(13);
14+
bst.Insert(6);
15+
bst.Insert(7);
16+
bst.Insert(16);
17+
bst.Insert(20);
18+
bst.Insert(18);
19+
bst.Insert(23);
20+
// bst.printTree();
21+
22+
TreeNode key = bst.search(15);
23+
TreeNode next = bst.getPredecessor(key);
24+
System.out.println(next.key);
25+
}
26+
}

‎BinarySearchTree/TreeNode.java‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
package BinarySearchTree;
2+
3+
public class TreeNode {
4+
5+
int key;
6+
TreeNode left, right, parent;
7+
8+
public TreeNode(int d) {
9+
key = d;
10+
left = right = parent = null;
11+
}
12+
}

‎Sorting/BubbleSort.java‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package Sorting;
2+
3+
public class BubbleSort {
4+
public static void bubbleSort(int[] array) {
5+
for (int i = array.length - 1; i > 0; i--) {
6+
for (int j = 0; j < i; j++) {
7+
if (array[j] > array[j + 1]) {
8+
swap (array, j, j + 1);
9+
}
10+
}
11+
}
12+
}
13+
14+
private static void swap(int[] array, int i, int j) {
15+
int temp = array[i];
16+
array[i] = array[j];
17+
array[j] = temp;
18+
}
19+
20+
public static void main(String[] args) {
21+
int[] numbers = {3, 1, 4, 9, -2, 5};
22+
for (int n : numbers) {
23+
System.out.print(n + " ");
24+
}
25+
bubbleSort(numbers);
26+
System.out.println();
27+
for (int n : numbers) {
28+
System.out.print(n + " ");
29+
}
30+
}
31+
}

‎Sorting/CountingSort.java‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package Sorting;
2+
3+
public class CountingSort {
4+
5+
public static void countSort(int[] array, int k) {
6+
int n = array.length;
7+
int[] temp = new int[n];
8+
int[] counts = new int[k + 1];
9+
for (int i = 0; i < n; i++) {
10+
counts[array[i]]++;
11+
}
12+
for (int i = 1; i <= k; i++) {
13+
counts[i] += counts[i - 1];
14+
}
15+
for (int i = n - 1; i >= 0; i--) {
16+
temp[counts[array[i]] - 1] = array[i];
17+
counts[array[i]]--;
18+
}
19+
for (int i = 0; i < n; i++) {
20+
array[i] = temp[i];
21+
}
22+
}
23+
24+
public static void main(String[] args) {
25+
int[] numbers = {3, 6, 4, 5, 5, 9, 1};
26+
for (int n : numbers) {
27+
System.out.print(n + " ");
28+
}
29+
countSort(numbers, 9);
30+
System.out.println();
31+
for (int n : numbers) {
32+
System.out.print(n + " ");
33+
}
34+
}
35+
}

‎Sorting/HeapSort.java‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package Sorting;
2+
3+
public class HeapSort {
4+
5+
public static void heapSort(int[] A) {
6+
MaxHeap h = new MaxHeap(A);
7+
h.buildMaxHeap();
8+
for (int i = h.arraySize - 1; i > 0; i--) {
9+
swap(h.array, 0, i);
10+
h.heapSize--;
11+
h.maxHeapify(0);
12+
}
13+
}
14+
15+
private static void swap(int[] array, int i, int j) {
16+
int temp = array[i];
17+
array[i] = array[j];
18+
array[j] = temp;
19+
}
20+
21+
public static void main(String[] args) {
22+
int[] numbers = {3, 1, 4, 9, -2, 5, 10, 2};
23+
for (int n : numbers) {
24+
System.out.print(n + " ");
25+
}
26+
heapSort(numbers);
27+
System.out.println();
28+
for (int n : numbers) {
29+
System.out.print(n + " ");
30+
}
31+
32+
// System.out.println("\nMAX " + Integer.MAX_VALUE);
33+
}
34+
}

‎Sorting/InsertionSort.java‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
2+
package Sorting;
3+
4+
public class InsertionSort {
5+
6+
public static void insertionSort(int[] array) {
7+
for (int i = 1; i < array.length; i++) {
8+
int curr = array[i];
9+
int j = i - 1;
10+
while (j >= 0 && array[j] > curr) {
11+
array[j + 1] = array[j];
12+
j--;
13+
}
14+
array[j + 1] = curr;
15+
}
16+
}
17+
18+
public static void main(String[] args) {
19+
int[] numbers = {3, 1, 4, 9, -2, 5};
20+
for (int n : numbers) {
21+
System.out.print(n + " ");
22+
}
23+
insertionSort(numbers);
24+
System.out.println();
25+
for (int n : numbers) {
26+
System.out.print(n + " ");
27+
}
28+
}
29+
}

‎Sorting/MaxHeap.java‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package Sorting;
2+
3+
public class MaxHeap {
4+
public int[] array;
5+
public int arraySize = 0;
6+
public int heapSize = 0;
7+
8+
public MaxHeap(int[] A) {
9+
int n = A.length;
10+
array = A;
11+
arraySize = heapSize = n;
12+
}
13+
14+
public void buildMaxHeap() {
15+
for (int i = heapSize / 2 - 1; i >= 0; i--) {
16+
maxHeapify(i);
17+
}
18+
}
19+
20+
public int getParentIndex(int i) {
21+
return (i - 1) / 2;
22+
}
23+
24+
public int getLeftChildIndex(int i) {
25+
return 2 * i + 1;
26+
}
27+
28+
public int getRightChildIndex(int i) {
29+
return 2 * i + 2;
30+
}
31+
32+
public void maxHeapify(int i) {
33+
int left = getLeftChildIndex(i);
34+
int right = getRightChildIndex(i);
35+
int largest = i;
36+
if (left < heapSize && array[i] < array[left]) {
37+
largest = left;
38+
}
39+
if (right < heapSize && array[largest] < array[right]) {
40+
largest = right;
41+
}
42+
if (largest != i) {
43+
int temp = array[largest];
44+
array[largest] = array[i];
45+
array[i] = temp;
46+
maxHeapify(largest);
47+
}
48+
}
49+
}

0 commit comments

Comments
 (0)