Optimizing Tree-like Data Structures

flat-tree.ts

import { performance } from "perf_hooks";

type TreeNode = {
  id: number;
  name: string;
  parentId: number | null;
  children: number[];
};

type NormalizedTree = {
  nodes: { [id: number]: TreeNode };
  rootIds: number[];
};

function createNormalizedTree(n: number): NormalizedTree {
  const tree: NormalizedTree = { nodes: {}, rootIds: [1] };

  for (let i = 1; i <= n; i++) {
    const parentId = i === 1 ? null : Math.floor(i / 2);
    tree.nodes[i] = {
      id: i,
      name: `Node ${i}`,
      parentId: parentId,
      children: [],
    };
    if (parentId !== null) {
      tree.nodes[parentId].children.push(i);
    }
  }

  return tree;
}

function dfsTraversal(
  tree: NormalizedTree,
  nodeId: number,
  callback: (node: TreeNode) => void
): void {
  const node = tree.nodes[nodeId];
  if (!node) return;

  callback(node);

  node.children.forEach((childId) => dfsTraversal(tree, childId, callback));
}

function bfsTraversal(
  tree: NormalizedTree,
  rootId: number,
  callback: (node: TreeNode) => void
): void {
  const queue: number[] = [rootId];

  while (queue.length > 0) {
    const nodeId = queue.shift()!;
    const node = tree.nodes[nodeId];
    if (!node) continue;

    callback(node);

    queue.push(...node.children);
  }
}

function getAncestors(tree: NormalizedTree, nodeId: number): TreeNode[] {
  const ancestors: TreeNode[] = [];
  let current = tree.nodes[nodeId];

  while (current && current.parentId !== null) {
    const parent = tree.nodes[current.parentId];
    if (!parent) break;
    ancestors.push(parent);
    current = parent;
  }

  return ancestors;
}

function getDescendants(tree: NormalizedTree, nodeId: number): TreeNode[] {
  const descendants: TreeNode[] = [];
  dfsTraversal(tree, nodeId, (node) => {
    if (node.id !== nodeId) descendants.push(node); // Loại trừ node gốc
  });
  return descendants;
}

function countNodes(tree: NormalizedTree, nodeId: number): number {
  let count = 0;
  dfsTraversal(tree, nodeId, () => count++);
  return count;
}

function isDescendant(
  tree: NormalizedTree,
  ancestorId: number,
  nodeId: number
): boolean {
  let found = false;
  dfsTraversal(tree, ancestorId, (node) => {
    if (node.id === nodeId) found = true;
  });
  return found;
}

function findPath(
  tree: NormalizedTree,
  fromId: number,
  toId: number
): TreeNode[] {
  const path: TreeNode[] = [];
  let current: TreeNode | null = tree.nodes[toId];

  while (current) {
    path.unshift(current);
    if (current.id === fromId) break;
    current = current.parentId ? tree.nodes[current.parentId] : null;
  }

  return current ? path : [];
}

function deleteSubtree(tree: NormalizedTree, nodeId: number): void {
  const parent = tree.nodes[nodeId]?.parentId;

  if (parent) {
    tree.nodes[parent].children = tree.nodes[parent].children.filter(
      (id) => id !== nodeId
    );
  }

  const deleteNodeAndDescendants = (id: number) => {
    const node = tree.nodes[id];
    if (!node) return;

    node.children.forEach(deleteNodeAndDescendants);
    delete tree.nodes[id];
  };

  deleteNodeAndDescendants(nodeId);
}

function getNodesAtLevel(
  tree: NormalizedTree,
  rootId: number,
  level: number
): TreeNode[] {
  const result: TreeNode[] = [];
  const bfs = (id: number, currentLevel: number) => {
    const node = tree.nodes[id];
    if (!node) return;
    if (currentLevel === level) result.push(node);

    node.children.forEach((childId) => bfs(childId, currentLevel + 1));
  };

  bfs(rootId, 0);
  return result;
}

function measurePerformance(action: () => void, actionName: string): void {
  const start = performance.now();
  action();
  const end = performance.now();
  console.log(`${actionName}: ${(end - start).toFixed(2)} ms`);
}

function runTests() {
  const nodeCounts = [1000, 10000, 100000];
  for (const count of nodeCounts) {
    console.log(`\nTesting with ${count} nodes...`);
    const tree = createNormalizedTree(count);

    measurePerformance(() => dfsTraversal(tree, 1, () => {}), "DFS Traversal");
    measurePerformance(() => bfsTraversal(tree, 1, () => {}), "BFS Traversal");
    measurePerformance(
      () => getAncestors(tree, Math.floor(count / 2)),
      "Get Ancestors"
    );
    measurePerformance(() => getDescendants(tree, 1), "Get Descendants");
    measurePerformance(() => countNodes(tree, 1), "Count Nodes");
    measurePerformance(() => isDescendant(tree, 1, count), "Check Descendant");
    measurePerformance(
      () => findPath(tree, 1, Math.floor(count / 2)),
      "Find Path"
    );
    measurePerformance(
      () => deleteSubtree(tree, Math.floor(count / 2)),
      "Delete Subtree"
    );
    measurePerformance(
      () => getNodesAtLevel(tree, 1, 3),
      "Get Nodes At Level 3"
    );
  }
}

runTests();