通过Java实现红黑树及其可视化

## Node name： - RED，BLACK，DOUBLEBLACK is the color of the node，DOUBLEBLACK is the node which is not satisfy the proprieties of RBTree** - left，right，parent - initx: initiative position - nodeID provide the constructor ## RBTree ### Name： - RED，BLACK，DOUBLEBLACK is the color of the node <<<<<<< HEAD - `-root` the rote of the tree ======= - `-root` is the root of the tree >>>>>>> e13233cdbde0c2fb2ef7bb958b11415064e8dcdc - provide the constructor of the tree ### Function： - `RBTree()` & `RBTree(Node)` is the constructor of the RBTree - `getRoot()` is the getter of the private belongings Root(the tree's root) - [**the series of insert:**](# the insertion rule of RBTree:) - `insert(int)` & `insert(Node,int)` are the base cases of insert ion which comply with the rules of the Balanced Binary Search Tree - `finalInsertion(int)` is the case of insertion which contains the color of each node. - `isRoot(Node):boolean` : whether the node is root or not - `uncleIsRed(Node):boolean` - `isLeftChild(Node):boolean` - `isBlack(Node):boolean` - `isRoot(Node):boolean` - `isLeaf(Node):boolean` - `consecutiveRedNodes(Node):boolean` : whether the node and the father node is successive red node - `changeColorInsertion(Node):void`: it will change the color of father node and the uncle node into BLACK and **it will change the grandfather node's color into RED** - `uncleIsRed(Node):boolean` - [**the series of rotating:**](#the rotation rule of RBTree:) - `Rotation(Node):void`: with the combine function of leftRotate and rightRotate ,it realize the rotate and change the color - `LeftRotate(Node):void`: rotate left the Node and if its subnode has leftnode or rightnode,it will be rotated together. - `RightRotate(Node):void`: same to the LeftRotate - [**the series of deleting**](#the delete rule of RBTree): - `delete(int):void`:delete the specific node through the swap of the specific node and the predecessive node and change the color. - `deleteNode(Node):void`: delete the specific node through the swap of the specific node and the predecessive node. - `fixDoubleBlack(Node):void`:delete the node and satisfy the rule of RBTree. - `print(Node):void` - `reset(Node):void` - `search(Node):Node` - `swap(Node):Node` ### the insertion rule of RBTree: - if the inserted node is root ,it will be black; in other cases ,it will be red; - if the inserted node's father node is black, it can be inserted directlly(4 cases) - if the inserted node's uncle node is black or it doesn't have uncle node(in this case, the father node is generally red) **case of RR and LL:** - insert the node after the father node, and it will construct a 4 node - change the link and the color to satisfy the property of the 234-tree and RBTree  **case of RL and LR**  - if the inserted node's uncle node is red, the inserted node's **father node** and the **uncle node** need to be changed into BLACK. In the view of 234-tree , this phenomenon is called overflow.(4 cases:)<img src="./imgs/Untitled-2022-11-30-1137q.png" alt="the uncle is red" style="zoom: 200%;" /> ### the rotation rule of RBTree: Due to the prepority of the equation of 234-tree and RBTree, each rotation shall satisfy the rule of 234-tree and the RBTree. In each rotation of the tree , the leftnode and rightnode of the subnode should be attention（the aim is to keep the correct of the successor and predecessor(in the meaning of the sort)）.  ### the delete rule of RBTree if the **node to be deleted is red**, then just remove it. if the **node to be deleted is black**: - if the **node has two red subnodes**, it can be view as operation to the leaf node through `swap(Node)` - if the **node to be delete is black node (3 nodes) with 1 red child node**, then replace the deleted node with the only red child node (need to color the replacement node black) - if the **node to be delete is black leaf node**: - Siblings have red children (borrowed from siblings to fix) - if the **node to be delete is root**, (after swapping) delete directly - if the sibling node of the deleted node is black: - **The red node is on the left of the sibling node**: delete the specified node, then right-rotate the parent node of the deleted node, and inherit the color of the parent node - **The red node is on the right of the sibling node**: delete the specified node, then perform left rotation on the sibling node first, and then right rotation on the parent node - **There are red nodes on both sides of the sibling node:** choose one of them to rotate - **Sibling nodes have no red children** (parent nodes are merged downwards) - **The parent node is red**——(Delete the specified node, and the parent node is merged downward to generate a 3-node (underflow in the meaning of B-tree, red-black tree only needs to change the color of the parent node to black, and the sibling nodes to red)) - **The parent node is black**—the sibling node is dyed red. The parent node is dyed black; if the parent node is black: the parent node is treated as a node that has been deleted, and the recursive deletion operation is performed. - **If the sibling node of the deleted node is red** (transformed to black processing)。 - Rotate the parent node, dye the sibling node black, dye the parent node red, and then use the method that the sibling node is black the notation of the visualization will not be supplied. if you have any question about the part of visualization or about the program, connect with github_for_jin@163.com and I will respond you as soon as possible. Maybe I will update it soon...