JavaScript binary tree and binary search tree implementation and application

Next, let’s discuss the tree in JS data structure. The tree here is analogous to a tree in real life, with trunks and branches. In a program, a tree is a data structure, which is not useful for storing data that needs to be found quickly. It is an abstract model of hierarchical data. A tree structure consists of a series of nodes in which a parent-child relationship exists. Each node has a parent node and zero or more children. So it is a tree structure 🙂

Concepts related to trees: 1. Subtree: a node and its descendants, as shown in the figure above. 2. Depth: The depth of a node depends on the number of its ancestors. For example, node 5 has two ancestors and its depth is 2. 3. Height: The height of the tree depends on the maximum depth of all nodes.

Introduction to binary trees and binary search trees

A node in a binary tree can only have two children at most, one on the left and one on the right. The advantage of this definition is that it helps us to write more efficient algorithms for inserting, finding and deleting nodes.

A binary search tree is a type of binary tree, but it only allows you to store values smaller than the parent in the left child node and larger than the parent in the right node. Next we will implement a binary search tree along these lines.

1. Create BinarySearchTree class

Here we will use the constructor to create a class:

function BinarySearchTree(){
    // The class used to create the node
    let Node = function(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
    / / the root node
    let root = null;
}
Copy the code

We will use Pointers similar to those used in linked lists to represent the relationships between nodes. If you don’t know about linked lists, see my post on how to Implement unidirectional and Bidirectional Linked Lists.

2. Insert a key

// Insert a key
this.insert = function(key) {
    let newNode = new Node(key);
    root === null ? (root = newNode) : (insertNode(root, newNode))
}
Copy the code

Inserting a new Node into the tree has three main parts: 1. Creating an instance of the Node class for the new Node –> 2. Determine whether the insert operation is the root node, if it is the root node, point it to the root node -> 3. Add the node to a location other than the root node.

The implementation of insertNode is as follows:

function insertNode(node, newNode){
    if(newNode.key < node.key) {
        node.left === null ? (node.left = newNode) : (insertNode(node.left, newNode))
    }else {
        node.right === null ? (node.right = newNode) : (insertNode(node.right, newNode))
    }
}
Copy the code

We’re going to use recursion here, and we’re going to use recursion a lot in search, del, etc., so if you don’t know it, you can learn it. We create a binary tree instance to insert a key:

let tree = new BinarySearchTree();
tree.insert(20);
tree.insert(21);
tree.insert(520);
tree.insert(521);
Copy the code

The inserted structure will be inserted according to the rules of binary search tree, similar to the first tree graph above.

Tree traversal

There are three traversal methods to access all nodes in the tree: medium order, first order, and last order.

In order traversal: access all nodes in order from smallest to largest
Preorder traversal: Each node is accessed in order prior to its descendants
Post-order traversal: Access the node’s descendants before access the node itself

Based on the above introduction, we can have the following implementation code.

Sequence of sorting

this.inOrderTraverse = function(cb){
    inOrderTraverseNode(root, cb);
}

// Helper function
function inOrderTraverseNode(node, cb){
    if(node ! = =null){ inOrderTraverseNode(node.left, cb); cb(node.key); inOrderTraverseNode(node.right, cb); }}Copy the code

In order traversal can be used to achieve the tree from small to large sort function.

First order sorting

// Sort first -- access each node in order prior to its descendants
   this.preOrderTraverse = function(cb) {
     preOrderTraverseNode(root, cb);
   }

   // Sort the helper method first
   function preOrderTraverseNode(node, cb) {
     if(node ! = =null) { cb(node.key); preOrderTraverseNode(node.left, cb); preOrderTraverseNode(node.right, cb); }}Copy the code

Use preorder sorting to achieve the ability to structure the output.

After the sequence sorting

// Subsequent traversal - first access the descendant node, then access the node itself
   this.postOrderTraverse = function(cb) {
     postOrderTraverseNode(root, cb);
   }

   // Then iterate over the helper method
   function postOrderTraverseNode(node, cb) {
     if(node ! = =null){ postOrderTraverseNode(node.left, cb); postOrderTraverseNode(node.right, cb); cb(node.key); }}Copy the code

Post-order traversal can be used to calculate the size of all elements in a hierarchical relationship.

Search for values in the tree

There are three types of search that are often performed in a tree: maximum, minimum, and specific values.

The minimum value

The minimum value can be defined as the node at the bottom of the left tree. The specific implementation code is as follows:

/ / the minimum
   this.min = function(){
     return minNode(root)
   }

    function minNode(node) {
     if(node) {
       while(node && node.left ! = =null){
         node = node.left;
       }
       return node.key
     }
     return null
   }
Copy the code

Similarly, the maximum value can be achieved as follows:

/ / Max
   this.max = function() {
     return maxNode(root)
   }

   function maxNode(node) {
     if(node){
       while(node && node.right ! = =null){
         node = node.right;
       }
       return node.key
     }
     return null
   }
Copy the code

2. Search for a specific value

// Search for a value in the tree
this.search = function(key) {
    return searchNode(root, key)
}

// Search AIDS
function searchNode(node, key){
    if(node === null) {
        return false
    }
    if(key < node.key) {
        return searchNode(node.left, key)
    } else if(key > node.key) {
        return searchNode(node.right, key)
    }else {
        return true}}Copy the code

Removing a node

this.remove = function(key){
    root = removeNode(root, key);
}

// Discover the smallest node
function findMinNode(node) {
    if(node) {
    while(node && node.left ! = =null){
        node = node.left;
    }
    return node
    }
    return null
}

// Remove the node helper method
function removeNode(node, key) {
    if(node === null) {
    return null
    }

    if(key < node.key){
    node.left = removeNode(node.left, key);
    return node
    } else if( key > node.key){
    node.right = removeNode(node.right, key);
    return node
    } else {
    // A page node
    if(node.left === null && node.right === null) {
        node = null;
        return node
    }

    // A node with only one child node
    if(node.left === null) {
        node = node.right;
        return node
    }else if(node.right === null) {
        node = node.left;
        return node
    }

    // A node with two child nodes
    let aux = findMinNode(node.right);
    node.key = aux.key;
    node.right = removeNode(node.right, aux.key);
    return node
    }
}
Copy the code

There are many cases to consider when deleting a node. Here we will use a similar implementation to min to write a function to find the smallest node. When the node to be deleted has two children, we will replace the current node to be deleted with the value of the largest child node, and then delete the child node.

At this point, a binary search tree is implemented, but there is a problem, it again if the tree is very deep, there will be some performance problems, in order to solve this problem, we can use the AVL tree, a kind of self balanced binary tree, that is to say, both side of any one node subtree height difference for a maximum of 1.

If you want to learn more about JS algorithms and data structures, you can long press attention oh ~

More recommended

With JavaScript and C3 to achieve a turntable small game
Teach you to use 200 lines of code to write a love bean spell H5 small game (with source code)
Exploration and summary of front-end integrated solutions based on React/VUE ecology
How to use gulP4 development project scaffolding
How to write your own JS library in less than 200 lines of code
A summary of common JS functions that make you more productive in an instant
A picture shows you how to play vue-Cli3 quickly
3 minutes teach you to use native JS implementation with progress listening file upload preview component
3 minutes teach you to use native JS implementation with progress listening file upload preview component
Developing travel List with Angular8 and Baidu Maps API
Js basic search algorithm implementation and 1.7 million data under the performance test
How to make front-end code 60 times faster
Front End Algorithm series array deweighting
Vue Advanced Advanced series – Play with Vue and vuex in typescript
In the first three years, talk about the top five books worth reading

JavaScript binary tree and binary search tree implementation and application

Introduction to binary trees and binary search trees

1. Create BinarySearchTree class

2. Insert a key

Tree traversal

Search for values in the tree

More recommended

Related Posts

You don’t know vscode | warehouse configuration project constraints

Front-end development in the common JS library

What objects are in JavaScript?