Learning JavaScript Data Structures and Algorithms

Loiane Groner

• Éditeur: Packt Publishing
• Année: 2018
• ISBN:
  9781788624947
• Édition: 3
• Sujet: Informatique
• Sous-sujet: Développement Web

Create classic data structures and algorithms such as depth-first search and breadth-first search, learn recursion, as well as create and use a heap data structure using JavaScriptAbout This Book• Implement common data structures and the associated algorithms along with the context in which they are used• Master existing JavaScript data structures such as arrays, sets, and maps, and learn how to implement new ones such as stacks, linked lists, trees, and graphs in ES 8• Develop abstract data types to make JavaScript a more flexible and powerful programming languageWho This Book Is ForIf you're a JavaScript developer who wants to dive deep into JavaScript and write complex programs using JavaScript data structures and algorithms, this book is for you.What You Will Learn• Declare, initialize, add, and remove items from arrays, stacks, and queues• Create and use linked lists, doubly linked lists, and circular linked lists• Store unique elements with hash tables, dictionaries, and sets• Explore the use of binary trees and binary search trees• Sort data structures using algorithms such as bubble sort, selection sort, insertion sort, merge sort, and quick sort• Search elements in data structures using sequential sort and binary searchIn DetailA data structure is a particular way of organizing data in a computer to utilize resources efficiently. Data structures and algorithms are the base of every solution to any programming problem. With this book, you will learn to write complex and powerful code using the latest ES 2017 features.Learning JavaScript Data Structures and Algorithms begins by covering the basics of JavaScript and introduces you to ECMAScript 2017, before gradually moving on to the most important data structures such as arrays, queues, stacks, and linked lists. You will gain in-depth knowledge of how hash tables and set data structures function as well as how trees and hash maps can be used to search files in an HD or represent a database. This book serves as a route to take you deeper into JavaScript. You'll also get a greater understanding of why and how graphs, one of the most complex data structures, are largely used in GPS navigation systems in social networks.Toward the end of the book, you'll discover how all the theories presented in this book can be applied to solve real-world problems while working on your own computer networks and Facebook searches.Style and approachEasy to follow guide which will cover the most used data structures and sorting/searching algorithms known in the computer science world along with examples to help the readers understand each chapter thoroughly.

Trees

So far in this book, we have covered some sequential data structures. The first non-sequential data structure we covered in this book was the Hash Table. In this chapter, you will learn about another non-sequential data structure called a tree, which is very useful for storing information that needs to be found easily.

In this chapter, we will cover:

• Tree terminology
• Creating a binary search tree
• Traversing a tree
• Adding and removing nodes
• The AVL tree

The tree data structure

A tree is an abstract model of a hierarchical structure. The most common example of a tree in real life would be a family tree or a company organizational chart, as we can see in the following figure:

Tree terminology

A tree consists of nodes with a parent-child relationship. Each node has a parent (except for the first node at the top) and zero or more children, as in the following figure:

The top node of a tree is called the root (11). It is the node that does not have a parent. Each element of the tree is called a node. There are internal nodes and external nodes. An internal node is a node with at least one child (7, 5, 9, 15, 13, and 20 are internal nodes). A node that does not have children is called an external node or a leaf (3, 6, 8, 10, 12, 14, 18, and 25 are leaves).

A node can have ancestors and descendants. The ancestors of a node (except the root) are the parent, grandparent, great-grandparent, and so on. The descendants of a node are children (child), grandchildren (grandchild), great-grandchildren (great-grandchild), and so on. For example, node 5 has 7 and 11 as its ancestors and 3 and 6 as its descendants.

Another terminology used with trees is the subtree. A subtree consists of a node and its descendants. For example, the nodes 13, 12, and 14 constitute a subtree from the tree of the preceding diagram.

The depth of a node consists of the number of ancestors. For example, node 3 has a depth of 3 because it has three ancestors (5, 7, and 11).

The height of a tree consists of the maximum depth of any node. A tree can also be broken down into levels. The root is on level 0, its children are on level 1, and so on. The tree from the preceding diagram has a height of 3 (the maximum depth is 3, as shown in the preceding figure on level 3).

Now that we know the most important terms related to trees, we can start learning more about trees.

The binary and binary search trees

A node in a binary tree has two children at most: one left child and one right child. This definition allows us to write more efficient algorithms to insert, search, and delete nodes to/from a tree. Binary trees are largely used in computer science.

A binary search tree (BST) is a binary tree, but it only allows you to store nodes with lesser values on the left-hand side and nodes with greater values on the right-hand side. The diagram in the previous topic exemplifies a binary search tree.

This will be the data structure that we will work on in this chapter.

Creating the Node and BinarySearchTree classes

Let’s start by creating our Node class that will represent each node of our binary search tree using the following code:

export class Node { constructor(key) { this.key = key; // {1} node value this.left = null; // left child node reference this.right = null; // right child node reference } }

The following diagram exemplifies how a binary search tree (BST) is organized in terms of the data structure:

Just as in linked lists, we will work with pointers (references) again to represent the connection between the nodes (called edges in tree terminology). When we worked with doubly linked lists, each node had two pointers: one to indicate the next node and another one to indicate the previous node. When working with trees, we will use the same approach, meaning we will also work with two pointers. However, one pointer will point to the left child, and the other one will point to the right child. For this reason, we will need a Node class that will represent each node of the tree. A small detail that is worth noting is that instead of calling the node itself as a node or item, as we did in the previous chapters, we will call it as key ({1}). A key is what a tree node is known as in tree terminology.

Next, we will declare the basic structure of our BinarySearchTree class:

import { Compare, defaultCompare } from '../util'; import { Node } from './models/node'; export default class BinarySearchTree { constructor(compareFn = defaultCompare) { this.compareFn = compareFn; // used to compare node values this.root = null; // {1} root node of type Node }

We will follow the same pattern we used in the LinkedList class (from Chapter 6, Linked Lists). This means that we will also declare a variable so that we can control the first node of the data structure. In the case of a tree, instead of the head, we have the root ({1}).

Next, we need to implement some methods. The following are the methods we create in our BinarySearchTree class:

• insert(key): This method inserts a new key in the tree
• search(key): This method searches for the key in the tree and returns true if it exists and false if the node does not exist
• inOrderTraverse(): This method visits all nodes of the tree using in-order traverse
• preOrderTraverse(): This method visits all nodes of the tree using pre-order traverse
• postOrderTraverse(): This method visits all the nodes of the tree using post-order traverse
• min(): This method returns the minimum value/key in the tree
• max(): This method returns the maximum value/key in the tree
• remove(key): This method removes the key from the tree...