JavaScript data structure and algorithm (Part 2)
In the last article, we learned a lot of data structures, including stack, queue, dictionary, linked list and so on. I hope you can absorb them one by one and we will make progress together. In this article, we will explore the mysteries of trees and graphs, and I will introduce several algorithms to arm our algorithm system. Start learning!
7, Tree
(1) Common tree
 Concept: what is a tree? A tree is a data structure similar to a tree in our life, which is composed of nodes and edges. Many scenes in our life can be described by trees, such as the company's position structure, family relationship spectrum, food chain, etc. Therefore, it is very important for us to study the characteristics of trees and learn trees.
 The above figure can well represent the structure of A tree. We need to understand several concepts. For example, A is the root node of the tree. Because A has three child nodes, A can also be called A 3degree node. Then you can silently tell me how many degree nodes D, C and B are? And there are many B's at the bottom. All B's are essentially leaf nodes!
 This is a common tree, which is composed of several points and edges. Each node has its own value and also stores references to other nodes.
(2) Binary tree
 What is a binary tree? In fact, a binary tree is a tree in which each node is at most a seconddegree node, that is, as long as the number of its child nodes does not exceed two nodes, such a tree can be called a binary tree, and any tree can be regarded or converted into a binary tree through certain operations.
 Compared with ordinary trees, binary trees have some specific laws, so the study of binary trees is actually a very important topic!
 The above is a standard binary tree and a perfect binary tree. You can see that each node has no more than two nodes. In this case, we can also classify. Some binary trees with incomplete symmetrical branches are called complete binary trees, and the rest are called ordinary binary trees
(3) Binary search tree
 Now we want to know an important topic, binary search tree
 What is a binary search tree
 In accordance with the principle of binary tree, we can meet the following requirements
1. If its left subtree is not empty, the values of all nodes on the left subtree are less than the values of the root node
2. If its right subtree is not empty, the values of all nodes on the right subtree are greater than those of the root node
3. Its left and right subtrees are also binary search trees
 Look at the above example. The numbers of all nodes on the left side of the root node are smaller than the root node, and the numbers on the right side are larger than the root node. And fully meet the requirements of the above three points, so we can confidently call the tree above as a binary search tree.
 But the question is, what's his use!
 A: its search efficiency is very high. We will package it later.
 You can find that the binary tree is orderly. Therefore, when we want to find a data, we don't have to compare and traverse one by one. First, we compare it with the root node. If it is larger than the root node, the target must be on the right, otherwise, it must be on the left. In this way, half of the data is excluded, so the search efficiency is greatly improved.
 And the more average a binary search tree is, the fewer levels are, and the higher the search efficiency is. Therefore, when creating a binary search tree, we should also distribute the binary search tree as evenly as possible! This is also an important topic.
 Well, having said so much, let's formally encapsulate the binary search tree!
// Encapsulation node class TreeNode { constructor(data, left, right) { this.data = data this.left = null this.right = null if (left && left < data) { this.left = left } if (right && right > data) { this.right = right } } } //Encapsulated binary search tree class BinarySearchTree { constructor(root) { this.root = root  null this.size = 0 } whitchIn(node, newNode) { if (newNode.data > node.data) { // The description is larger and should be inserted on the right if (node.right === null) { node.right = newNode } else { this.whitchIn(node.right, newNode) } } else { if (node.left === null) { node.left = newNode } else { this.whitchIn(node.left, newNode) } } } insert(data) { if (this.root == null) { const newNode = new TreeNode(data) this.root = newNode } else { // Call recursive function const newNode = new TreeNode(data) this.whitchIn(this.root, newNode) } this.size++ return this } // Depth first traversal foreach(handler, type = 'first') { this.forFun(this.root, handler, type) } forFun(node, handler, type) { if (node !== null) { if (type === 'first') { handler(node.data) } this.forFun(node.left, handler, type) if (type === 'middle') { handler(node.data) } this.forFun(node.right, handler, type) if (type === 'last') { handler(node.data) } } } min(current = this.root, returnType = 'data') { while (current.left !== null) { current = current.left } if (returnType === 'data') { return current.data } else { return current } } max(current = this.root, returnType = 'data') { let parentNode = null while (current.right !== null) { parentNode = current current = current.right } if (returnType === 'data') { return current.data } else { return [current, parentNode] } } search(data) { let node = this.root while (node !== null) { if (data > node.data) { node = node.right } else if (data < node.data) { node = node.left } else { return true } } return false } remove(data) { let parentNode = null let isLeft = true let current = this.root while (current != null) { if (data > current.data) { isLeft = false parentNode = current current = current.right } else if (data < current.data) { isLeft = true parentNode = current current = current.left } } if (current.left === null && current.right === null) { if (current === this.root) { this.root = null } else { if (isLeft) { parentNode.left = null } else { parentNode.right = null } } } else if (current.left === null) { if (isLeft) { parentNode.left = current.right } else { parentNode.right = current.right } } else if (current.right = null) { if (isLeft) { parentNode.left = current.left } else { parentNode.right = current.left } } else { // This is the famous third case, where neither side is zero let [current = replaceNode, parentNode = replaceParentNode] = this.max(current.left, 'node') let replaceLeft = replaceNode.left if (replaceNode.left !== null) { replaceParentNode.right = replaceLeft } replaceNode.left = current.left replaceNode.right = current.right if (isLeft) { parentNode.left = replaceNode } else { parentNode.right = replaceNode } } } }

