Trie Data Structure

Trie Data Structure

A Trie, also known as a prefix tree or digital tree, is a specialized tree used to store associative data structures. It is commonly used for storing strings or sequences where it can efficiently support operations like insertion, deletion, and prefix search.

Key Concepts

• Nodes: Each node represents a character of the stored strings.
• Edges: The edges between nodes represent the transitions from one character to the next.
• Root: The root node represents the starting point of the Trie and does not store any character.

Operations

1. Insertion: Add a new string to the Trie.
2. Search: Check if a string exists in the Trie.
3. Prefix Search: Find all strings that share a common prefix.
4. Deletion: Remove a string from the Trie.

Code Implementation

Here's a basic implementation of a Trie in JavaScript:

class TrieNode {
  children = {};
  isEnd = false;
}

class Trie {
  root = new TrieNode();

  // Inserts a word into the trie
  insert = (word) => {
    let node = this.root;

    for (const char of word) {
      node = node.children[char] ??= new TrieNode();
    }
    node.isEnd = true; // Mark the word as complete
  };

  search = (word) => {
    let node = this.root;

    for (const char of word) {
      if (!node.children[char]) return false; // If the character doesn't exist, return false
      node = node.children[char];
    }
    return node.isEnd; // Check if this is the end of a complete word
  };

  startsWith = (prefix) => {
    let node = this.root;

    for (const char of prefix) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return true;
  };

  remove = (word) => {
    let root = this.root;
    const path = [];

    // Search and track path
    for (const c of word) {
      path.push([root, c]);
      if (!root.children[c]) return false;
      root = root.children[c];
    }

    // Check if word exists
    if (!root.isEnd) return false;
    root.isEnd = false;

    // Keep node if has children
    if (Object.keys(root.children).length > 0) return true;

    // Backtrack and trim branches
    while (path.length) {
      const [node, c] = path.pop();
      delete node.children[c];
      if (Object.keys(node.children).length > 0) break;
    }

    return true;
  };
}

XOR Trie

A XOR Trie is a data structure specifically designed for efficiently solving problems related to finding the maximum XOR of numbers in an array, subarray XOR queries, or other XOR-related tasks.

class XORTrie {
  root = {};

  // Insert a number into the trie
  insert = (num) => {
    let node = this.root;
    for (let i = 31; i >= 0; i--) {
      const bit = (num >> i) & 1; // Extract the i-th bit
      if (!node[bit]) {
        node[bit] = {}; // Create a new branch if it doesn't exist
      }
      node = node[bit];
    }
  }

  // Find the maximum XOR of a given number with the trie
  findMaxXOR = (num) => {
    let node = this.root;
    let maxXOR = 0;
    for (let i = 31; i >= 0; i--) {
      const bit = (num >> i) & 1; // Extract the i-th bit
      const oppositeBit = 1 - bit; // XOR maximization prefers the opposite bit
      if (node[oppositeBit]) {
        maxXOR = (maxXOR << 1) | 1; // Add 1 to maxXOR (prefer opposite bit)
        node = node[oppositeBit];
      } else {
        maxXOR = maxXOR << 1; // Add 0 to maxXOR
        node = node[bit];
      }
    }
    return maxXOR;
  }
}

// Example usage
const nums = [3, 10, 5, 25, 2, 8];
const xorTrie = new XORTrie();

// Insert all numbers into the trie
nums.forEach(num => xorTrie.insert(num));

// Find the maximum XOR of any pair in the array
console.log(nums.reduce((maxXor, num) => Math.max(maxXor, xorTrie.findMaxXOR(num)), 0)); // Output: 28

File System

class TrieNode {
  constructor() {
    this.children = {}; // Stores directories/files
    this.isFile = false;
  }
}

class FileSystemTrie {
  constructor() {
    this.root = new TrieNode();
  }

  // Insert a file or directory
  insert(path, isFile = false) {
    const parts = path.split('/').filter(Boolean);
    let node = this.root;

    for (const part of parts) {
      if (!node.children[part]) {
        node.children[part] = new TrieNode();
      }
      node = node.children[part];
    }
    node.isFile = isFile;
  }

  // Search files with a given pattern (backtracking)
  searchFiles(pattern, node = this.root, path = '', results = []) {
    for (const [key, child] of Object.entries(node.children)) {
      const newPath = path ? `${path}/${key}` : key;

      if (child.isFile && key.includes(pattern)) {
        results.push(newPath);
      }
      this.searchFiles(pattern, child, newPath, results);
    }
    return results;
  }
}

// Example Usage
const fs = new FileSystemTrie();

fs.insert('/home/user/documents', false);
fs.insert('/home/user/documents/resume.pdf', true);
fs.insert('/home/user/documents/report.docx', true);
fs.insert('/home/user/photos/vacation.jpg', true);
fs.insert('/home/user/photos/selfie.png', true);
fs.insert('/home/user/notes.txt', true);

console.log(fs.searchFiles('doc'));  // Finds "report.docx"
console.log(fs.searchFiles('res'));  // Finds "resume.pdf"
console.log(fs.searchFiles('.jpg')); // Finds "vacation.jpg"