“🌟🌟🌟🌟🌟“

“Taste: Ants on a tree“

“Cooking time: 10min“

This article has been featured on Github github.com/Geekhyt, thanks to Star.

Mr. Zhou Shuren once said: if you learn tree well, you will master half of data structure and algorithm!

Canteen boss (Tong Oba) : even if we as the Internet wave of leaf nodes, also need to have an ant of the spirit of shaking the tree, even if an ant is powerful. Because even if you spend your whole life being average, you can’t spend your whole life trying to be average.

Today’s recipe, ants climbing a tree, let’s introduce the actors.

Tree related noun popular science

  • The root node
  • A leaf node
  • The parent node
  • Child nodes
  • Brother nodes
  • highly
  • The depth of the
  • layer

A is the root node. C, D, F, and G are leaf nodes. A is the parent of B and E. B and E are children of A. B and E are sibling nodes. Height, depth and layer are shown in the figure above. For easy memorization, height means looking up, depth means looking down. Different from height and depth, floors are similar to buildings in Inception. Buildings are counted from the first floor. In Inception, buildings are inverted and start from the top down.

Binary Tree

Each node has a maximum of two children, namely, the left child and the right child.

Binary Tree Full Binary Tree

The leaf nodes are all at the bottom level, and each node except the leaf node has left and right child nodes. The graph above is a full binary tree.

Complete Binary Tree

The leaf nodes are in the bottom two layers, and the leaf nodes in the last layer are arranged to the left, and the number of nodes in all layers except the last layer should reach the maximum.

A heap is a complete binary tree, usually stored in an array.

Using array storage complete binary tree, do not need to store the left and right child node Pointers like chain storage, can save memory.


Traversal of binary trees


  • Sequential traversal: Prints the current node first, then the left subtree of the current node, and finally the right subtree of the current node(ABCDEFG)
  • Middle-order traversal: Prints the left subtree of the current node first, then the current node, and finally the right subtree of the current node(CBDAFEG)
  • Back-order traversal: Prints the left subtree of the current node, then the right subtree of the current node, and finally the current node(CDBFGEA)
// preorder traversal
const preorderTraversal = function(root) {
    const result = [];
    function pushRoot(node) {
        if(node ! =null) {
 result.push(node.val);  if(node.left ! =null) {  pushRoot(node.left);  }  if(node.right ! =null) { pushRoot(node.right);  }  }  }  pushRoot(root);  return result; }; Copy the code
// middle order traversal
const inorderTraversal = function(root) {
    const result = [];
    function pushRoot(node) {
        if(node ! =null) {
 if(node.left ! =null) {  pushRoot(node.left);  }  result.push(node.val);  if(node.right ! =null) { pushRoot(node.right);  }  }  }  pushRoot(root);  return result; }; Copy the code
// after the sequence traversal
const postorderTraversal = function(root) {
    const result = [];
    function pushRoot(node) {
        if(node ! =null) {
 if(node.left ! =null) {  pushRoot(node.left);  }  if(node.right ! =null) { pushRoot(node.right);  }  result.push(node.val);  }  }  pushRoot(root);  return result; }; Copy the code

Complexity analysis

  • Time complexity: O(n)
  • Space complexity: Worst-case O(n), average case O(logn)

Binary Search Tree

Also known as binary sorting tree, binary search tree.

Middle order traversal binary search tree, can output ordered data sequence, time complexity is O(N), very efficient.

Any node in a binary search tree, every node in the left subtree is less than this node, and every node in the right subtree is greater than this node.


In binary search trees, the time complexity of search, insert, delete and many other operations is proportional to the height of the tree. The time complexity of the two extreme cases is O(n) and O(logn) respectively, corresponding to the case where the binary tree degenerates into a linked list and the case where the binary tree is complete.

In extreme cases, complexity degradation is not desirable, so we need to design a balanced binary search tree. The height of balanced binary search tree is close to logn, so the time complexity of search, insert and delete operation is stable, which is O(logn).

AVL Tree Adelson Velsky – Landis Tree