In fact, most of them are easy to understand in the packaging process, but the deletion operation is still troublesome. There are many situations to consider. Let me sort out my ideas!

First, we will get a point to be deleted. Through a roundtrip operation, we can get the node to be deleted, the parent node of the node to be deleted, and whether the node to be deleted is the left node of the parent node.

Then there will be several big situations

1. If the node to be deleted is a leaf node,

2. If the node to be deleted has only one left child node

3. If the node to be deleted has only one right child node

4. If the node to be deleted has two child nodes

Make a judgment according to the above different situations to ensure that after deleting a node, it is still a binary search tree.
(4) Red black tree
 The thing above is actually a red black tree
 Let's answer first, what is red black tree and why red black tree appears!
 Red black tree is essentially a binary search tree
 It is actually used to solve a problem
 When inserting data into the binary search tree, sometimes the tree formed by the insertion will lose balance, which makes the layer side of the binary search tree very deep
 As we all know, the efficiency of the binary search tree is very related to its hierarchy. Therefore, I must find a way to continuously adjust the binary search tree during the insertion process to make it relatively balanced and stable
 The red black tree is such a relatively balanced and evenly distributed binary search tree!
 Below is an unbalanced binary search tree

It can be seen that if we do not adjust, as long as we insert a larger number that increases more than continuous insertion, it will form a deep structure. In this way, the binary search tree will lose its original meaning.

Red black tree is a solution!

In other words, as long as the red black tree meets the following rules, it can ensure that the red black tree is a binary search tree with relatively uniform distribution and search efficiency close to the best

Every section

It's not black

It's red
* The root node is always black * If the node is red, its child nodes must be black (otherwise not necessarily) * Each path from root to leaf node * The number of black nodes must be the same
Because the content of red black tree is still relatively responsible, we will introduce red black tree here for the time being. Later, I will write a blog to introduce it in detail.
8, Figure

Next, we need to understand an important data structure, graph, and even have a set of special theories to study it in mathematics!

Today, we take it out of context and only learn what is helpful for our development.

In the data structure of graph, it is composed of nodes and edges. Why does graph appear!

In fact, because there are many problems in life, we can abstract them into graphs for research, which can facilitate research and help us analyze them with the help of mathematical tools.
 It will be found that the graph is very similar to the binary search tree, because the binary search tree is actually a graph. The graph is composed of nodes and edges, and any node can point to any node from the edge
 In life, we will encounter the shortest path problem and the minimum cost problem, which can be analyzed with the help of graphs.
 First, we encapsulate the data structure of graph!
