This album is based on B station “JavaScript data Structures and algorithms” video organized study notes, the author of this article has the notes, source code, test environment hosted on GitHub, welcome students Star and Fork.

It is recommended that you follow the order of the directory structure to learn, from the shallow to the deep, step by step, easy to figure out the data structure and algorithm.

What is a tree?

Real trees:

Characteristics of the tree:

  • Trees generally have a root, connected to the root is the trunk;
  • The trunk diverges, forming branches that go on to form smaller branches;
  • The last of the branches are the leaves;

In real life, many structures are abstractions of trees. The simulated tree structure is equivalent to a tree rotated 180 degrees.

What are the advantages of tree structures over arrays/linked lists/hashes?

Array:

  • Advantages: Can be accessed through the subscript value, high efficiency;
  • Disadvantages: When searching data, the data needs to be sorted first to generate an ordered array, so as to improve the search efficiency; In addition, a large number of displacement operations are required when inserting and deleting elements.

List:

  • Advantages: Data insertion and deletion operation efficiency is very high;
  • Disadvantages: low search efficiency, need to start from the beginning to search, until the target data is found; When data needs to be inserted or deleted in the middle of the list, the insertion or deletion is inefficient.

Hash table:

  • Advantages: Hash table insert/query/delete efficiency is very high;
  • Disadvantages: low space utilization, many elements in the underlying array are not utilized; Moreover, the elements in the hash table are unordered, and the elements in the hash table cannot be traversed in a fixed order; And you can’t quickly figure out what the maximum or minimum value is in the hash table.

Tree structure:

  • Advantages: The tree structure integrates the advantages of the above three structures, but also makes up for their shortcomings (although the efficiency is not necessarily higher than them). For example, the data in the tree structure are ordered, and the search efficiency is high; High space utilization rate; And can quickly obtain the maximum and minimum values.

In general: Each data structure has its own specific application scenario.

Tree structure:

  • Tree: a finite set consisting of n (n ≥ 0) nodes. When n = 0, it is called an empty tree.

  • For any non-empty tree (n > 0), it has the following properties:

    • There is a special node in the number called Root, denoted by r;
    • The remaining nodes can be divided into m (m > 0) non-intersecting finite sets T1, T2… Tm, where each set is itself a tree, called a SubTree of the original tree.

Common terms for trees:

  • Degree: the number of subtrees of a node. For example, the Degree of node B is 2;
  • Tree degree: the maximum degree of all nodes in the tree, such as the tree degree in the figure above is 2;
  • Leaf node: Node of degree 0 (also called Leaf node), such as H, I, etc., in the figure above;
  • Parent node: The node whose degree is not 0 is called the Parent node. In the figure above, node B is the Parent node of nodes D and E.
  • Child: if B is the parent of D, then D is a Child of B;
  • Sibling nodes: Nodes with the same parent node are Sibling nodes to each other, such as B and C, D and E in the figure above are mutually Sibling nodes;
  • Path and path length: A path refers to A channel from one node to another. The number of edges in A path is called the path length. For example, the length of A->H path is 3.
  • Node Level: specifies that the root node is at layer 1, and the number of layers of any other node is the number of layers of its parent node plus 1. For example, the level of B and C nodes is 2;
  • Tree Depth: The maximum level of all nodes in the tree is the Depth of the tree.

Representation of the tree structure

The most common expression:

As shown in the figure, the structure of a tree is similar to a linked list, which is made up of node connections. However, the number of references required for each parent node varies depending on the number of nodes in each parent node. For example, node A needs three references to child nodes B, C, and D; Node B requires two references, one to child nodes E and F; The K node does not need to be referenced because it has no child nodes.

The disadvantage of this approach is that we cannot determine the number of references to a particular node.

Son-brother notation:

This representation can completely record the data of each node, such as:

/ / the node A
Node{
  // Store data
  this.data = data
  // Record only the left child node
  this.leftChild = B
  // Record only the first sibling node on the right
  this.rightSibling = null
}

