preface
This article mainly explains recently has been heard of the red black tree, see what is the fairy ghost.
Binary tree
A tree that satisfies the following two conditions is a binary tree:
- The Tree itself is an Ordered Tree (if the sub-trees of each node in the Tree are regarded as Ordered from left to right (that is, they cannot be exchanged), the Tree is called an Ordered Tree).
- The degree of each node contained in the tree cannot exceed 2, that is, it can only be 0, 1 or 2;
A Binary tree is a tree with at most two branches per node (i.e., no node with a branching degree greater than 2). Branches are usually referred to as “left subtrees” or “right subtrees”.
Binary search tree
Before we get to red-black trees, we have to look at what binary search trees are.
Wikipedia definition
A Binary Search Tree (English: Binary Search Tree), also known as a Binary Search Tree, ordered Binary Tree or sorted Binary Tree, is an empty Tree or a Binary Tree with the following properties
- If the left subtree of any node is not empty, the values of all nodes in the left subtree are less than the values of its root node.
- If the right subtree of any node is not empty, the value of all nodes in the right subtree is greater than or equal to the value of its root node.
- The left and right subtrees of any node are binary search trees respectively.
Here is to understand
The following figure shows how to find the node whose value is 29.
- View root node 41
- Because 41> 29, look at 41’s left child 20
- Since 20 is less than 29, we look at child 29 to the right of 20 and find that it is the node we want to look at.
The degradation of
Binary lookup trees have a very serious problem. If data is inserted from large to small, or from small to large, the binary lookup tree can degenerate into a single-linked list, commonly known as “lame”.
-
Left cripple: for example, insert data in order {5,4,3,2,1} (from large to small), as shown below:
-
Right cripple: for example, insert data {1,2,3,4,5} (from small to large), as shown below:
In order to solve this problem, there are some solutions, namely balance, which can make the tree to balance, this kind of self-balancing tree is called balance tree.
Balanced tree
A Balance Tree (BT) is one in which the height difference of the subtrees of any node is less than or equal to 1. There are AVL tree (binary balanced search tree), B tree (multi-path balanced search tree, 2-3 tree, a kind of 2-3-4 tree), red black tree and so on.
AVL tree
AVL trees (named by the initials of inventors Adelson-Velsky and Landis) are balanced trees where the height difference between the two subtrees of any node is no more than 1. Also known as
Self-balanced binary search tree.
The AVL tree can solve the right cripple problem in the binary search tree above. For example, if the insertion data is {1,2,3,4,5} (from small to large), then it is shown as follows:
AVL tree will adjust the structure that does not conform to the height difference, so that the binary tree tends to be balanced.
2-3 tree
The basic concept
A 2-3 tree is a self-balancing tree where each node with child nodes (internal node, internal node) has either two child nodes and a data element, or three child nodes and two data elements, and all leaf nodes have the same height.
In simple terms, the non-leaf nodes of a 2-3 tree have two or three forks, so it is easier to understand what is called a 2-3 tree.
In other words, a node with two children and one data element is called a 2-node, and a node with three children and two data elements is called a 3-node, so the whole tree is called a 2-3 tree.
All leaf points are on the same level of the tree, the same height.
Properties 1. Properties of binary search tree 2. Nodes can store one or two elements 3. Each node has two or three child nodes
Create rules for 2-3 trees
The insert
- Inserts elements into the 2-node
- Inserts elements into a tree with only one 3-node
The 2-3-4 trees
meaning
- 2-node: contains two child nodes and a data element
- 3-node: Contains three child nodes and a data element
- 4-node: Contains four child nodes and a data element
A two-three-four tree, where every non-leaf node has either two or three or four nodes, and it’s self-balancing, so it’s called a two-three-four tree.
The rules
Rule 1. When a new node is added, it is not added to the empty position, but to the last leaf node. Rule 2. Four nodes can be decomposed into a tree consisting of three 2-nodes, and the root node of the new tree needs to fuse upward with the parent node
The insert
- The original two-three-four tree
- For the 2-3-4 tree in the figure above, insert a node 17. Due to rule 1, node 17 will not join the subtree of node [16,18,20], but fuse with this node.
- Due to rule 2, node [16,17,18,20] is a 4-node node. This node is disassembled into a new tree, and 18 is split as the root node of the subtree.
- At this point, the tree is temporarily out of balance, and we need to fuse the root node of the split subtree upward.
- Similarly, due to rule 2, node [6,10,14,18] is a four-node node. This node is disassembled into a new tree, and 14 is taken as the root node of the subtree to split, thus completing the construction of a 2-3-4 tree.
So, we had two-three-four trees, two-three-five trees, two-three-four-five trees, two-three-four-five… What about the existence of a -n tree? In fact, there is a name for this group of trees: B-trees.
B tree
A B-tree is a tree that allows a node to have more than two children, and at the same time, is self-balanced, and leaves are all the same height.
So, in order to better distinguish what kind of tree a B-tree belongs to, we give it a new attribute: Degree: how many arrows a node can have pointing to other nodes.
A b-tree with degree 3 means that a node has at most three child nodes, which is the definition of a 2-3 tree.
You have a b-tree of degree 4, which means that a node has at most four children, which is the definition of a 2-3-4 tree.
Example diagram of a B-tree of degree 4:
Red and black tree
Introduction to the
R-b Tree, full name is red-black Tree, also known as “Red Black Tree”, it is a special binary search Tree. Red-black trees have memory bits on each node to indicate the color of the node, which can be Red or Black.
How to understand red-black trees
A classic red-black tree is shown below (omitting NIL nodes whose leaves are all black)
As shown in Figure 2, compare the red-black tree with the two-three-four tree mentioned above, and see if it can be found that the red-black tree is a two-three-four tree.
-
Each node is either black or red.
-
The root node is black.
-
Each leaf node (NIL) is black. [Note: leaf nodes are NIL or NULL leaf nodes!]
-
If a node is red, its children must be black. Since every node of red-black tree is transformed from 2-3-4 tree, red nodes cannot appear two times in a row, or there will be four nodes, which leads to the violation of Rule 2. And every black node in a red-black tree is either the middle of the three nodes, or one of the two nodes.
-
All paths from a node to its descendants contain the same number of black nodes. Reason: Red-black tree these black nodes in the two-three-four tree represent a two-three-four tree with 1 node, and the two-three-four tree is the same subtree depth is the same, balanced, so all the paths from a node to the descendants of the node contain the same number of black nodes. (As shown in the figure below, blue represents black nodes)
Note:
- Leaf nodes in property (3) are nodes that are NIL or null only.
- Feature (5) ensures that no path is twice as long as any other. Therefore, red-black trees are relatively nearly balanced binary trees.
- Although red black tree is a binary search tree in essence, it adds coloring and correlation properties on the basis of the binary search tree to make the red black tree relatively balanced, so as to ensure that the search, insert, delete time complexity of red black tree is O(log n) at worst.
As shown in the above example, we only need to treat red-black trees as 2-3-4 trees and change the corresponding colors or perform left-right rotation operations to achieve the goal of making red-black trees balanced.
How do I preserve the structure of a red-black tree
When inserting a new node, how can we ensure that the structure of a red-black tree still conforms to the above five properties?
Tree rotation is divided into left and right, the following with the help of the figure to introduce the left and right rotation of the two operations.
left-handed
Original state
The process diagram
The end of the figure
As you can see in the figure above, when we do a left-handed operation on some target node E, we assume that its right child S is not NIL. Left-handed rotation takes place with the chain between S and E as a “pivot”, which makes S the new root of the subtree and the left child of S the right child of E.
Right hand
Original state diagram
The process diagram
The end of the figure
Just like left-handed, when we do a right-handed operation on some target node, S, we’re going to assume that its right child, S, is not NIL. Left-handed rotation takes place with the chain between S and E as a “pivot”, which makes S the new root of the subtree and the left child of S the right child of E.
application
Red-black tree is widely used, mainly to store ordered data, its time complexity is O(logn), very high efficiency. For example, TreeSet and TreeMap in Java collections, set and map in C++ STL, and Linux virtual memory management are all implemented through red-black trees.
The resources
VisuAlgo – Dynamic Visualization of Data Structures and Algorithms (Chinese)
The Beauty of Data Structures and Algorithms
Red/Black Tree Visualization
(3 messages) teach you a preliminary understanding of red black tree _ structure method algorithm -CSDN blog
Understand the origin of red black trees, understand the nature of red black trees
Linux learning 21, Principles and characteristics of self-balancing binary tree and red black tree – liu Cong’s blog
Animation | what is 2-3 tree? – zhihu