28
loading...
JavaScript Data Structures and Algorithms (Trees, Part 1: Binary Trees)
Hello! In this 5th post about JavaScript data structures and algorithms I will be discussing trees and how we run insert, append, prepend, traverse, and delete operations for then. By now you must realize I'm not one for preambles, so let's dive right in!
Trees are data structures that consist of a parent node, or a root, and two child nodes, referred to as the left child and right child, respectively. Each child is also capable of having children and being a root to those children. Trees where all left children have a lower value than the root, and all right children are valued greater than the root, are called binary trees. :
//First I'll define a node class with properties for the left and right children, as well as the node's value
class Node {
constructor(value){
this.left = null;
this.right = null;
this.value = value;
}
}
//This tree object will contain the operations for insertion, deletion, lookup, etc.
class BinarySearchTree {
constructor(){
this.root = null;
}
...
}As a side note, we can create the node object in more than one way. In the example above we instantiated a node class we can call upon at a future time, or we can also create a node object within our tree's methods.
...
const newNode = {
left: null,
right: null,
value: value
}
...Since traversion requires visiting every node, whether it is by indexed order or level-by-level (more on this later in the series), searching operations are done, at best, in O(log n) time, and O(n) time at worst. A tree's height is determined by the number of levels that exist after the root. For example, a tree with only three nodes (the root and 2 children) has a height of 1.
Furthermore, since a single node in a binary search tree will either be located on the left half or the right half of the tree, we only need to traverse that half of a tree to find a node, based on its value compared to our root's value.
Furthermore, since a single node in a binary search tree will either be located on the left half or the right half of the tree, we only need to traverse that half of a tree to find a node, based on its value compared to our root's value.
...
lookup(value){
//verify our parameters
if (!this.root) {
return false;
}
//track the node being traversed through
let currentNode = this.root;
while(currentNode){
//search the left half of the tree
//of left half is less than root value
if(value < currentNode.value){
currentNode = currentNode.left;
//search the right half if the node's
//value is greater than the roots value
} else if(value > currentNode.value){
currentNode = currentNode.right;
//return the node with a matching value
} else if (currentNode.value === value) {
return currentNode;
}
}
return null
}
...Insertion and deletion operations in binary search trees are fast. Below you will find example insert method, given a target value:
...
insert(value){
const newNode = new Node(value);
if (this.root === null) {
this.root = newNode;
} else {
let currentNode = this.root;
while(true){
if(value < currentNode.value){
//Left
if(!currentNode.left){
currentNode.left = newNode;
return this;
}
currentNode = currentNode.left;
} else {
//Right
if(!currentNode.right){
currentNode.right = newNode;
return this;
}
currentNode = currentNode.right;
}
}
}
...Like when inserting a node into a binary search tree, we must traverse from the root node to the target node. This requires traversal, iteration through every element in the tree. The most commonly used traversal techniques are pre-order traversal, post-order traversal, and in-order traversal. In the example below I use pre-order traversal, which visits every node in the following order: root, left, right. Every left child is traversed first in pre-order traversal. Only when there is no longer a left child to traverse will we visit the right child.
delete(value) {
if (!this.root) {
return false;
}
let currentNode = this.root;
let parentNode = null;
while(currentNode){
if(value < currentNode.value){
parentNode = currentNode;
currentNode = currentNode.left;
} else if(value > currentNode.value){
parentNode = currentNode;
currentNode = currentNode.right;
} else if (currentNode.value === value) {
//We have a match, get to work!
//Option 1: No right child:
if (currentNode.right === null) {
if (parentNode === null) {
this.root = currentNode.left;
} else {
//if parent > current value, make current left child a child of parent
if(currentNode.value < parentNode.value) {
parentNode.left = currentNode.left;
//if parent < current value, make left child a right child of parent
} else if(currentNode.value > parentNode.value) {
parentNode.right = currentNode.left;
}
}
//Option 2: Right child which doesnt have a left child
} else if (currentNode.right.left === null) {
currentNode.right.left = currentNode.left;
if(parentNode === null) {
this.root = currentNode.right;
} else {
//if parent > current, make right child of the left the parent
if(currentNode.value < parentNode.value) {
parentNode.left = currentNode.right;
//if parent < current, make right child a right child of the parent
} else if (currentNode.value > parentNode.value) {
parentNode.right = currentNode.right;
}
}
//Option 3: Right child that has a left child
} else {
//find the Right child's left most child
let leftmost = currentNode.right.left;
let leftmostParent = currentNode.right;
while(leftmost.left !== null) {
leftmostParent = leftmost;
leftmost = leftmost.left;
}
//Parent's left subtree is now leftmost's right subtree
leftmostParent.left = leftmost.right;
leftmost.left = currentNode.left;
leftmost.right = currentNode.right;
if(parentNode === null) {
this.root = leftmost;
} else {
if(currentNode.value < parentNode.value) {
parentNode.left = leftmost;
} else if(currentNode.value > parentNode.value) {
parentNode.right = leftmost;
}
}
}
return true;
}
}
}28