/ / the node B
Node{
  this.data = data
  this.leftChild = E
  this.rightSibling = C
}

/ F/node
Node{
  this.data = data
  this.leftChild = null
  this.rightSibling = null
}
Copy the code

The advantage of this notation is that the number of references in each node is determined.

The son-brother representation rotates

Here is the tree structure of the son-brother notation:

After rotating it clockwise by 45° :

This makes a binary tree, from which we can conclude that any tree can be simulated by a binary tree. But doesn’t that change the parent? In fact, the parent node is only set to be convenient to point to the child node. In the code implementation, it doesn’t matter who the parent node is, as long as the corresponding node is found correctly.

Binary tree

If each node in a tree has at most two child nodes, such a tree is called a binary tree;

The composition of a binary tree

  • A binary tree can be empty, meaning it has no nodes;
  • If a binary tree is not empty, it consists of a root node and two disjoint binary trees called its left subtree TL and its right subtree TR;

The five forms of binary trees

The figure above shows: an empty binary tree, a binary tree with only one node, a binary tree with only left subtree TL, a binary tree with only right subtree TR, and a binary tree with left and right subtrees.

Properties of binary trees

  • The maximal node tree of layer I of a binary tree is: 2^(I -1)^, I >= 1;
  • The maximum number of nodes in a binary tree with depth k is 2^k^ -1, k >= 1;
  • For any non-empty binary tree, if n0Is the number of leaves, n2Represents the number of non-leaf nodes whose degree is 2, then the two satisfy the relation: n0 = n2+ 1; As shown in the figure below: H, E, I, J and G are leaf nodes, with a total of 5; A, B, C and F are non-leaf nodes with degree 2, and the total number is 4; Meet n0 = n2Plus one.

Special binary trees

Perfect binary tree

A Perfect Binary Tree is also known as a Full Binary Tree. In a Binary Tree, except for the leaf node at the bottom layer, each node at the bottom layer has two child nodes, which constitutes a Perfect Binary Tree.

Perfect binary tree

Complete Binary Tree:

  • Except for the last layer of the binary tree, the number of nodes in other layers reaches the maximum.
  • Moreover, the leaf nodes of the last layer exist continuously from left to right, and only several leaf nodes on the right side are missing.
  • A perfect binary tree is a special perfect binary tree;

In the figure above, H is not a complete binary tree because it is missing its right child node.

Binary tree data storage

Common binary tree storage methods are arrays and linked lists:

Use an array

  • Full binary tree: Stores data from top to bottom and left to right.

node A B C D E F G H I
The serial number 1 2 3 4 5 6 7 8 9

The serial number of the left child node is equal to the serial number _ 2 of the parent node, and the serial number of the right child node is equal to the serial number _ 2 + 1 of the parent node.

  • Incomplete binary tree: An incomplete binary tree needs to be converted to a full binary tree to be stored as described above, which wastes a lot of storage space.

node A B C ^ ^ F ^ ^ ^ ^ ^ ^ M
The serial number 1 2 3 4 5 6 7 8 9 10 11 12 13

Use the list

The most common storage method of binary tree is linked list: each Node is encapsulated into a Node, which contains stored data, references of the left Node, and references of the right Node.

Binary search tree

Binary Search Tree (BST, Binary Search Tree), also known as Binary sort Tree and Binary Search Tree.

A binary search tree is a binary tree and can be null.

If it is not empty, the following properties are satisfied:

  • Condition 1: All keys of a nonnull left subtree are less than the key of its root node. For example, the key value of all non-empty left subtrees of node 6 in three is less than 6;
  • Condition 2: All keys of a nonnull right subtree are greater than the key of its root node; For example, the key value of all non-empty right subtrees of node 6 in three is greater than 6;
  • Condition 3: Left and right subtrees themselves are also binary search trees;

As shown in the figure above, tree 2 and tree 3 meet three conditions to be a binary tree, tree 1 does not meet condition 3 so it is not a binary tree.