class Graph { constructor() { this.vertexes = [] this.edges = {} this.size = 0 this.state = {} } addVertex(vertex) { let list = new List() // The list here is the encapsulated list of the previous article this.vertexes.push(vertex) this.edges[[vertex]] = list this.size++ this.state[vertex] = false } addEdge(vertex1, vertex2) { // Judge if it doesn't exist this.edges[vertex1].append(vertex2) this.edges[vertex2].append(vertex1) return this } toString() { let result = '' for (var key in this.edges) { result += key + '=>' + this.edges[key].toString() + '\n' } console.log(result); return result } }
9, Traversal algorithm
 In order to traverse the graph structure, we can have two strategies, the first one
 Start traversing from the start node, traverse its child nodes one by one, and then the grandchildren until the nodes in the whole graph are traversed. This method is called breadth first search.
 The second is to start traversing from the start node, traverse its first child node, and then traverse the first child node and the first child node. After this branch traverses, traverse the second child node of the start node and traverse the whole graph. This method is called depth first search, and we also write the method.
 Just add it directly to the previous class!
// BFS breadth first search bfs(initV, handler) { let queue = [] queue.push(initV) // [ 'A','B','C','D'... ] while (queue.length > 0) { let targetV = queue.shift() if (!this.state[targetV]) { this.edges[targetV].foreach((item) => { if (!this.state[targetV]) { queue.push(item) } }) handler(targetV) this.state[targetV] = true } } } // DFS depth first search dfs(initV, handler) { let handleNode = (initV, handler) => { if (!this.state[initV]) { handler(initV) this.state[initV] = true this.edges[initV].foreach(item => { if (!this.state[item]) { handleNode(item, handler) } }) } } handleNode(initV, handler) }
10, Sorting algorithm
 Next, we will introduce several sorting algorithms. Each sorting algorithm has its own characteristics!
 Why should we understand the sorting algorithm!
 Because it is very important to change a group of data from disorder to order. It plays an important role in managing and using these data in the future. Therefore, let's learn the sorting algorithm!
(1) Bubble sorting
 First of all, let me explain bubble sorting. Its core is to compare the first one with the second one when there is a set of data. Follow a principle that if who is bigger, change who to the front! Then compare the second with the third! At the end of the first cycle, the last face of this set of data must be a maximum number, and then use the cycle to control where to end the sub cycle. The outer cycle should decrease, because the more to the end, the fewer elements to compare! Finally, there is a sorted data!
class ArrayList { constructor(arr = []) { this.arr = arr this.size = arr.length } insert(ele) { this.arr.push(ele) this.size++ } toString() { let result = '' this.arr.forEach((item) => { result += item + " " }) return result } // change of position exchange(position1, position2) { let temp = this.arr[position1] this.arr[position1] = this.arr[position2] this.arr[position2] = temp } // Bubble sort O(n**2) bubbleSort() { for (var j = this.size  1; j > 0; j) { for (var i = 0; i < j; i++) { if (this.arr[i] > this.arr[i + 1]) { this.exchange(i, i + 1) } } } } }
(2) Select sort
 Selective sorting is actually an optimization of bubbling sorting. The main optimization is the number of exchanges. You can imagine bubbling sorting in your mind. First, the inner loop of bubbling sorting will find the largest value and put it in the end, but the final result is formed by many exchanges, If the largest tree is at the top of the data column, That has to be exchanged n1 times (N generally refers to the length of the list) in order to put the maximum value at the end. The optimization idea of sorting is that since the maximum value is compared, why don't we find the maximum value in the limited range first. After finding it, we only need to exchange it once, and this time directly put the maximum value at the end! Is this much less than the exchange times of bubble sorting? Yes, Let's write it!
class ArrayList { constructor(arr = []) { this.arr = arr this.size = arr.length } insert(ele) { this.arr.push(ele) this.size++ } toString() { let result = '' this.arr.forEach((item) => { result += item + " " }) return result } // change of position exchange(position1, position2) { let temp = this.arr[position1] this.arr[position1] = this.arr[position2] this.arr[position2] = temp } // Select sort O(n**2) chooseSort() { for (var j = 0; j < this.size; j++) { let min = j for (var i = j + 1; i < this.size; i++) { if (this.arr[min] > this.arr[i]) { min = i } } this.exchange(min, j) } } }
 Did you find that the first level cycle does not end once, there will be a maximum value position, and then make an exchange,
(3) Insert sort
 The socalled insertion sort is the real optimization of the number of cycles. How to optimize it? Let's explain the insertion sort in detail
 The idea of insertion sorting is to always regard the left side of a group of unordered sequence as ordered, and the first time is the first, because there is only one, so we regard it as ordered.
 The second time, take out the second bit and insert it into the ordered sequence on the left, and then traverse the ordered sequence. Because it is ordered, as long as you find the first number smaller than the extracted number and insert it in front of the number, you don't need to traverse the whole sequence. Therefore, the number of cycles can be less than the above two algorithms, So the whole sequence can be ordered until the end.
 All right, let's start writing!
class ArrayList { constructor(arr = []) { this.arr = arr this.size = arr.length } insert(ele) { this.arr.push(ele) this.size++ } toString() { let result = '' this.arr.forEach((item) => { result += item + " " }) return result } // change of position exchange(position1, position2) { let temp = this.arr[position1] this.arr[position1] = this.arr[position2] this.arr[position2] = temp } // Insert sort O(n**2) insertSort() { for (var i = 1; i < this.size; i++) { let target = this.arr[i] for (var j = 0; j < i; j++) { if (target < this.arr[j]) { this.exchange(i, j) break } } } }
 In fact, the second loop is suggested to be written as a while loop, so there is no need to force break to end the loop
(4) Quick sort
 Next, you can be a little excited! Quick sorting is known as one of the top 10 algorithms in the 20th century.
 What is the idea of quick sorting! It's like this!
 From a group of unordered sequences, select any number as middle as possible (that is, the size of this number is almost in the middle of this group of sequences), and then put all the numbers larger than this tree on the right and those smaller than this number on the left
 Then do the same recursive operation for the unordered sequence on the left and right sides
 After recursion, there is an ordered sequence of numbers
 Let's look at the code!
class ArrayList { constructor(arr = []) { this.arr = arr this.size = arr.length } insert(ele) { this.arr.push(ele) this.size++ } toString() { let result = '' this.arr.forEach((item) => { result += item + " " }) return result } // Quick sort quickSort(arr = this.arr) { if (arr.length == 1  !arr.length) { return arr } else { let middle = arr[0] let less = arr.filter(item => item < middle) let more = arr.filter(item => item > middle) return [...this.quickSort(less), middle, ...this.quickSort(more)] } } }
 After seeing the code, it's easier to understand! In fact, in addition to these four sorting algorithms, there is also a hill sorting. Interested students can also learn about it! Due to space reasons, I won't introduce it here!