Home/Blog/Programming/Data Structures 101: Advanced Data Structures in JavaScript

Data Structures 101: Advanced Data Structures in JavaScript

Jerry Ejonavi

Dec 03, 2020

9 min read

content

What are Tries?Pros and Cons of Tries Implementing Tries in JavaScript Insertion in a trie Searching a Trie Deletion in a Trie Self-Balancing-Binary-Search-Trees Application of Self-Balancing BTS Keep the learning going.Segment Trees Binary Index Trees Applications of Binary Index Trees What to learn next Continue reading about data structures and algorithms

Become a Software Engineer in Months, Not Years

From your first line of code, to your first day on the job — Educative has you covered. Join 2M+ developers learning in-demand programming skills.

Data structures are important in computer programming for organizing, managing, and storing data quickly and efficiently. It’s important for a software engineer to have a good grasp of the various data structures.

This knowledge is useful to help you solve problems during coding interviews and build fast and efficient applications.

Today, we would be looking at some advanced data structures such as segmented trees, tries, self-balancing trees, and binary index trees.

The knowledge of basic data structures like trees, stacks, and heaps, would be a good foundation for this article.

Today, we will be learning:

What are Tries?
Implementing Tries in JavaScript
What are Self-Balancing BST?
What are Segment Trees
What are Binary Index Trees?
What to learn next

Get hands-on with data structures
This course contains a detailed review of all the common data structures and provides implementation level details in JavaScript. Also available in other languages.

Data Structures for Coding Interviews in JavaScript

What are Tries?#

The word ‘trie’ is derived from the word retrieval. Tries are an ordered tree-like data structure efficient in handling programming problems related to strings.

It is also called a Prefix Tree or a Digital tree.

Tries are used in dictionary word searches, spell-checking and in search engines by making auto-suggestions. Some properties are necessary to maintain the overall efficiency of a trie, they include:

A trie is always a set of linked nodes with an empty root node.
Each node represents a unique alphabet.
Each node can point to null or other children nodes.
The depth of a trie depends on the longest word that it stores.
Tries to provide the same path for words that share a common prefix.
The size of a trie depends on the number of alphabets (i.e. the child nodes), and the number of child nodes in a trie depends upon the total number of values possible.

For example, in English, there are 26 letters so the number of unique nodes cannot exceed 26. Likewise, in Bengali with 50 letters would have 50 unique nodes.

Pros and Cons of Tries#

Enjoying the article? Scroll down to sign up for our free, bi-monthly newsletter.

Implementing Tries in JavaScript#

Every node in a trie represents an alphabet. A typical node in a trie consists of three data members:

char: This stores the character that the node is supposed to contain.
children[ ]: An array that consists of pointers to children nodes. The size of this array depends on the number of alphabets. All are set to null.
isEndWord: A flag to indicate the end of a word. It is set to false by default and is only updated when words end during insertion.

A trie would be implemented using the TrieNode class, and each node would have at most 26 children if we are storing English words. The root node (usually placed on top) contains 26 pointers, each representing a letter in the English alphabet.

These pointers hold either null or another trieNode.

The children pointers have a zero index and all words are stored in a top-to-bottom manner. Remember to always set the isEndWord flag to true on the last character to indicate the end of the word.

To implement a trie node, create a Trienode.js file and paste the following code:

"use strict";
module.exports = class TrieNode{
  constructor(char){
    this.children = [];
    for(var i=0; i<26; i++){ //Total # of English Alphabets
      this.children[i]=null;
    }
    this.isEndWord = false; //will be true if the node represents the end of word
    this.char = char; //To store the value of a particular key
  }
  //Function to mark the currentNode as Leaf
  markAsLeaf(){
    this.isEndWord = true;
  }
    
  //Function to unMark the currentNode as Leaf  
  unMarkAsLeaf(){
    this.isEndWord = false;
  }
}

Insertion in a trie#

To insert a key(word) into a trie, you first check if the character in the key exists at the index you need it to be. If it does, you set the isEndWord on the last character to true.

If a prefix is present, the new key would be added as an extension of the last prefix key. The last case would be if there is no common prefix, the children nodes would be added to the root node which is always null.

The key length determines the trie depth. Note that null keys are not allowed in a trie and all keys are stored in lowercase.

Always remember to set the isEndWord value of the last node to true.

Create an index.js file and add the following code to it:

use strict";
const TrieNode = require('./TrieNode.js');
 
class Trie{
 constructor(){
   this.root = new TrieNode(''); //Root node
  };
 
  getIndex(t){
   return t.charCodeAt(0) - "a".charCodeAt(0);
  }
  //Function to insert a key in the Trie
  insert(key){
   if (key == null){
     return;
   };
  
   key = key.toLowerCase();
   let currentNode = this.root;
   let index = 0;  
        
   //Store the character index 
   //Iterate the trie with the given character index,
   //If the index points to null
   //simply create a TrieNode and go down a level 
   for (let level=0; level<key.length; level++){
     index = this.getIndex(key[level]);
    
     if (currentNode.children[index] == null){
       currentNode.children[index] = new TrieNode(key[level]);
       console.log(String(key[level]) + " inserted");
     }
     currentNode = currentNode.children[index];
   }
    
   //Mark the end character as leaf node
   currentNode.markAsLeaf();
   console.log("'" + key + "' inserted");
  };
  
 //Function to search a given key in Trie
 search(key){
   return false;
 };
 delete(key){
   return;
 }
} 
 // Input keys (use only 'a' through 'z' and lower case)
let keys = ["the", "a", "there", "answer", "any",
                    "by", "bye", "their","abc"];   
let t = new Trie();
console.log("Keys to insert: ");
console.log(keys);
  //Construct Trie
for (let i=0; i<keys.length; i++){
t.insert(keys[i]);
}

In the code above, a Trie class is created. The root node ) is initialized in the constructor. Then, we iterate over characters in the key and get the index for each character using getIndex( ).

Next, in an insert() method, we first write a check to ensure that null keys are not allowed and all keys are stored in lower case. Then we store the character’s index by iterating the trie with the given character index.

If the index points to null, we create a TrieNode to go a level down. Finally, we mark the last node as the leaf node, since the word has ended.

For a key with n characters, the worst-case time complexity turns out to be $O(n)$ since we need to make $n$ iterations.

Searching a Trie#

To search through a trie, you need to take note of three possible cases:

If the word does not exist, you find null before the last character can be exhausted.
If the word is a substring of another word, it would not be found because its isEndWord value of the last character on the trie is set to false.
If the word exists as a path from the root node to the last node and/or node marked as an end, then it is a successful search case.

search(key){
  
   if (key == null){
     return false; //null key
   }
  
   key = key.toLowerCase();
   let currentNode = this.root;
   let index = 0;
  
   //Iterate the Trie with given character index,
   //If it is null at any point then we stop and return false
   //We will return true only if we reach leafNode and have traversed the
   //Trie based on the length of the key
  
   for (var level=0; level<key.length; level++){
     index = this.getIndex(key[level]);
     if (currentNode.children[index] == null){
       return false;
     }
     currentNode = currentNode.children[index];
   }                                            
   if (currentNode != null && currentNode.isEndWord){
     return true;
   }
   return false;
 };

Deletion in a Trie#

Nodes without child branches are easily deleted. The leaf node exists first till the entire word is deleted. For prefixes, the isEndWord value is set to false.

Words with common prefixes would have their last node deleted along with all parent nodes in the branch that do not have any other children and are not end characters.

To delete a node in a trie, we first write a helper function to check if the currentNode has any children.

Then we write a recursive function that takes a key, the key’s length, a trie node, and the level (index) of the key as an argument. This function deletes any given key.

//Helper Function 
 hasNoChildren(currentNode){
   for (let i=0; i<currentNode.children.length; i++){
     if (currentNode.children[i] != null)
       return false;
   }
   return true;
 }
  
 //Recursive function