Summary: The main characteristics of binary search trees are that smaller values are always stored on the left node, and relatively large values are always stored on the right node. This feature makes the query efficiency of binary search tree very high, which is the source of “search” in binary search tree.

Examples of binary search tree applications

Here is a binary search tree:

If you want to find data 10 in it, you only need to find 4 times, the search efficiency is very high.

  • The first time: 10 is compared with root node 9. Since 10 > 9, 10 is compared with the right child node 13 of root node 9.
  • Second: since 10 < 13, 10 next compares with the left child 11 of parent 13;
  • The third time: because 10 < 11, so 10 next compared with the left child of the parent 11 node 10;
  • Fourth time: since 10 = 10, the data 10 is finally found.

Select * from ‘array’ where ’10’ = ’10’; select * from ‘array’ where ’10’ = ’10’;

If it is a sorted array, you can use binary search: the first search is 9, the second search is 13, the third search is 15… . And what we found is that if you take the binary data and you represent it as a tree it’s a binary search tree. That’s why array dichotomy is so efficient.

Encapsulation of binary search trees

The binary search tree has four basic properties: the root of the node, the key in the node, the left pointer, and the right pointer.

Therefore, in addition to defining the root attribute in the binary search tree, you should also define a node inner class that contains the left, right, and key attributes in each node.

/ / the node class
class Node {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null; }}Copy the code

Binary search tree common operations:

  • insert(key)Insert a new key into the tree.
  • search(key)Look for a key in the tree, returning true if the node exists; Returns if it does not existfalse.
  • preOrderTraverseAll nodes are traversed in preorder traversal mode.
  • inOrderTraverseAll nodes are traversed in the in-order traversal mode.
  • postOrderTraverseAll nodes are traversed in post-order traversal mode.
  • minReturns the smallest value/key in the tree.
  • maxReturns the largest value/key in the tree.
  • remove(key)Removes a key from the tree.

Insert data

Implementation ideas:

  • Start by creating a node object based on the key passed in.
  • Then judge whether the root node exists. If not, use: this.root = newNode to directly take the newNode as the root node of the binary search tree.
  • Redefine an internal method if there is a root nodeinsertNode()Used to find insertion points.

Insert (key) code implementation

// Insert (key) Insert data
insert(key) {
  const newNode = new Node(key);

  if (this.root === null) {
    this.root = newNode;
  } else {
    this.insertNode(this.root, newNode); }}Copy the code

InsertNode () insertNode()

By comparing the two incoming nodes, you keep looking for a suitable place for the new node to be inserted until the new node is successfully inserted.

  • When newNode.key < node.key left lookup:

    • If the node has no left child node, insert it directly:

    • Case 2: insertNode() is recursively called when node has left child nodes, until newNode is successfully inserted without left child nodes. This case is no longer met, insertNode() is no longer called, and the recursion stops.

  • When newNode.key >= node.key looks right, it is similar to looking left:

    • If the node has no right child node, insert it directly:

    • Case 2: insertNode() is recursively called when node has right children until newNode is successfully inserted into a node with no right children passed into the insertNode method.

InsertNode (root, node) code implementation

insertNode(root, node) {

  if (node.key < root.key) { // Look to the left for insert

    if (root.left === null) {
      root.left = node;
    } else {
      this.insertNode(root.left, node); }}else { // Look to the right for insert

    if (root.right === null) {
      root.right = node;
    } else {
      this.insertNode(root.right, node); }}}Copy the code

Through the data

The tree traversal is not just for binary search trees, but for all binary trees. Since the tree structure is not a linear structure, there are many choices of traversal methods. The three common traversal methods of binary tree are:

  • Preorder traversal;
  • In order traversal;
  • Post-order traversal;

There is also sequence traversal, which is less used.

The first sequence traversal

The process of preorder traversal is:

First, the root node is traversed; Then, the left subtree is traversed; Finally, the right subtree is traversed;

As shown in the figure above, the nodes of A binary tree are traversed in the following order: A -> B -> D -> H -> I -> E -> C -> F -> G.

Code implementation:

// Order traversal (DLR around root)
preorderTraversal() {
  const result = [];
  this.preorderTraversalNode(this.root, result);
  return result;
}

preorderTraversalNode(node, result) {
  if (node === null) return result;
  result.push(node.key);
  this.preorderTraversalNode(node.left, result);
  this.preorderTraversalNode(node.right, result);
}
Copy the code
In the sequence traversal

Implementation idea: with the first order traversal principle is the same, but traversal order is not the same.

First, the left subtree is traversed; Then, the root (parent) node is traversed; Finally, the right subtree is traversed;

Process diagram:

The order of the output node should be: 3 – > 5 – > 6-7-8 – > > > 9-10-11-12 – > > > > 13-14-15-18 – > > > > 20 – > 25.

Code implementation:

// In order traversal (left root right LDR)
inorderTraversal() {
  const result = [];
  this.inorderTraversalNode(this.root, result);
  return result;
}

inorderTraversalNode(node, result) {
  if (node === null) return result;
  this.inorderTraversalNode(node.left, result);
  result.push(node.key);
  this.inorderTraversalNode(node.right, result);
}
Copy the code
After the sequence traversal

Implementation idea: with the first order traversal principle is the same, but traversal order is not the same.

First, the left subtree is traversed; Then, the right subtree is traversed; Finally, the root (parent) node is traversed;

Process diagram:

The order of the output node should be: 3 – > 6 – > 5-8-10 – > > > 9-7-12-14 – > > > > 13 to 18-25 – > > > 20 – > 15 – > 11.

Code implementation:

// Back order traversal (left and right root LRD)
postorderTraversal() {
  const result = [];
  this.postorderTraversalNode(this.root, result);
  return result;
}

postorderTraversalNode(node, result) {
  if (node === null) return result;
  this.postorderTraversalNode(node.left, result);
  this.postorderTraversalNode(node.right, result);
  result.push(node.key);
}
Copy the code
conclusion

The three traversal methods are distinguished by the order in which the root (parent) node is traversed. For example, the first order traversal first traversal the root node, the second order traversal root node, the last root traversal traversal.

To find the data

Find the maximum or minimum value

Finding the maximum value in a binary search tree is very simple. The minimum value is on the far left of the binary search tree, and the maximum value is on the far right. Just keep searching left/right to get the most value, as shown in the figure below:

Code implementation:

// min() obtain the binary search tree minimum value
min() {
  if (!this.root) return null;
  let node = this.root;
  while(node.left ! = =null) {
    node = node.left;
  }
  return node.key;
}

// Max () gets the maximum binary search tree value
max() {
  if (!this.root) return null;
  let node = this.root;
  while(node.right ! = =null) {
    node = node.right;
  }
  return node.key;
}
Copy the code
Find a specific value

It is also very efficient to find specific values in the binary search tree. Start from the root node and compare the key value of the node to be searched. If node.key < root, search left, if node.key > root, search right, until null is found or found. You can do it recursively or you can do it looping.

Code implementation:

// Search (key) looks for the same key in the binary search tree. Returns true if there is one, false if not
search(key) {
  return this.searchNode(this.root, key);
}

// Recursively
searchNode(node, key) {
  if (node === null) return false;
  if (key < node.key) {
    return this.searchNode(node.left, key);
  } else if (key > node.key) {
    return this.searchNode(node.right, key);
  } else {
    return true; }}// Through the while loop
search2(key) {

  let node = this.root;

  while(node ! = =null) {
    if (key < node.key) {
      node = node.left;
    } else if (key > node.key) {
      node = node.right;
    } else {
      return true; }}return false;

}
Copy the code

Delete the data

Implementation ideas:

Step 1: Find the node that you want to delete. If the node is not found, you do not need to delete it.

The parent variable is used to save its parent node. The isLeftChild variable is used to save whether current is the left node of the parent node. In this way, it is easy to change the direction of the node when deleting the node later.

