1. Introduction

Want to learn the front end, first practice good internal power, internal power is not good, even if the moves to practice again fancy, eventually become a master.

Nonlinear table (tree, heap), can be said to be the front-end programmer’s internal work, to know why, know why.

The author wrote the beauty of JavaScript data structure and algorithm series with the language is JavaScript, aimed at the introduction of data structure and algorithm and convenient later review.

What are trees and heaps in nonlinear tables used for? What is the data structure?

I encourage you to read the following with these two questions in mind.

2. The tree

The data structure of a tree is just like a real tree in our lives, but inverted.

The terms defined

  • Node: Each element in the tree is called A node, such as A, B, C, D, E, F, G, H, I, J.
  • Parent node: node that points to child node, such as A.
  • Child node: nodes pointed to by the parent node, such as children B, C, and D of A.
  • Parent-child relationship: The connection of two adjacent nodes, called parent-child relationship, such as A and B, C and H, D and J.
  • Root node: A node with no parent, such as A.
  • Leaf node: node without child node, such as E, F, G, H, I, J.
  • Sibling node: Multiple nodes with the same parent are called sibling nodes, such as B, C, and D.
  • Height of node: from node to leaf nodeThe longest pathThe number of edges contained.
  • Node depth: the number of edges contained in the path from the root node to the node.
  • Node layers: the depth of the node +1 (the number of layers of the root node is 1).
  • Tree height: Equal to the height of the root node.
  • Forest: A collection of N mutually exclusive trees.

Height is measured from the bottom up. For example, if a person is 180cm tall, the starting point is 0.

Depth is measured from the top down, such as a swimming pool of 180cm, and the starting point is zero.

Height and depth are marked with degrees and are counted from 0.

The calculation of the number of floors is the same as that of our usual floors. The bottom layer is the first layer and counts from 1, so the root node is located at the first layer and the other child nodes add 1 successively.

Binary tree classification

Binary tree

  • Each nodeOnly up toA tree of two child nodes, the left child and the right child. As shown in figure 1, 2 and 3. However, a binary tree does not require every node to have two children. Some nodes have only the left child and some have only the right child. And so on, think of their own quadtree, octree structure diagram.

Full binary tree

  • A special binary tree with each node except the leaf nodeThere areA binary tree with left and right children is called a full binary tree. As shown in figure 2.

Complete binary tree

  • A special binary tree in which the leaf nodes are in the bottom two layers and the leaf nodes in the last layer are close togetherOn the leftArrange, and in addition toThe lastThe number of nodes in all other layers must be reachedThe biggestSuch a binary tree is called a complete binary tree. As shown in figure 3. It’s hard to tell a complete binary tree from a partial binary tree, so look at the following figure.

The heap

Stack memory vs. heap memory, shallow copy vs. deep copy: In JavaScript, reference types (such as objects, arrays, functions, etc.) are objects stored in the heap memory, and the value size is not fixed. The access address of the object stored in the stack memory points to the object in the heap memory. JavaScript does not allow direct access to the location in the heap memory, so when manipulating an object, the object reference is actually manipulated.

So what exactly is a heap? What about the data structure?

A heap is actually a special kind of tree. As long as these two things are true, it’s a heap.

  • The heap is a complete binary tree. Complete binary tree: The number of nodes is full except for the last layer, and the nodes of the last layer are arranged to the left.
  • The value of each node in the heap must be greater than or equal to (or less than or equal to) the value of each node in its child tree. It can also be said that each node in the heap has a value greater than or equal to (or less than or equal to) the value of its left and right children. These two statements are equivalent.

A heap with each node greater than or equal to the value of each node in the subtree is called a large top heap. A small top heap is a heap where the value of each node is less than or equal to the value of each node in the subtree.

Figure 1 and figure 2 are the big top heap, Figure 3 is the small top heap, and Figure 4 is not a heap. In addition, as you can see from the figure, we can build many different types of heap for the same set of data.

Binary Search Tree

  • A special kind of binary tree, relativesmallerThe value of theThe left node,largerThe value of theRight node, called binary search tree, also called binary search tree. Binary search tree is an ordered tree, so it supports quick search, quick insertion, and quick deletion of a data. In the figure below, all three are binary search trees,