deleteHelper(key, currentNode, length, level){
   let deletedSelf = false;
       
   if (currentNode == null){
     console.log("Key does not exist");
     return deletedSelf;
   }
  
   //Base Case: If we have reached the node which points to the alphabet at the end of the key.
   if (level == length){
     //If there are no nodes ahead of this node in this path
     //Then we can delete this node
     if (this.hasNoChildren(currentNode)){
       currentNode = null;
       deletedSelf = true;
     }
    
     //If there are nodes ahead of currentNode in this path
     //Then we cannot delete currentNode. We simply unmark this as leaf
     else{
       currentNode.unMarkAsLeaf();
       deletedSelf = false;
     }
   }
   else{
     let childNode = currentNode.children[this.getIndex(key[level])];
     let childDeleted = this.deleteHelper(key, childNode, length, level + 1);
     if (childDeleted){
       //Making children pointer also None: since child is deleted
       currentNode.children[this.getIndex(key[level])] = null;
       //If currentNode is leaf node that means currentNode is part of another key
       //and hence we can not delete this node and it's parent path nodes
       if (currentNode.isEndWord)
         deletedSelf = false;
      
       //If childNode is deleted but if currentNode has more children then currentNode must be part of another key
       //So, we cannot delete currentNode
       else if(this.hasNoChildren(currentNode) == false)
         deletedSelf = false;
      
       //Else we can delete currentNode
       else{
         currentNode = null;
         deletedSelf = true;
       }
     } 
     else
       deletedSelf = false;
   } 
   return deletedSelf
 }
  //Function to delete given key from Trie
 delete(key){
    if (this.root == null || key == null){
     console.log("None key or empty trie error");
     return;
    }
  
    this.deleteHelper(key, this.root, key.length, 0);
 }
}

Self-Balancing-Binary-Search-Trees#

Self-Balancing Binary Search Trees are a height-balanced tree that automatically tries to keep its height as minimal as possible when performing basic operations.

A balanced tree is one where for every node, the height of its right and left subtrees differs by at most 1.

The time complexity of all three basic operations- Insertion, deletion, and search take $O(h)$ time, where $h$ is the height of the Binary Search Tree.

Common examples of Self-Balancing BST include Red-Black Trees, AVL, Splay Tree, and treaps. These BSTs perform Left or Right Rotations after performing insertion and delete operations while maintaining its BTS property.

Application of Self-Balancing BTS#

Self-Balancing trees are used to maintain ordered lists, such as a priority queue.
They are used for associative arrays where key-value pairs are inserted in an order based on the key.
They can be extended easily to perform new operations, which can be used to optimize database queries or other list-processing algorithms.

Segment Trees#

A segment tree is a tree data structure used in storing intervals or segments. It is used in cases where there are multiple range queries on the array and modifications of elements of the same array.

It follows the principle of a static structure, whereby a structure cannot be modified once it’s built. This means that we can update the values of nodes but we cannot change its structure.

Before building a segment tree, we need to decide the following:

The value is stored in each node of the tree and,
The merge operation that would form the internal parent node.

A common case would be finding the sum of all the elements in an array from indices L to R.

Here, at each node (except the leaf nodes), the sum of its children nodes is stored.

A segment tree can be built using recursion (i.e, from the bottom-up). Each leaf represents a single element, and in each step, data from two leaves are used to form an internal parent node.

This parent node can be merged with another leaf or parent node depending on what level it is on, till it gets to the root node.

The merge operation used depends on the question being solved. So, recursion will end up at the root node, which will represent the whole array.

The image below illustrates a sum query for an array:

let x = [2, 6, -3, 8, -5];

The shaded boxes represent the leaf nodes while the clear boxes represent the internal parent nodes.

Segment trees are a flexible data structure. It can be used in solving problems like finding the sum of elements on some segments in an array or finding the minimum query of all elements in an array with indices l to r in $O(logN)$ time.

Binary Index Trees#

A binary indexed tree (also known as a Fenwick tree) is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers efficiently.

It provides a way to represent an array of numbers in an array or a tree. The time complexity for every operation on binary index trees is $O(logN)$ . The tree will take $n-1$ nodes.

Each binary tree node contains an index and a value. The value is a prefix sum.

Compared to segmented trees, binary indexed trees are more space-efficient and relatively easier to implement, especially during programming contests.

Applications of Binary Index Trees#

Binary Indexed trees are used to implement the arithmetic coding algorithm.
They can be used to count inversions in an array in $O(NlogN)$ time.

What to learn next#

I hope that this helped you get a good understanding of some of the more advanced data structures. There’s still so much more to learn about these data structures and others, such as:

Disjoint set data structure
K Dimensional Trees
n-ary Tree

You can continue your learning with Educative’s course on Data Structures for Coding Interviews in JavaScript. The course aims to give you a detailed explanation of all common JavaScript data structures.

It also contains real-world data structure problems and their solutions. By the end of the course, you should be better equipped to write better code with all the different data structures that you learn.

Happy learning!

Continue reading about data structures and algorithms#

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments