Java Implementations: Dijkstra, Balanced BST, and Hash Table

Java Implementations of Dijkstra's Algorithm, a Balanced Binary Tree, and a Hash Table

Dijkstra's Shortest Path Algorithm

The following class implements Dijkstra's algorithm to compute the shortest distances from a source node to all other nodes in a weighted graph.

import java.util.*;

class Dijkstra {
static class Edge {
int dst, weight;

Edge(int dst, int weight) {
this.dst = dst;
this.weight = weight;
}
}

public static Map<Integer, Integer> shortestPath(int source, Map<Integer, List<Edge>> graph) {
Map<Integer, Integer> distances = new HashMap<>();
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));

for (int node : graph.keySet()) {
distances.put(node, Integer.MAX_VALUE);
}
distances.put(source, 0);
pq.offer(new int[]{source, 0});

while (!pq.isEmpty()) {
int[] current = pq.poll();
int node = current[0], dist = current[1];

if (dist > distances.get(node)) continue;

for (Edge edge : graph.get(node)) {
int newDist = dist + edge.weight;
if (newDist < distances.get(edge.dst)) {
distances.put(edge.dst, newDist);
pq.offer(new int[]{edge.dst, newDist});
}
}
}

return distances;
}
}

Balanced Binary Search Tree (AVL Tree)

The following class implements a self-balancing AVL tree supporting insertion and deletion while maintaining height balance through rotations.

class BalancedBinaryTree {
class Node {
int value, height;
Node left, right;

Node(int value) {
this.value = value;
this.height = 1;
}
}

private Node root;

public void insert(int value) {
root = insertNode(root, value);
}

private Node insertNode(Node node, int value) {
if (node == null) return new Node(value);

if (value < node.value) {
node.left = insertNode(node.left, value);
} else if (value > node.value) {
node.right = insertNode(node.right, value);
} else {
return node; // Duplicate values are not allowed
}

updateHeight(node);
return balance(node);
}

public void delete(int value) {
root = deleteNode(root, value);
}

private Node deleteNode(Node node, int value) {
if (node == null) return null;

if (value < node.value) {
node.left = deleteNode(node.left, value);
} else if (value > node.value) {
node.right = deleteNode(node.right, value);
} else {
if (node.left == null || node.right == null) {
return (node.left != null) ? node.left : node.right;
} else {
Node successor = getMin(node.right);
node.value = successor.value;
node.right = deleteNode(node.right, successor.value);
}
}

updateHeight(node);
return balance(node);
}

private Node getMin(Node node) {
while (node.left != null) node = node.left;
return node;
}

private void updateHeight(Node node) {
node.height = 1 + Math.max(height(node.left), height(node.right));
}

private int height(Node node) {
return (node == null) ? 0 : node.height;
}

private int getBalanceFactor(Node node) {
return (node == null) ? 0 : height(node.left) - height(node.right);
}

private Node balance(Node node) {
int balanceFactor = getBalanceFactor(node);

if (balanceFactor > 1) {
if (getBalanceFactor(node.left) < 0) {
node.left = rotateLeft(node.left);
}
return rotateRight(node);
}

if (balanceFactor < -1) {
if (getBalanceFactor(node.right) > 0) {
node.right = rotateRight(node.right);
}
return rotateLeft(node);
}

return node;
}

private Node rotateRight(Node y) {
Node x = y.left;
Node t = x.right;

x.right = y;
y.left = t;

updateHeight(y);
updateHeight(x);

return x;
}

private Node rotateLeft(Node x) {
Node y = x.right;
Node t = y.left;

y.left = x;
x.right = t;

updateHeight(x);
updateHeight(y);

return y;
}
}

Simple Hash Table with Separate Chaining

The following class implements a hash table using separate chaining with linked lists to resolve collisions.

import java.util.LinkedList;

class SimpleHashTable {
private static final int SIZE = 10;
private LinkedList<Entry>[] table;

public SimpleHashTable() {
table = new LinkedList[SIZE];
for (int i = 0; i < SIZE; i++) {
table[i] = new LinkedList<>();
}
}

private int hash(String key) {
return Math.abs(key.hashCode()) % SIZE;
}

public void put(String key, String value) {
int index = hash(key);
for (Entry entry : table[index]) {
if (entry.key.equals(key)) {
entry.value = value; // Update value if key exists
return;
}
}
table[index].add(new Entry(key, value));
}

public String get(String key) {
int index = hash(key);
for (Entry entry : table[index]) {
if (entry.key.equals(key)) {
return entry.value;
}
}
return null; // Key not found
}

public void remove(String key) {
int index = hash(key);
table[index].removeIf(entry -> entry.key.equals(key));
}

static class Entry {
String key, value;

Entry(String key, String value) {
this.key = key;
this.value = value;
}
}
}