let currentNode = this.root;
let parentNode = null;
let isLeftChild = true;

// Loop to find currentNode, parentNode, isLeftChild
while(currentNode.key ! == key) { parentNode = currentNode;// If less than, go left
  if (key < currentNode.key) {
    isLeftChild = true;
    currentNode = currentNode.left;
  } else {
    // Otherwise, search to the right
    isLeftChild = false;
    currentNode = currentNode.right;
  }

  // Return false if no equal nodes are found
  if (currentNode === null) {
    return false; }}Copy the code

Step 2: Delete the found node. There are three cases:

  • Delete the leaf node;
  • Delete a node that has only one child;
  • Delete a node with two children;
It is the leaf node that is deleted

The leaf node is deleted in two cases:

  • The leaf is also the root

    When the leaf node is the root node, as shown in the figure below, current == this.root, directly delete the root node: this.root = null.

  • Leaf nodes are not root nodes

    There are also two cases when the leaf node is not the root node, as shown in the figure below

    If current = 8, delete node 8 by: parent.

    If current = 10, delete node 10 with parent. Right = null;

    Code implementation:

    // 1, delete the leaf node
if (currentNode.left === null && currentNode.right === null) {
  if (currentNode === this.root) {
    this.root = null;
  } else if (isLeftChild) {
    parentNode.left = null;
  } else {
    parentNode.right = null;
  }

  // 2, delete a node that has only one child node
}
Copy the code
You delete a node that has only one child node

There are six conditions:

When current has a left child (current.right == null) :

  • In case 1, if current is the root node (current == this.root), for example, if this is node 11, run the following command to delete root node 11: this.root = current.left;

  • Parent.left = current.left == true; parent.left = current.left == true;

  • Case 3: the current to the parent node right child nodes of the parent (isLeftChild = = false), such as node 9, at this time by: parent. Right = current. Left, delete node 9;

Left = null when current has a right child:

  • In case 4, if the current node is the root node (current == this.root), for example, if the current node is 11, run the this.root = current.right command to delete root node 11.

  • Case 5: current to the parent node of the parent left child node (isLeftChild = = true), such as node 5, by this time: the parent, left = current. Right, delete node 5;

  • Case 6: current to the parent node right child nodes of the parent (isLeftChild = = false), such as node 9, by this time: the parent. Right = current. Right, delete node 9;

Code implementation:

