More articles
preface
Asked for leave to go home, came back to continue serious work, study
Data flattening
This paper first introduces a practical development of tree data optimization — data flattening, which is a more practical method, but still needs to be flexible according to the actual needs
Tree is a hierarchical structure, and the query of tree nodes requires recursive query until the corresponding node is found, and such frequent search is quite performance consuming. At this time, we can flatten the tree, as shown in the following data:
let tree = [
{
id: '1'.name: 'a'.children: [{id: 1-1 ' '.name: 'a-1'.arr: [1]}]}, {id: '2'.name: 'b'.children: [{id: '2-1'.name: 'b-1'
}, {
id: '2-2'.name: 'b-2'}}]]Copy the code
Let’s flatten the above data:
let flatTree = {};
const getFlatTree = (tree, parent) = > {
tree.forEach((item) = > {
flatTree[item.id] = item;
flatTree[item.id].parent = parent
if (item.children) {
getFlatTree(item.children, item)
}
})
}
getFlatTree(tree, null)
console.log(flatTree)
// Print the result
/ / {
// 1: {id: "1", name: "a", children: Array(1), parent: null}
/ / 1-1: {id: "1-1," name: "a - 1", arr, Array (1), the parent: {... }}
// 2: {id: "2", name: "b", children: Array(2), parent: null}
// 2-1: {id: "2-1", name: "b-1", parent: {... }}
// 2-2: {id: "2-2", name: "b-2", parent: {... }}
// }
Copy the code
Can see after processing tree into an object, the object contains all tree nodes, it much easier to query, in any one node contains the tree data of the whole line (can make corresponding processing) according to the actual business, subsequent query, modify, operations such as operational data, after treatment to avoid recursive consumption operation performance, time and again not give more examples, Flexible use is recommended
The tree
Next, let’s look at trees in detail
Basic concept
Let’s start with some concepts about trees. Here’s an example
- node
- Each element in A tree is A node, for example, A, B, C, D, E, F, K, L, and M
- There is only one root node and no parent node, for example: A
- A is the parent of B (B is A child of A), B is the parent of E, and B and C are siblings of each other
- Those without children are leaf nodes, such as K, L, F, M, G, I, J
- Node degree and hierarchy
- Degree refers to the number of children of A node. The degree of A node is 3 and the degree of B is 2
- The root node is the first layer, and so on, D is the second layer and H is the third layer
- Ordered tree, unordered tree
- From left to right according to the law of ordered tree refers to the tree, that puts the most on the left side of the tree of the first child is called “first child,” called the “last” at the right, if above, orderly tree, the root node subtree is B the first child of the whole tree, D as the root node subtree as last of the whole tree
- A tree that is not ordered is an unordered tree
Binary tree
Binary trees have two characteristics:
- A binary tree is an ordered tree
- Each node of a binary tree has a degree of 2 or less
Binary trees are divided into full binary trees and complete binary trees:
- Full binary trees are nodes (except leaf nodes) whose degree is 2 and leaf nodes are at the same level, as follows:
- A complete binary tree is a full binary tree except for the last layer, and it is arranged from left to right as follows:
Implement binary search tree
The basic principle of implementing binary search tree is to store the left node smaller than the parent node and the right node larger than the parent node. Next is code time, first implement a node class:
class Node {
constructor(key) {
this.key = key; // Store node data
this.left = null; // Store data smaller than nodes
this.right = null; // Store data larger than the node}}Copy the code
Then write a simple binary search tree class
insert
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(key) {
const newNode = new Node(key);
const insertNode = (node, newNode) = > {
if (newNode.key < node.key) {
if (node.left === null) {
node.left = newNode
} else {
// The node exists, continue to insert
insertNode(node.left, newNode)
}
} else {
if (node.right === null) {
node.right = newNode
} else {
insertNode(node.right, newNode)
}
}
}
if (!this.root) {
// The root is assigned for the first time
this.root = newNode;
} else {
// Insert children
insertNode(this.root, newNode)
}
}
}
Copy the code
Insert a binary tree into a binary tree
const tree = new BinarySearchTree();
tree.insert(11)
tree.insert(7)
tree.insert(12)
tree.insert(3)
tree.insert(10)
console.log(tree.root)
Copy the code
The results are still in line with our expectations, as follows:
Now let’s implement depth-first traversal of the tree, and there are three methods of depth-first traversal, so let’s look at them
In the sequence traversal
// Sequential traversal is a way of accessing all nodes in the smallest to largest order
inOrderTraverse(callback) {
const inOrderTraverseNode = (node, callback) = > {
if(node ! = =null) {
inOrderTraverseNode(node.left, callback)
callback(node.key)
inOrderTraverseNode(node.right, callback)
}
}
inOrderTraverseNode(this.root, callback)
}
tree.inOrderTraverse((value) = >console.log('Middle order traversal',value))
Copy the code
The result is as follows:
The first sequence traversal
// Sequential traversal accesses each node in precedence over subsequent nodes. One application of preemptive traversal is to print a structured document.
preOrderTraverse(callback) {
const preOrderTraverseNode = (node, callback) = > {
if(node ! = =null) {
callback(node.key)
preOrderTraverseNode(node.left, callback)
preOrderTraverseNode(node.right, callback)
}
}
preOrderTraverseNode(this.root, callback)
}
tree.preOrderTraverse((value) = >console.log('Sequential traversal',value))
Copy the code
The result is as follows:
Subsequent traversal
// After traversal, the descendant nodes of the node are visited first, and then the node itself. One application of back-order traversal is to calculate the size of the space occupied by all files in a directory and its subdirectories.
postOrderTraverse(callback) {
const postOrderTraverseNode = (node, callback) = > {
if(node ! = =null) {
postOrderTraverseNode(node.left, callback)
postOrderTraverseNode(node.right, callback)
callback(node.key)
}
}
postOrderTraverseNode(this.root, callback)
}
tree.postOrderTraverse((value) = > console.log('Post-order traversal', value))
Copy the code
Breadth-first traversal
orderByLevel(callback) {
const { root } = this;
if(! root)return
let queue = [ root ];
while(queue.length) {
let level = queue.length;
for(let i = 0; i < level; i++ ) {
const current = queue.shift()
callback(current.key);
current.left ? queue.push(current.left) : ' ';
current.right ? queue.push(current.right) : ' '; }}}Copy the code
The query
// Query the minimum value
min(node) {
const minNode = node= > node ? (node.left ? minNode(node.left) : node) : null;
return minNode(node || this.root)
}
// Query the maximum value
max(node) {
const maxNode = node= > node ? (node.right ? maxNode(node.right) : node) : null;
return maxNode(node || this.root)
}
// Search for a specific value
search(key) {
const searchNode = (node, key) = > {
if (node === null) return false
if (node.key === key) return node
return searchNode((key < node.key) ? node.left : node.right, key)
}
return searchNode(this.root, key)
}
Copy the code
remove
remove(key) {
const 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 {
if (node.left == null && node.right == null) {
// No children, completely remove itself
node = null;
return node;
}
if (node.left == null) {
// Select the right node from the left node
node = node.right;
return node;
} else if (node.right == null) {
// Select the left node from the right node
node = node.left;
return node;
}
// Find the minimum value to the right of the node and assign it to the node to be removed
var aux = this.findMinNode(node.right);
node.key = aux.key;
/ / remove the aux
node.right = removeNode(node.right, aux.key);
returnnode; }}return removeNode(this.root, key)
}
// Find the smallest node on the right
findMinNode(node) {
while(node && node.left ! = =null) {
node = node.left;
}
return node;
}
Copy the code
The complete code
class Node {
constructor(key) {
this.key = key;
this.left = null;
this.right = null; }}class BinarySearchTree {
constructor() {
this.root = null;
}
insert(key) {
const newNode = new Node(key);
const insertNode = (node, newNode) = > {
if (newNode.key < node.key) {
if (node.left === null) {
node.left = newNode
} else {
insertNode(node.left, newNode)
}
} else {
if (node.right === null) {
node.right = newNode
} else {
insertNode(node.right, newNode)
}
}
}
if (!this.root) {
this.root = newNode;
} else {
insertNode(this.root, newNode)
}
}
// Sequential traversal is a way of accessing all nodes in the smallest to largest order
inOrderTraverse(callback) {
const inOrderTraverseNode = (node, callback) = > {
if(node ! = =null) {
inOrderTraverseNode(node.left, callback)
callback(node.key)
inOrderTraverseNode(node.right, callback)
}
}
inOrderTraverseNode(this.root, callback)
}
Preemptive traversal accesses each node in order of precedence over descendant nodes. One application of preemptive traversal is to print a structured document.
preOrderTraverse(callback) {
const preOrderTraverseNode = (node, callback) = > {
if(node ! = =null) {
callback(node.key)
preOrderTraverseNode(node.left, callback)
preOrderTraverseNode(node.right, callback)
}
}
preOrderTraverseNode(this.root, callback)
}
// After traversal, the descendant nodes of the node are visited first, and then the node itself is accessed. One application of back-order traversal is to calculate the size of the space occupied by all files in a directory and its subdirectories.
postOrderTraverse(callback) {
const postOrderTraverseNode = (node, callback) = > {
if(node ! = =null) {
postOrderTraverseNode(node.left, callback)
postOrderTraverseNode(node.right, callback)
callback(node.key)
}
}
postOrderTraverseNode(this.root, callback)
}
orderByLevel(callback) {
const { root } = this;
if(! root)return
let queue = [ root ];
while(queue.length) {
let level = queue.length;
for(let i = 0; i < level; i++ ) {
const current = queue.shift()
callback(current.key);
current.left ? queue.push(current.left) : ' ';
current.right ? queue.push(current.right) : ' '; }}}// Query the minimum value
min(node) {
const minNode = node= > node ? (node.left ? minNode(node.left) : node) : null;
return minNode(node || this.root)
}
// Query the maximum value
max(node) {
const maxNode = node= > node ? (node.right ? maxNode(node.right) : node) : null;
return maxNode(node || this.root)
}
// Search for a specific value
search(key) {
const searchNode = (node, key) = > {
if (node === null) return false
if (node.key === key) return node
return searchNode((key < node.key) ? node.left : node.right, key)
}
return searchNode(this.root, key)
}
// Remove a node
remove(key) {
const 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 {
if (node.left == null && node.right == null) {
// No children, completely remove itself
node = null;
return node;
}
if (node.left == null) {
// Select the right node from the left node
node = node.right;
return node;
} else if (node.right == null) {
// Select the left node from the right node
node = node.left;
return node;
}
// Find the minimum value to the right of the node and assign it to the node to be removed
var aux = this.findMinNode(node.right);
node.key = aux.key;
/ / remove the aux
node.right = removeNode(node.right, aux.key);
returnnode; }}return removeNode(this.root, key)
}
// Find the smallest node on the right
findMinNode(node) {
while(node && node.left ! = =null) {
node = node.left;
}
returnnode; }}Copy the code
conclusion
To be continued…