Book Image

Learning JavaScript Data Structures and Algorithms - Second Edition

By : Loiane Groner
Book Image

Learning JavaScript Data Structures and Algorithms - Second Edition

By: Loiane Groner

Overview of this book

This book begins by covering basics of the JavaScript language and introducing ECMAScript 7, before gradually moving on to the current implementations of ECMAScript 6. You will gain an in-depth knowledge of how hash tables and set data structure functions, as well as how trees and hash maps can be used to search files in a HD or represent a database. This book is an accessible route deeper into JavaScript. Graphs being one of the most complex data structures you’ll encounter, we’ll also give you a better understanding of why and how graphs are largely used in GPS navigation systems in social networks. Toward the end of the book, you’ll discover how all the theories presented by this book can be applied in real-world solutions while working on your own computer networks and Facebook searches.
Table of Contents (18 chapters)
Learning JavaScript Data Structures and Algorithms - Second Edition
Credits
About the Author
About the Reviewer
www.PacktPub.com
Preface

Self-balancing trees


Now that you know how to work with BST, you can dive into the study of trees if you want to.

BST has a problem: depending on how many nodes you add, one of the edges of the tree can be very deep, meaning a branch of the tree can have a high level and another branch can have a low level, as shown in the following diagram:

This can cause performance issues when adding, removing, and searching for a node on a particular edge of the tree. For this reason, there is a tree called the Adelson-Velskii and Landi's tree (AVL tree). The AVL tree is a self-balancing BST tree, which means the height of both the left and right subtrees of any node differs by 1 at most. You will learn more about the AVL tree in the next topic.

Adelson-Velskii and Landi's tree (AVL tree)

The AVL tree is a self-balancing tree, meaning the tree tries to self-balance whenever a node is added to it or removed from it. The height of the left or right subtree of any node (and any level) differs by 1 at most...