AVL tree is the first invented balanced binary search tree (named after the inventor), which defines that the height difference between the left and right subtrees of any node is no more than 1, and both subtrees are a balanced binary tree.

AVL tree is a highly balanced binary search tree. Although the search efficiency is high, in order to maintain a high balance, the insertion and deletion operations need to be adjusted (left rotation, right rotation), which needs to pay a large maintenance cost.


Red-black Tree Red-balck Tree

A red-black tree could be called a “web mangrove,” with a higher attendance than any other tree by a skyline. Unlike AVL trees, red-black trees are approximately balanced, not strictly balanced. Therefore, the cost of maintaining balance is lower than that of AVL tree, and the performance of search, insert, delete and other operations is relatively stable, and the time complexity is O(logn).

A qualified red black tree should satisfy:

  • Every node can be red or black
  • The root node is black
  • Each leaf node is black and empty (leaf nodes do not store data)
  • Adjacent nodes cannot be red at the same time, and red and black are separated
  • Each node, and all paths from that node to its reachable leaf node, contains the same number of black nodes

Red-black trees have a lot of applications in engineering, because engineering performance stability is very high requirements. Because of its stable performance, red-black trees are leading in engineering applications.


Trie tree

Behind the powerful keyword prompt function of search engines such as Google and Baidu, the most basic principle is the Trie tree, which reduces the query time to improve efficiency by changing time through space and using the common prefix of string. In addition, there are many applications, such as the longest prefix matching algorithm of Trie tree in IP routing, the use of forwarding table to select the path, and intelligent hints in IDE.


Trie tree is an atypical multi-fork tree model, which is different from the general multi-fork tree. We can compare the data structure design of their nodes. A typical multi-fork tree node contains node values and Pointers to children. The nodes of the Trie tree contain whether the node is the end of a string and a list of letter mappings. With the letter mapping table we can get all of the children from one parent.

The time complexity of finding a string in the Trie tree is O(k), where k is the length of the string to find.


The Trie tree is made up of five words: color, coat, city, Hi, and hot. The value of the root is null.

LeetCode 208. Implement Trie tree

class Trie {
  constructor() {
    this.root = {};
  }
  insert(word) {
 let curr = this.root;  word.split(' ').forEach(ch= > (curr = curr[ch] = curr[ch] || {}));  curr.isWord = true;  }  traverse(word) {  let curr = this.root;  for (let i = 0; i < word.length; i++) {  if(! curr)return null;  curr = curr[word[i]];  }  return curr;  }  search(word) {  let node = this.traverse(word);  return!!!!! node && !! node.isWord; }  startsWith(word) {  return!!!!!this.traverse(word);  } } Copy the code

B + tree

We know that indexes stored in content are faster to query than those stored on disk. But when the volume of data is large, the index is also large. Memory is limited and we have to store indexes on disk. Then, how to improve the efficiency of reading from disk becomes one of the key engineering.

Most indexes of relational databases, such as MySQL and Oracle, are implemented by B+ tree. B+ trees are better than red-black trees for building indexes stored on disk. A B+ tree is a multi-fork tree whose height is lower than a red-black tree when the same number of data are indexed. When querying data with indexes, reading B+ tree indexes requires fewer disk I/OS.

A B-tree of order M satisfies the following characteristics:

  • The number of neutron nodes k of each node is m > K > m/2, and the number of child nodes of the root node can not exceed m/2
  • Leaf nodes are connected in series through a bidirectional linked list for easy searching by interval
  • M-tree only stores indexes, not really data
  • Typically, the root node is stored in memory and the other nodes are stored on disk

reference

  • The Beauty of Data Structures and Algorithms

The articles

  • How the front end handles data structures and Algorithms (Pilot)
  • Time and space complexity analysis of JavaScript algorithm
  • Do you really understand recursion?
  • Divide and conquer, dynamic programming, backtracking, greed

❤️ Love triple punch

1. Please give me a “like” when you see this. Your “like” is the motivation for my creation.

2. Pay attention to the front canteen of the public account, “your front canteen, remember to eat on time”!

3. This article has been included in the front canteen Github github.com/Geekhyt, for a small Star, thanks to Star.