Qin Chao is nearing the end of his algorithm Training camp. Through this period of learning and training, he has further deepened his cognition of data structure and algorithm. From the curDS of business systems down to the underlying data structures and algorithms, one of the biggest impressions I get from looking back is that these data structure and algorithm scientists/experts are great.

I’m going to spend some time today summarizing what we learned about trees. Readers need to note that there is only a brief introduction and summary of several “trees” mentioned below. Detailed reasoning and proof suggest that interested readers can consult the detailed information, so that this paper does not have to spend a lot of space copying the papers of various scientists. Tip: Some of the hyperlinks in this article require your own science web tools to access.

A Tree (Tree)

  • Root: indicates the Root node
  • Parent Node: indicates the Parent Node
  • Child Node: indicates the Child Node
  • Left Node: indicates a leaf Node
  • Sub – tree: subtree

Binary Tree

Each parent node of a binary tree has a maximum of two child nodes, which can be traversed in the following three order:

1. Pre-order: root -> left -> right

// sample code
public void preorder(List<Integer> res, Node root) {
    // terminator
    if (root == null) return;
    
    // business
    res.add(root.val);
    preorder(res, root.left);
    preorder(res, root.right);
}
Copy the code

2. In-order: left -> root -> right

// sample code
public void preorder(List<Integer> res, Node root) {
    // terminator
    if (root == null) return;
    
    // business
    preorder(res, root.left);
    res.add(root.val);
    preorder(res, root.right);
}
Copy the code

3. Post-order: left -> right -> root

// sample code
public void preorder(List<Integer> res, Node root) {
    // terminator
    if (root == null) return;
    
    // business
    preorder(res, root.left);
    preorder(res, root.right);
    res.add(root.val);
}
Copy the code

Binary Search Tree

A Binary search Tree, also called a Binary search Tree, Ordered Binary Tree, Sorted Binary Tree, is an empty Tree or a Binary Tree with the following properties:

  1. The left subtreeAll the nodesAre smaller than the value of its root node;
  2. The right subtreeAll the nodesIs greater than the value of its root node;
  3. And so on: the left and right subtrees are also binary search trees (this is repeatability).

Note: Order traversal in a binary search tree results in ascending order.

Now let’s think about this picture, and figure out what is the total time complexity of the red nodes?The total time complexity of finding the red node in the binary search tree above is O(log2N), where 2 is the base and N is the number of nodes.

If the extreme case shown below is reduced to a linear structure, what is the time complexity of the bottom node?In the linear structure above, it is found that the time complexity of the bottommost node is O(N), where N is the number of nodes.

It can be concluded from the above phenomenon that it is necessary to ensure the two-dimensional dimension and balance the left and right subtree nodes.

The wikipedia self-balancing Binary Search Tree provides a detailed look at some of the trees that are balancing the binary search tree.

  • 2–3 tree
  • AA tree
  • AVL tree
  • B-tree
  • Red – black tree
  • Scapegoat tree
  • Splay tree
  • Tango tree
  • Treap
  • Weight-balanced tree

AVL tree

Each node of an AVL tree has its balance factor, which determines whether the subtree is to be balanced by rotation operations (there are four rotation operations).

Balance Factor: The height of the left subtree of a parent node minus the height of its right subtree (sometimes the right subtree minus the left). The equilibrium factor has three values, namely -1, 0 and 1. If a node’s balance factor does not belong to one of these three values, it and its subtrees need to be rotated.

The figure below is an AVL tree with green numbers representing the nodesBalance factor.

When adding a node of value 14, the value of the treeBalance factorChange to the following figure.

When adding a node of value 3, the value of the treeBalance factorChange to the following figure.Of the node whose value is 10Balance factorIs not- 1.0.1One of them, but instead2 -, you need to rotate it and its subtrees.

How do I rotate? First of all, four kinds of rotation will be introduced, and then the above picture will be used to specify which rotation method.

1. Left-handed

When the state of the subtree is right-right subtree (a parent node has only a single right subtree, and the right subtree also has only a single right subtree), left-rotation is performed on it, as shown in the figure below (the left is the state of right-right subtree, and the right is the rotated state).

2. Right

When the subtree state is left-left subtree (a parent node has only a single left subtree, and the left subtree also has only a single left subtree), it is right-rotated, as shown in the figure below (the left is the state of left-left subtree, and the right is the rotated state).

3. Turning around

When the state of the subtree is left and right subtree (a parent node has only a single left subtree, and the left subtree has only a single right subtree), it is rotated left and right, as shown in the following two figures.

First, left-spin the left and right subtrees to make them left and left subtrees.

And then you rotate the left and left subtrees right.

4. The right left

When the subtree state is right-left subtree (a parent node has only a single right subtree, and the left subtree has only a single left subtree), right-left rotation is performed on it, as shown in the following two figures.

First, you rotate the right-left subtree to make it a right-right subtree.

And then you left-handed rotate the right and right subtrees.

The diagram of the four rotation operations described above does not show the subtree. With subtree rotationLink 1/Link 2Please refer to the diagram below.

Rotation operation example number 1

After describing the four rotation operations, I return to the AVL tree mentioned earlier: “When adding a node of value 3, the value of the treeBalance factorAs shown below.”Of the node whose value is 10Balance factorIs not- 1.0.1One of them, but instead2 -, you need to rotate it and its subtrees.

Since the node with log value of 10 belongs to the state of left-left subtree, it needs to be right-rotated, as shown in the following figure.

As can be seen from the diagram of belt tree rotation above, the subtree (8) of the node with value 5 should be mounted under the node with value 10 after rotation. The result of the rotation is shown below.

Rotation operation example 2

An AVL treeBalance factorThe diagram below.

When the node with value 15 is added, theBalance factorChange to the following figure.At this point, the value of the node is 9 and the value of the node is 7Balance factorIs not- 1.0.1One of them, but instead+ 2, you need to rotate it and its subtrees.

We rotate the node with a higher number of layers and a value of 9, which belongs to the state of left and right subtree, so we need to rotate it left and right. First, we rotate it right, as shown in the following two figures.

The result of dextral supination is shown below.

And then you rotate it to the left, in the following two pictures.

The result of left supination is shown below.

AVL tree summary

  1. It’s a balanced binary tree;
  2. Balance factor = {-1, 0, 1};
  3. Four rotation operations.

Due to the data structure of AVL tree, the height difference between left and right subtrees of each node is no more than 1, and the time complexity of extreme situations is very close to O(log2N), so its query efficiency is relatively high. However, this also brings some disadvantages: nodes need to store additional information (balance factor) and adjust frequently, hence the red-black tree.

Red and black tree

Red-black Tree is an approximately balanced BinarySearch Tree, which can ensure that the height difference between the left and right subtrees of any node is less than twice. Specifically, red-black trees are binary search trees that satisfy the following conditions:

  • Each node is either red or black
  • The root node is black
  • Each leaf node (NIL node, empty node) is black.
  • You can’t have two red nodes next to each other
  • All paths from any node to each of its leaves contain the same number of black nodes.

Key property: The longest possible path from the root node to the leaf node is no more than twice the shortest possible path.

Finally, there is an overview and comparison of AVL tree and red-black tree, as shown in the figure below.

  • AVL trees have higher query efficiency than red-black trees because AVL trees are more strictly balanced. The height difference between the left and right subtrees of the AVL tree mentioned above is no more than 1, and the longest possible path from the root node to the leaf node of a red-black tree is no more than twice the shortest possible path.
  • Red-black trees have higher insertion and deletion efficiency than AVL because red-black trees are approximately balanced trees. AVL tree if add/remove nodes becauseBalance factorFor more rotation operations.
  • AVL trees store more information than red-black trees, so AVL trees consume more space than red-black trees. You want to deposit AVLBalance factorAnd the height of the tree, and the red-black tree only has to store a bit to store 0 or 1 to indicate whether it’s black or red.
  • Red-black trees are commonly used in high-level languages (Java, C++…) There are more MAP structures and more AVL trees in the database. Because according to the above conclusion, if there are a lot of read operations or half of read/write operations, use red-black trees, so there are more maps in high-level languages. Databases tend to do more reads than writes, so AVL trees are generally used.