Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

Principle and implementation of red black tree

DeusJin 2021-04-06 11:12:04 阅读数:8 评论数:0 点赞数:0 收藏数:0

Red and black trees

  1. Nodes are red or black .
  2. The root node is black .
  3. Each leaf node is a black, empty node ( A leaf node is an empty leaf node ).
  4. The two children of each red node are black ( You cannot have two consecutive red nodes on all paths from each leaf to the root ).
  5. All paths from any node to each of its leaves contain the same number of black nodes .

1. data structure

class TreeNode{
private Boolean color;
private int val;
private TreeNode left;
private TreeNode right;
private TreeNode parent;
get,set...
}
class RBTree{
public boolean add(int val){...}
public boolean delete(int val){...}
public void display(){...}
}

2. Left and right rotation

2.1 left-handed

2.2 Right hand

3. Insert

  • Newly inserted node (newNode) In red .

  • Insert according to the binary search tree insertion rule .

  • Discussion by situation The following situation is basically to maintain the characteristics of the red black tree mentioned above 4 Hete 5

    1、 if newNode Root node , It turns black , The insertion is complete , return true.

    2、 if newNode The parent node is black , The insertion is complete , return true.

    3、 As shown in the figure below , if newNode The parent node is red , And uncle node exists and is red , The parent node and uncle node turn black , Grandfather node turns red ,newNode = Grandfather node .

    4、 As shown in the figure below , if newNode The parent node is red , Uncle node does not exist or is black , And newNode For the father node right child , The parent node is the grandfather node and the left child node , Then rotate left with the parent node as the axis , Entry situation 6.

5、 As shown in the figure below , if newNode The parent node is red , Uncle node does not exist or is black , And newNode For the father, for the child , The parent node is the grandfather node and the right child node , Then turn right with the parent node as the axis , Entry situation 7

6、 Here's the picture , At this time, the grandfather node is used as the axis to rotate right , Change the grandfather node to red ,newNode Black .

7、 Here's the picture , At this time, the grandfather node is used as the axis for left rotation , Change the grandfather node to red ,newNode Black .

4. Delete

Discussion by situation ( It's the same as inserting , The following situation is basically to maintain the characteristics of the red black tree mentioned above 4 Hete 5)

  1. Here's the picture , If the node to be deleted B There are two non empty child nodes , The node to be deleted has only the right child ( Or no children ) The situation of , Habitually select the smallest node in the right subtree of the node to be deleted E Replace the node to be deleted ( Just value substitution , The color doesn't change ), And change the node to be deleted to E.

  1. According to the color of the node to be deleted and the only child node , Handle according to the situation :

    1. Oneself O It's red , Child node N It's black , Delete directly .

    2. Oneself O It's black , Child node N It's red , Delete directly and Put the child nodes N Black .

    3. Oneself O It's black , Child node N non-existent ( It doesn't exist, that is, the child node is empty and black , It can also be used to judge ) or It's also black , More complicated , Delete first , Let's discuss the situation :

      1、N Root node , There is no need to adjust .

      2、 Here's the picture ,N Father 、 brother 、 Nephews are all black , The brother turns red , My father regarded N, Recursive processing .

3、( There is a mirror image )N The sibling node of is red , And N For father and son , The father node is the axis of left rotation ( Otherwise right-handed ), And turn it around N My grandfather's node turns black ,N The parent node of becomes red , Entry situation 4,5 or 6.

4、N My father's node is red , Brother and nephew nodes are black , The father node turns black , Brother nodes turn red .

​ 5、( There is a mirror image )N The color of the parent node is arbitrary , Brother node is father node, black right child , The left nephew node is red , The right nephew node is black , Take the brother node as the axis to rotate right , After rotating N The sibling nodes of turn black ,N Your right nephew node turns red , Entry situation 6

​ 6、( There is a mirror image )N The parent node of , The brother node is the black right son of the parent node , The right nephew node is red , With N The parent node of is the axis for left rotation , Left back N The grandparent node of becomes the parent node color , The parent node turns black , Uncle, the nodes are black .

test

Original tree ( On the lower left )

Delete 53

Delete 23

Delete 54

add to 67

Code :

https://github.com/DEUSJIN/RBTree

Copyright statement
In this paper,the author:[DeusJin],Reprint please bring the original link, thank you

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;