// 2, delete a node that has only one child node
} else if (currentNode.right === null) { // currentNode contains only the left node
  //-- 2.1. CurrentNode only contains < left node >
  //---- 2.1.1, currentNode equals root
  //---- 2.1.2, parentNode.left equals currentNode
  //---- 2.1.3, parentNode.right equals currentNode

  if (currentNode === this.root) {
    this.root = currentNode.left;
  } else if (isLeftChild) {
    parentNode.left = currentNode.left;
  } else{ parentNode.right = currentNode.left; }}else if (currentNode.left === null) { // Only the right node exists in currentNode
  //-- 2.2. CurrentNode contains only the right node
  //---- 2.1.1 currentNode equals root
  //---- 2.1.1 parentNode.left equals currentNode
  //---- 2.1.1 parentNode.right equals currentNode

  if (currentNode === this.root) {
    this.root = currentNode.right;
  } else if (isLeftChild) {
    parentNode.left = currentNode.right;
  } else {
    parentNode.right = currentNode.right;
  }
Copy the code
You are deleting a node that has two child nodes

This situation is very complicated, first of all, according to the following binary search tree, discuss such a problem:

Deleting a Node 9

On the premise that the original binary tree remains a binary search tree after node 9 is deleted, there are two methods:

  • Method 1: Select an appropriate node from the left subtree of node 9 to replace node 9, so that node 8 meets the requirements.
  • Method 2: Select an appropriate node from the right subtree of node 9 to replace node 9, so that node 10 meets the requirements.

Deleting a Node 7

On the premise that the original binary tree remains a binary search tree after node 7 is deleted, there are also two methods:

  • Method 1: Select an appropriate node from the left subtree of node 7 to replace node 7, so that node 5 meets the requirements.
  • Method 2: Select an appropriate node from the right subtree of node 7 to replace node 7, so that node 8 meets the requirements.

Delete a node. 15

On the premise that the original tree binary tree is still a binary search tree after node 15 is deleted, there are also two methods:

  • Method 1: Select an appropriate node from the left subtree of node 15 to replace node 15, so that node 14 meets the requirements.
  • Method 2: Select an appropriate node from the right subtree of node 15 to replace node 15, so that node 18 meets the requirements.

I believe you have found the pattern!

Rule summary: If the node to be deleted has two child nodes, or even child nodes have child nodes, in this case, it is necessary to find a suitable node from the child nodes below the node to be deleted to replace the current node.

If current represents the node to be deleted, the appropriate node is:

  • The node slightly smaller than current in the left subtree of current, that is, the maximum value in the left subtree of current;
  • The node slightly larger than current in the current right subtree, that is, the minimum value in the current right subtree;
Precursor & successor

In a binary search tree, these two special nodes have special names:

  • A node slightly smaller than current is called the precursor of the current node. For example, node 5 in the figure below is the precursor of node 7;
  • A node slightly larger than current is called the successor of the current node. For example, node 8 in the figure below is the successor of node 7;

To find the successor of the node current that needs to be deleted, the minimum value needs to be found in the right subtree of current, that is, the right subtree of current has been traversed to the left to find;

When searching for the precursor, it is necessary to search for the maximum value in the left subtree of current, that is, to search all the way to the right in the left subtree of current.

We will only discuss the case of finding a successor to current. The principle of finding a precursor is the same and will not be discussed here.

Code implementation:

  // 3, delete a node with two child nodes
  } else {

    // 1, find the next node
    let successor = this.getSuccessor(currentNode);

    // 2. Check whether it is the root node
    if (currentNode === this.root) {
      this.root = successor;
    } else if (isLeftChild) {
      parentNode.left = successor;
    } else {
      parentNode.right = successor;
    }

    // 3. Change the subsequent left node to the left node to be deletedsuccessor.left = currentNode.left; }}// Get the next node, that is, start to the right of the node to be deleted and look for the smallest value
getSuccessor(delNode) {

  // Define a variable to hold the follow-up to be found
  let successor = delNode;
  let current = delNode.right;
  let successorParent = delNode;

  // Loop to find the right subtree node of current
  while(current ! = =null) {
    successorParent = successor;
    successor = current;
    current = current.left;
  }

  // Determine if the next node found is directly the right of the node to delete
  if(successor ! == delNode.right) { successorParent.left = successor.right; successor.right = delNode.right; }return successor;
}
Copy the code
Complete implementation
// Delete the node
remove(key) {

  let currentNode = this.root;
  let parentNode = null;
  let isLeftChild = true;

  // Loop to find currentNode, parentNode, isLeftChild
  while(currentNode.key ! == key) { parentNode = currentNode;// If less than, go left
    if (key < currentNode.key) {
      isLeftChild = true;
      currentNode = currentNode.left;

    } else {  // Otherwise, search to the right
      isLeftChild = false;
      currentNode = currentNode.right;
    }

    // Return false if no equal nodes are found
    if (currentNode === null) {
      return false; }}// 1, delete the leaf node
  if (currentNode.left === null && currentNode.right === null) {

    if (currentNode === this.root) {
      this.root = null;
    } else if (isLeftChild) {
      parentNode.left = null;
    } else {
      parentNode.right = null;
    }


    // 2, delete a node that has only one child node
  } else if (currentNode.right === null) { // currentNode contains only the left node
    //-- 2.1. CurrentNode only contains < left node >
    //---- 2.1.1, currentNode equals root
    //---- 2.1.2, parentNode.left equals currentNode
    //---- 2.1.3, parentNode.right equals currentNode

    if (currentNode === this.root) {
      this.root = currentNode.left;
    } else if (isLeftChild) {
      parentNode.left = currentNode.left;
    } else{ parentNode.right = currentNode.left; }}else if (currentNode.left === null) { // Only the right node exists in currentNode
    //-- 2.2. CurrentNode contains only the right node
    //---- 2.1.1 currentNode equals root
    //---- 2.1.1 parentNode.left equals currentNode
    //---- 2.1.1 parentNode.right equals currentNode

    if (currentNode === this.root) {
      this.root = currentNode.right;
    } else if (isLeftChild) {
      parentNode.left = currentNode.right;
    } else {
      parentNode.right = currentNode.right;
    }


    // 3, delete a node with two child nodes
  } else {

    // 1, find the next node
    let successor = this.getSuccessor(currentNode);

    // 2. Check whether it is the root node
    if (currentNode === this.root) {
      this.root = successor;
    } else if (isLeftChild) {
      parentNode.left = successor;
    } else {
      parentNode.right = successor;
    }

    // 3. Change the subsequent left node to the left node to be deletedsuccessor.left = currentNode.left; }}// Get the next node, that is, start to the right of the node to be deleted and look for the smallest value
getSuccessor(delNode) {

  // Define a variable to hold the follow-up to be found
  let successor = delNode;
  let current = delNode.right;
  let successorParent = delNode;

  // Loop to find the right subtree node of current
  while(current ! = =null) {
    successorParent = successor;
    successor = current;
    current = current.left;
  }

  // Determine if the next node found is directly the right of the node to delete
  if(successor ! == delNode.right) { successorParent.left = successor.right; successor.right = delNode.right; }return successor;
}
Copy the code

Balanced tree

The defect of binary search tree: when the data inserted is ordered, the depth of binary search tree will be too large. For example, the original binary search tree consists of 11, 7 and 15, as shown in the figure below:

When inserting a set of ordered data: 6, 5, 4, 3, 2, it will become a search binary tree with too much depth, which will seriously affect the performance of the binary search tree.

The balanced tree

  • For a good binary search tree, the data should be evenly distributed from left to right.
  • However, after the insertion of continuous data, the distribution of data in the binary search tree becomes uneven, which is called an unbalanced tree.
  • For a balanced binary tree, the efficiency of insert/find and so on is order log n.
  • For a non-balanced binary tree, it is equivalent to writing a linked list, and the lookup efficiency becomes O(n).

The balance of the tree

In order to manipulate a tree in order log n time, we need to ensure that the tree is always in balance:

  • At least for the most part it’s balanced, and the time complexity is close to order log n;
  • This requires that the number of descendants to the left of each node in the tree should, as far as possible, be equal to the number of descendants to the right;

Common balance tree

  • AVL tree: One of the earliest balanced trees, it keeps the tree balanced by storing an extra data at each node. Since the AVL tree is a balanced tree, its time complexity is also order log n. However, its overall efficiency is not as good as the red-black tree, and it is less used in development.
  • Red-black tree: The same feature that keeps the tree balanced is order log n. When performing insert/delete operations, the performance is better than AVL trees, so most applications of balanced trees are red black trees.

If it helps, support the author with a like at ❤️

Album series

  • Learn JavaScript data structures and algorithms from 0
  • Learn JavaScript data structures and algorithms from 0 (2) Arrays
  • Learn JavaScript data structures and algorithms from 0 (3) stack
  • Learn JavaScript data structures and algorithms from 0 (4) queue
  • Learning JavaScript data structures and algorithms from 0 (5) priority queues
  • Start from 0 to learn JavaScript data structures and algorithms (6) unidirectional linked lists
  • Start from 0 to learn JavaScript data structures and algorithms (7) two-way linked lists
  • Learn JavaScript data structures and algorithms (8) set from 0
  • Learn JavaScript data structures and algorithms from 0 (9) dictionary
  • Start from 0 to learn JavaScript data structures and algorithms (10) hash tables