Tree of data structures

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…