Balanced binary search tree

  • Balanced binary search tree:The height difference between the left and right subtrees of any node in a binary tree cannot be greater than 1. From this definition, both complete and full binary trees are actually balanced binary trees, but incomplete binary trees may also be balanced binary trees. Balanced binary search treebalanceThe left and right sides of the tree look comparablesymmetry, comparison,balanceDo not make the left subtree tall and the right subtree short. This keeps the height of the whole tree relatively low, and the insertion, deletion, and lookup operations are more efficient. There are many balanced binary search trees, such as Splay Tree (stretch Tree), Treap (stack Tree), etc., but when we mention balanced binary search Tree, we hear basically red black Tree.

Red Black Tree

Nodes in a red-black tree, one class is marked black and one class is marked red. In addition, a red-black tree needs to meet several requirements:

  • The root node is black.
  • Each leaf node is black and NIL, that is, the leaf node does not store data.
  • No neighboring nodes can be red at the same time, that is, red nodes are separated by black nodes.
  • Each node, and all paths from that node to its reachable leaf node, contains the same number of black nodes.

The next two are red black trees.

storage

Storage of complete binary trees

  • Chain store

Each node consists of three fields, one of which stores data and the other two are Pointers to the left and right child nodes. By holding the root node, we can string the whole tree together using Pointers to the left and right child nodes. This storage method is common, and most binary tree code is implemented in this way.

  • Sequential storage

For a complete binary tree, if node X is stored with subscript I in the array, its left child is stored with subscript 2 * I, and its right child is stored with subscript 2 * I + 1. Conversely, the subscript I / 2 is the parent node of the node. Notice that the root node is stored at subscript 1. Arrays are the most efficient way to store a full binary tree.

Traversal of binary trees

There are three classical methods: pre-order traversal, middle-order traversal, post-order traversal. Where, the order before, middle and after represents the order of traversal access of the node and its left and right subtree nodes.

Front-order traversal (root => left => right)

  • For any node in the tree, this node is accessed first, then its left subtree, and finally its right subtree.

Middle-order traversal (left => root => right)

  • For any node in the tree, its left subtree is accessed first, then itself, and finally its right subtree.

Post-order traversal (left => right => root)

  • For any node in the tree, its left subtree is accessed first, then its right subtree, and finally itself.

In fact, the front, middle and back traversal of binary tree is a recursive process.

Time complexity: In the three traversal modes, each node is accessed at most twice, which is proportional to the number of nodes N, so the time complexity is O(n).

Implement binary search tree

Binary search trees are characterized by relatively small values stored in the left node and large values stored in the right node.

Code to achieve a binary search tree, the method has the following.

methods

  • Insert (key) : Inserts a new key into the tree.
  • Search (key) : Searches the tree for a key, returning true if the node exists; If it does not exist, return false.
  • Min: Returns the smallest value/key in the tree.
  • Max: Returns the largest value/key in the tree.
  • Remove (key) : Removes a key from the tree.

traverse

  • PreOrderTraverse:The first sequence traversalMethod traverses all nodes.
  • InOrderTraverse:In the sequence traversalMethod traverses all nodes.
  • PostOrderTraverse:After the sequence traversalMethod traverses all nodes.

Specific code

  • The first implementation of binary search tree class class
// binary search tree class
function BinarySearchTree() {
    // The class used to instantiate the node
    var Node = function(key){
        this.key = key; // The key of the node
        this.left = null; // The pointer to the left node
        this.right = null; // A pointer to the right node
    };
    var root = null; // Set the root node to null
}
Copy the code
  • The insert method inserts a new key into the tree. If the former is greater than the latter, continue to recursively traverse the right child node, and vice versa, continue to traverse the left child node until an empty node is found and inserted at that position.
