Data Structure Algorithms: Hashtables, Lists, Trees, and Graphs

Posted on May 12, 2024 in Computers

Hashtable Compression: Removing Duplicates

public int compress() {
    Set<T> in = new HashSet<>();
    int count = 0;
    for (int i = 0; i < table.size(); i++) {
        T current = table.get(i);
        if (current != null) {
            if (in.contains(current)) {
                table.set(i, null);
                count++;
                size--;
            } else {
                in.add(current);
            }
        }
    }
    return count;
}

List Reversal

public void reverse() {
    if (size <= 1) return;
    last = last.next;
    if (size == 2) return;
    Node prev = last;
    Node current = prev.next;
    Node aux = current.next;
    for (int i = 0; i < size; i++) {
        current.next = prev;
        prev = current;
        current = aux;
        aux = aux.next;
    }
}

Recursive Add to Binary Tree

private BinaryNode add(BinaryNode r, E item) {
    if (r == null) {
        r = new BinaryNode(item);
        itemToReturn = true;
    } else if (item.compareTo(r.data) < 0) {
        r.left = add(r.left, item);
        if (!itemToReturn)
            r.leftchildren++;
    } else if (item.compareTo(r.data) > 0) {
        r.right = add(r.right, item);
        if (!itemToReturn)
            r.rightchildren++;
    } else {
        itemToReturn = false;
    }
    return r;
}

Binary Tree Subtree Check

If the tree is null, it will return true. There are no nodes that contain null.

public boolean isSubtree(BinaryTree<T> other) {
    if (other == null || other.root == null)
        return true;
    return isSubTree(root, other.root);
}
private boolean isSubTree(BinaryNode root, BinaryNode other) {
    if (areEqual(root, other))
        return true;
    if (root == null)
        return false;
    return isSubTree(root.left, other) || isSubTree(root.right, other);
}
private boolean areEqual(BinaryNode one, BinaryNode another) {
    if (one == another)
        return true;
    if (one == null || another == null)
        return false;
    if (!one.data.equals(another.data))
        return false;
    return areEqual(one.left, another.left) && areEqual(one.right, another.right);
}

MinHeap Fast Search

public int minHeapFastSearch(T k) {
    if (array.size() == 0) return -1;
    return minHeapFastSearch(k, 0);
}
private int minHeapFastSearch(T k, int p) {
    int res = -1;
    if (compare(array.get(p), k) == 0) 
        res = p;
    else if (compare(array.get(p), k) > 0) 
        res = -1;
    else {
        int left = 2 * p + 1;
        if (left < array.size()) {
            res = minHeapFastSearch(k, left);
            if (res == -1 && left + 1 < array.size())
                res = minHeapFastSearch(k, left + 1);
        } else res = -1;
    }
    return res;
}

Graph: Finding Unreachable Nodes

Extract a list with the indices of the nodes that are NOT reachable from the start node (GRAPHS). Breadth-first search is used.

public List<Integer> notReachable(int start) {
    List<Integer> res = new ArrayList<Integer>();
    Queue<Integer> qu = new LinkedList<Integer>();
    if (start < 0 || start >= nodes.size()) return res;
    if (nodes.get(start) == null) return res;
    int[] parent = new int[nodes.size()];
    for (int i = 0; i < parent.length; i++)
        parent[i] = -1;
    parent[start] = start;
    qu.add(start);
    while (!qu.isEmpty()) {
        int current = qu.remove();
        for (EDEdge<W> edge : nodes.get(current).lEdges) {
            int neighbor = edge.getTarget();
            if (parent[neighbor] == -1) {
                parent[neighbor] = current;
                qu.add(neighbor);
            }
        }
    }
    for (int i = 0; i < parent.length; i++) {
        if (parent[i] == -1 && nodes.get(i) != null)
            res.add(i);
    }
    return res;
}

Graph: Finding Nodes with Greater Degree of Separation

Returns the set of people with a greater degree of separation from the start node. If start.value is not valid, returns null.

public Set<T> greaterDegreeSep(int start) {
    if (start < 0 || start > nodes.size()) return null;
    Set<T> s = new HashSet<T>();
    int[] dist = distanceToAll(start);
    int max = dist[0];
    for (int i = 1; i < dist.length; i++)
        if (dist[i] > max) max = dist[i];
    if (max > 0) {
        for (int i = 0; i < dist.length; i++) {
            if (dist[i] == max)
                s.add(nodes.get(i).data);
        }
        return s;
    }
    return null; // Add this line to handle the case when max <= 0
}
public int[] distanceToAll(int start) {
    Queue<Integer> qu = new LinkedList<Integer>();
    int[] parent = new int[nodes.size()];
    for (int i = 0; i < parent.length; i++)
        parent[i] = -1;
    parent[start] = 0;
    while (!qu.isEmpty()) {
        int actual = qu.remove();
        for (EDEdge<W> e : nodes.get(actual).lEdges) {
            int target = e.getTarget();
            if (parent[target] == -1) {
                parent[target] = parent[actual] + 1;
                qu.add(target);
            }
        }
    }
    return parent; // Change 'distancia' to 'parent'
}

Graph: Cycle Detection

public boolean containsCycles() {
    boolean[] visited = new boolean[nodes.size()];
    boolean[] branch = new boolean[nodes.size()];
    for (int start = 0; start < nodes.size(); start++) {
        if (!visited[start]) {
            boolean rt = containsCycles(start, branch, visited);
            if (rt) return true;
        }
    }
    return false;
}
private boolean containsCycles(int current, boolean[] branch, boolean[] visited) {
    visited[current] = true;
    branch[current] = true;
    for (EDEdge<W> edge : nodes.get(current).lEdges) {
        int target = edge.getTarget();
        if (branch[target] == true) {
            if ((!isDirected() && target != current) || isDirected())
                return true;
        } else return containsCycles(target, branch, visited);
    }
    branch[current] = false;
    return false;
}