This is the 28th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Don’t you know that everyone in the front end knows about red black trees? Bengua, I’ve heard it before, but it’s not quite clear what it does. After knowing the balanced binary tree, AVL tree, now we have come to this node, we must look at the “red black tree”!

Today is not Arbor Day, but still to plant trees! ðŸŒģ ðŸŒģ ðŸŒģ

Idle talk less Syria, blunt! āļ‡ āļ‡, _, ()

Algorithms column on tree portals:

  • “Judged-balanced binary Trees for The Sun Arch Algorithm”
  • AVL Tree Rotation and JS Implementation, Balancing tree Branching ~
  • Nice Diagram for Solving the Problem of Data Stream Medians with Large and small Heaps

Let’s take a look at why binary search trees are born!

As we all know: array is suitable for static operation (O(1)) of query, but not for dynamic operation (O(n)) of delete and insert, while linked list is suitable for delete and insert, and the query efficiency is relatively slow.

Binary search trees are designed to balance the gap between static operations (arrays) and dynamic operations (linked lists)

Features:

  • If the left subtree of any node is not empty, the value of the left subtree is less than that of the root node.
  • If the right subtree of any node is not empty, the value of the right subtree is greater than that of the root node.
  • The left and right subtrees of any node are binary search trees respectively.
  • No nodes with equal keys;

In order to avoid the extreme situation as shown below:

Binary search trees must be “balanced” to prevent the number of layers on one side being too deep;

The AVL tree (balanced binary tree) was born!

The practice complexity is increased to O(log2n);

AVL tree is a binary search tree with equilibrium condition. The height of left and right subtrees is less than 1. It is strictly balanced binary tree.

Whether we perform an insert or delete operation, as long as the above conditions are not met, we need to balance by rotation, which is very time-consuming;

From this, we can know that AVL tree is suitable for less times of insertion and deletion, but more searches.

In order to balance “balance” and “rotation time”, the “red black tree” was born!!

A red-black tree is a weakly balanced binary tree! By limiting how nodes can be colored on any path from root to leaf, ensure that no path is twice as long as any other;

Compared with the strict AVL tree, it has fewer rotations. Correspondingly, rotation takes less time;

Red-black trees have a wide range of applications:

  • In C++ STL,map and set are implemented using red-black trees.
  • Linux process scheduler Completely Fair Scheduler uses red-black tree to manage the process control block. The virtual memory area of the process is stored in a red-black tree. Each virtual address area corresponds to a node of the red-black tree.
  • The implementation of IO multiplexing epoll uses red-black tree to organize and manage SOCKFD to support fast add, delete, change and search.
  • In NgniX, red-black tree is used to manage timer, because red-black tree is orderly, it can quickly get the timer with the smallest distance to the current.
  • Implementation of TreeMap in Java;

Red and black is to use non-strict balance in exchange for the reduction of rotation when adding and removing nodes, any imbalance will be resolved within three rotations ~~

For more information, it is recommended to read b’s answer above:

OK, this article only shares the origin of the birth of red black tree, and some conceptual things, the subsequent implementation in JS and so on;

In fact, the concept of space for time can be seen in many places, functional programming is more memory intensive, also space for time; Amazing ~ ~

Writing is not easy, please encourage 👍👍👍

I am Anthony Nuggets, the public account of the same name, every day a pawn, dig a gold, goodbye ~