this.insert = function(key){
    var newNode = new Node(key); // instantiate a node
    if (root === null){
        root = newNode; // If the tree is empty, use this node directly as the root node
    } else {
        insertNode(root,newNode); // Insert node (pass root node as argument)}};// Insert the node function
var insertNode = function(node, newNode){
    // If the key value of the inserted node is smaller than that of the current node
    // When insertNode is first executed, the current node is the root node.
    if (newNode.key < node.key){
        if (node.left === null) {// If the left child of the current node is empty, insert it directly at that left child
            node.left = newNode;
        } else {
            // If the left child node is not empty, we need to continue insertNode,
            // The node to be inserted is compared with the descendants of the left child until the insertion position is foundinsertNode(node.left, newNode); }}else {
        // If the key value of the inserted node is greater than that of the current node
        // The process is similar except that insertNode continues to compare the right child
        if (node.right === null){
            node.right = newNode;
        } else{ insertNode(node.right, newNode); }}}Copy the code

Insert the node with the key value of 6 into the tree as follows:

  • In binary search trees, whether the whole tree or its children, the minimum value must be at the bottom of the tree at the far left. So given a tree or its children, you just go all the way to the left node.
this.min = function(node) {
    // the min method allows passing in subtrees
    node = node || root;
    // Traverse the left child node all the way to the bottom
    while(node && node.left ! = =null) {
        node = node.left;
    }
    return node;
};
Copy the code
  • Search maximum The search maximum is similar to the search for minimum, but traverses along the right side of the tree.
this.max = function(node) {
    // the min method allows passing in subtrees
    node = node || root;
    // Traverse the left child node all the way to the bottom
    while(node && node.right ! = =null) {
        node = node.right;
    }
    return node;
};
Copy the code
  • Searching for a specific value Is handled similarly to inserting a value. Traverses the tree, comparing the value to be searched with the node traversed, recursively traversing the right child node if the former is greater than the latter, recursively traversing the left child node if the former is greater than the latter.
this.search = function(key, node){
    // Again, the search method allows you to look up values in subtrees
    node = node || root;
    return searchNode(key, node);
};
var searchNode = function(key, node){
    // If node is null, there is no value in the tree to look for. Return false
    if (node === null) {return false;
    }
    if (key < node.key){
        // If the value you are looking for is less than this node, continue to recursively traverse its left node
        return searchNode(node.left, key);
    } else if (key > node.key){
        // If the value you are looking for is greater than the node, continue to recursively traverse the node to its right
        return searchNode(node.right, key);
    } else {
        // If the value to be searched is equal to this node, the search is successful
        returnnode; }};Copy the code
  • Removing a node To remove a node, first find the node to be removed in the tree, and then determine whether the node has children, one child node, or two child nodes.
this.remove = function(key, node) {
	// Again, it is allowed to delete nodes only in subtrees
	node = node || root;
	return removeNode(key, node);
};
var self = this;
var removeNode = function(key, node) {
	// If node does not exist, return
	if (node === false) {
		return null;
	}

	// Find the node to delete
	node = self.search(key, node);

	// In the first case, the node has no children
	if (node.left === null && node.right === null) {
		node = null;
		return node;
	}
	// In the second case, the node has only one child node
	if (node.left === null) {
		// Only the right node
		node = node.right;
		return node;
	} else if (node.right === null) {
		// Only the left node
		node = node.left;
		return node;
	}
	// In the third case, there is a node with two children
	// Replace the minimum value in the right subtree to the position to be deleted
	// Find the minimum value
	var aux = self.min(node.right);
	/ / replace
	node.key = aux.key;
	// Delete the minimum value
	node.right = removeNode(aux.key, node.right);
	return node;
};
Copy the code

The process of the third case is shown in the figure below. When want to delete the node has two children, in order not to damage the tree structure, remove the keys of the nodes to substitute up after the size must be in the left and right child nodes of the deleted node between key values, and substitute up node should not have children, otherwise it will produce a node has multiple bytes point, therefore, to find the right subtree of the minimum replacement class. Similarly, you can substitute the maximum value of the left subtree.

  • The first sequence traversal
this.preOrderTraverse = function(callback){
    // Similarly, callback is used to perform operations on nodes traversed
    preOrderTraverseNode(root, callback);
};
var preOrderTraverseNode = function (node, callback) {
    // Iterate until node is null
    if(node ! = =null) {
        callback(node.key); // Process the current node first
        preOrderTraverseNode(node.left, callback); // Continue traversing the left child node
        preOrderTraverseNode(node.right, callback); // Walk through the right child node for the last time}};Copy the code

Walk through the tree shown in the following figure in a prior order and print the node keys. Output: 11 7 5 3 6 9 8 10 15 13 12 14 20 18 25. The traversal process is shown as follows:

  • In the sequence traversal
this.inOrderTraverse = function(callback){
    // Callback is used to perform operations on nodes traversed
    inOrderTraverseNode(root, callback);
};
var inOrderTraverseNode = function (node, callback) {
    // Iterate until node is null
    if(node ! = =null) {
        // The left node is traversed first to ensure that it is traversed from small to large
        inOrderTraverseNode(node.left, callback);
        // Process the current node
        callback(node.key);
        // Traverse the node on the rightinOrderTraverseNode(node.right, callback); }};Copy the code

Do a middle order traversal of the tree below and output the key values of each node. Output: 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25. The traversal process is shown as follows:

  • After the sequence traversal
this.postOrderTraverse = function(callback){
    postOrderTraverseNode(root, callback);
};
var postOrderTraverseNode = function (node, callback) {
    if(node ! = =null) {
        postOrderTraverseNode(node.left, callback); / / {1}
        postOrderTraverseNode(node.right, callback); / / {2}
        callback(node.key); / / {3}}};Copy the code

As you can see, middle-order, pre-order, and post-order traversals are implemented almost exactly the same, except that lines {1}, {2}, and {3} are executed in different order. Perform a back-order traversal of the tree below and print the key values: 3 6 5 8 10 9 7 12 14 13 18 25 20 15 11. The traversal process is shown as follows:

  • Add the method print to print.
this.print = function() {
  console.log('root :', root);
  return root;
};
Copy the code

See the file binary-search-tree.html for the full code

Test process:

/ / test
var binarySearchTree = new BinarySearchTree();
var arr = [11.7.5.3.6.9.8.10.15.13.12.14.20.18.25];
for (var i = 0; i < arr.length; i++) {
	var value = arr[i];
	binarySearchTree.insert(value);
}

console.log('Sequential traversal:');
var arr = [];
binarySearchTree.preOrderTraverse(function(value) {
	// console.log(value);
	arr.push(value);
});
console.log('arr :', arr); / / [11, 7, 5, 3, 6, 9, 8, 10, 15, 13, 12, 14, 20, 18, 25]

var min = binarySearchTree.min();
console.log('min:', min); / / 3
var max = binarySearchTree.max();
console.log('max:', max); / / 25
var search = binarySearchTree.search(10);
console.log('search:', search); / / 10
var remove = binarySearchTree.remove(13);
console.log('remove:', remove); / / 13

console.log('Sequential traversal:');
var arr1 = [];
binarySearchTree.preOrderTraverse(function(value) {
	// console.log(value);
	arr1.push(value);
});
console.log('arr1 :', arr1); //  [11, 7, 5, 3, 6, 9, 8, 10, 15, 14, 12, 20, 18, 25]

console.log('Middle traversal:');
var arr2 = [];
binarySearchTree.inOrderTraverse(function(value) {
	// console.log(value);
	arr2.push(value);
}); 
console.log('arr2 :', arr2); / / [3, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 18, 20, 25]

console.log('After traversal:');
var arr3 = [];
binarySearchTree.postOrderTraverse(function(value) {
	// console.log(value);
	arr3.push(value);
});
console.log('arr3 :', arr3); //  [3, 6, 5, 8, 10, 9, 7, 12, 14, 18, 25, 20, 15, 11]

binarySearchTree.print(); // Look at the console
Copy the code

The results are as follows:

See here, you can answer the title of the article nonlinear table tree, heap is used? What is the data structure?

If not, go back and take a closer look.

3. Article output plan

The beauty of JavaScript data structures and algorithms series of articles, adhere to about 3-7 days to update a tentative plan as shown in the following table.

The title link
Time and space complexity Github.com/biaochenxuy…
Linear tables (arrays, linked lists, stacks, queues) Github.com/biaochenxuy…
Implementing a front-end route, how to implement browser forward and backward? Github.com/biaochenxuy…
Stack and heap memory, shallow copy and deep copy Github.com/biaochenxuy…
recursive Github.com/biaochenxuy…
Nonlinear tables (tree, heap) Github.com/biaochenxuy…
Bubble sort Wonderful to be continued
Insertion sort Wonderful to be continued
Selection sort Wonderful to be continued
Merge sort Wonderful to be continued
Quick sort Wonderful to be continued
Count sorting Wonderful to be continued
Radix sort Wonderful to be continued
Bucket sort Wonderful to be continued
Hill sorting Wonderful to be continued
Heap sort Wonderful to be continued
Top 10 classic rankings Wonderful to be continued

If there is any mistake or not precise place, please be sure to give correction, thank you very much.

4. The last

Last Saturday and Sunday, accidentally watched the grave robbers notes TV drama, did not resist, but also read two 😂😅, so the article update a little slow.

It will be updated in about 3-7 days. Please look forward to it.

Reference article:

The beauty of data structures and algorithms

Learn JavaScript data structures and algorithms – trees