Red-black tree properties, advantages, and insertion introduction

Learning: In this article, we will learn three main points

  • Introduction to red-black trees
  • Red-black trees have advantages
  • Red-black tree insertion logic

Red and black tree

A red-black tree is a self-equilibrating red-black binary tree. The red-black tree satisfies all attributes of the binary search tree, and some additional attributes are added to the red-black tree. Each node of the red-black tree is black or red, and its height is O(logn), where n is the number of nodes in the tree

Properties of red-black trees

  • The root node is always black (it could have been red, but the algorithm chose a random rule)
  • The empty children of each node in a red-black tree represent black
  • The children of the red node must be black, and the parent of the red node must also be black
  • All leaf nodes have the same black node depth
  • Each simple path has the same number of black nodes from the root node to the leaf node

Red black tree display

  • This is a binary search tree
  • The root node is black
  • The children of the red node must be black
  • All paths from the root to the external node contain the same black nodes such as 75-90-80-88-NULL and 75-40-30-NULL contain the same three nodes

Advantages of red-black trees

  • Red-black trees are relatively efficient when we insert and delete data relatively frequently
  • Red-black trees are self-equilibrating and all operations are order logn at most.
  • No matter how it changes, there are only red and black constants, right

Insert data

The data that needs to be inserted should be marked red not every node that is inserted will cause an imbalance, but if it does, it needs to be removed, and the deletion operation depends on the previous layout of the tree and is usually used when an imbalance occurs

  1. Relabel color
  2. rolling

To better understand the insertion operation, let’s assume that A. u is the latest node to be inserted. B. P is the parent node of u. C. g is the grandfather node of U. D. Un is the uncle node of U

The tree must be an equilibrium number until a new node is inserted, but when we insert a new node we break the equilibrium, so we switch colors first. If the equilibrium has not been removed, we roll the nodes to make the tree reach equilibrium

Case 1

The occurrence of imbalance is mainly related to the uncle node. If the uncle node is red, there are four scenarios to deal with, and the imbalance can be deleted by changing the color again

1. LRr imbalance

Since P is the left node of G and u is the right node of P, it is called left-right imbalance. The reason for the imbalance is that the inserted nodes must be red, but the red nodes cannot be adjacent, so one of them needs to turn black, so the color needs to be re-marked

  • Change the color of p to black
  • Change the color of Un to black
  • If g is not the root, change g to red

Pay attention to If g is a root node does not need to change color Why don’t the three steps to remove balance, because the transformation p and the Un can ensure g as the root node of the two lines of black node number is the same, but if g is not the root node, then black + 1 nodes in every line, actually need to minus 1, so the color of the g need to become red, after three cases similar

2. LLr imbalance
Since P is the left node of G and u is the left node of P, it is called left-right imbalance. The reason for the imbalance is that the inserted nodes must be red, but the red nodes cannot be adjacent, so one of them needs to turn black, so the color needs to be re-markedCopy the code

  • Change the color of p to black
  • Change the color of Un to black
  • If g is not the root, change g to red
3. RRr imbalance

Since P is the right node of G and u is the right node of P, it is called left-right imbalance. The reason for the imbalance is that the inserted nodes must be red, but the red nodes cannot be adjacent, so one of them needs to turn black, so the color needs to be re-marked

Remove the left and right imbalance by following the steps below

  • Change the color of p to black
  • Change the color of Un to black
  • If g is not the root, change g to red
4. RLr imbalance

Since P is the right node of G and u is the left node of P, it is called left-right imbalance. The reason for the imbalance is that the inserted nodes must be red, but the red nodes cannot be adjacent, so one of them needs to turn black, so the color needs to be re-marked

  • Change the color of p to black
  • Change the color of Un to black
  • If g is not the root, change g to red

Case 2

The imbalance also occurs when the UNCLE node is black, and the following four scenarios will be mentioned, where the imbalance of LR imbalance LL imbalance RR imbalance RL imbalance can be removed by moving the node

LL and RR imbalances can be removed by the following two steps

A. p scroll takes up position G, g scroll takes up position Un, B. p is re-labeled black, g is re-labeled red

This logic is also easy to understand, mainly to ensure that the number of black nodes in the two branches with G as the root node does not change, similar in the following

LR and RL imbalances can be removed by the following two steps

A. u scrolls twice to occupy the position of G, and G becomes a child node of U. B. Recolabinate U as black, g and P as red

Remind:

The default color of the inserted node must be red. If the Un node does not exist, follow the logic of the black node

[www.includehelp.com/data-struct…]