First of all, let’s take a look at the structure of the red-black tree, as shown in the figure:
(Learning video sharing: java teaching video)
The structural characteristics of the red-black tree:
(1) Each node is either black or red.
(2) The root node is black.
(3) Each leaf node (NIL) is black. [Note: The leaf node here refers to the leaf node that is empty (NIL or NULL)! ]
(4) If a node is red, its child nodes must be black.
(5) All paths from a node to the node’s descendant nodes contain the same number of black nodes.
Why use red-black trees?
1. First of all, red-black trees do not meet the balance conditions of AVL trees, that is, binary search trees in which the heights of the left subtree and right subtree of each node differ by at most 1. However, it is proposed to add colors to nodes. Red-black trees use non-strict balance to reduce the number of rotations when adding or deleting nodes. Any imbalance will be resolved within three rotations, while AVL is a strictly balanced tree, so when adding or deleting nodes, When it comes to nodes, depending on the situation, the number of rotations is more than that of the red-black tree. Therefore, the insertion efficiency of red-black trees is higher
(Recommendations for more related interview questions:java interview questions and answers)
2. Red-black trees can perform O( Log2 (n)) time complexity for search, insertion, and deletion operations
3. Simply put, the red-black tree is to solve the shortcomings of the binary search tree, because the binary search tree in some cases will degenerate into a linear structure.
Comparison and selection of red-black tree and balanced tree
1. The balanced tree structure is more intuitive, and the reading performance is higher than that of the red-black tree; the performance of adding and deleting nodes to restore balance is not as good as that of the red-black tree. Black tree
2. The reading performance of red-black tree is not as good as that of balanced tree; the performance of adding and deleting nodes to restore balance is worse than balanced tree
Usage scenarios of red-black tree:
TreeMap, Both TreeSet and HashMap after JDK1.8 use red-black trees at the bottom layer.
Related recommendations: java introductory tutorial
The above is the detailed content of java interview-red-black tree. For more information, please follow other related articles on the PHP Chinese website!