Binary tree sort
Binary tree sorting mainly includes the design of node information, node insertion and tree middle order traversal
- Node information (including left and right children and node values)
private int value;// Node parameters
private Node left;/ / the left child
private Node right;/ / right child
Copy the code- Node is inserted into the
Left subtree < current value< right subtree (for the same value, can be determined according to the order of the same value, our code does not consider the same value), that is, if the value of the inserted value is less than the current node value, it is inserted into the left subtree, if the value of the inserted value is greater than the current node value, it is inserted into the right subtree, equal to the current node value discard the inserted value
// Insert the node into the tree. Node represents the new node and root represents the root node
public Node insertNode(Node node,Node root){
if(root.getValue()>node.getValue()){// Insert the left subtree
if(root.getLeft()! =null) {return insertNode(node,root.getLeft());
}else {
root.setLeft(node);
returnnode; }}else if (root.getValue() <node.getValue()){// Insert the right subtree
if(root.getRight() ! =null) {return insertNode(node,root.getRight());
}else {
root.setRight(node);
returnnode; }}else{// This node is obsolete
return null; }}Copy the code- Order in time
// middle order traversal
public void traverseTree(Node node){
if(node! =null){
traverseTree(node.getLeft());// Iterate over the left subtree
printNode(node);// Displays node information
traverseTree(node.getRight());// Iterate over the right subtree}}Copy the codeSince we insert data according to the rule of left subtree < current value< right subtree, the result of middle order traversal is an ordered list. 4. The efficiency of binary tree sorting is still good under normal circumstances, and the time complexity can be said to be Nlogn. However, when we meet the data input of the following graphs, the efficiency is a little unsatisfactory.
- This can be avoided as much as possible by shuffling the input order. This method is relatively simple and easy to implement, but it still cannot avoid the above situation
- These graphs are inefficient because they are unbalanced, so to improve efficiency, let’s try to balance the trees.
Red-black trees are the perfect solution to this problem
Properties of red-black trees
- Each node is either black or red.
- The root node is black.
- Each leaf node is black. (Leaf nodes are the empty nodes at the end of the tree.)
- If a node is red, its children must be black.
- For any node, each path to the leaf contains the same number of black nodes.
According to the properties, we can express the node information as follows
private int value;
private Node left;/ / the left subtree
private Node right;/ / right subtree
private Node parent;/ / the parent node
private boolean color;//true for black and false for red
Copy the codeAccording to property 5, we can know that red-black trees ensure the output balance according to the number of black nodes to the leaf nodes, so as to avoid the imbalance phenomenon in the figure above
Rotation operation
Rotation is an important operation for red-black trees, which are left – and right-handed rotations and coloring to maintain the tree’s balance
Left rotation produces the right graph, right rotation produces the left graph, left and right rotation are opposite operations, rotation does not change the properties of binary search trees
/** * Left-rotation code implements **@param node
*/
public void leftRoate(Node node){
if(node == null) {return;
}
Node pNode =node.getParent();
if(pNode == null) {return;
}
Node lChild =node.getLeft();
node.setParent(pNode.getParent());
if(pNode.getParent()! =null) {
if (pNode.getParent().getLeft() == pNode) {
pNode.getParent().setLeft(node);
}else {
pNode.getParent().setRight(node);
}
}
pNode.setParent(node);
node.setLeft(pNode);
pNode.setRight(lChild);
if(lChild! =null)
lChild.setParent(pNode);
}
/** * Right rotation code implementation **@param node
*/
public void rightRoate(Node node){
if(node ==null) {return;
}
Node pNode =node.getParent();
if(pNode ==null) {return;
}
Node rChild =node.getRight();
node.setParent(pNode.getParent());
if(pNode.getParent()! =null) {
if (pNode.getParent().getLeft() == pNode) {
pNode.getParent().setLeft(node);
}else {
pNode.getParent().setRight(node);
}
}
pNode.setParent(node);
node.setRight(pNode);
pNode.setLeft(rChild);
if(rChild! =null)
rChild.setParent(pNode);
}
Copy the codeNode is inserted into the
- Insert the red-black tree as if it were a binary search tree
- The insertion node is dyed red (the reason why the insertion is red is because if it is black, it must violate nature 5. Violating the nature means that the tree needs to be adjusted. Dyed red is only possible to violate nature 4. We try to violate and adjust as little as possible.
// Insert the node into the tree
public Node insertNode(Node node,Node root){
if(root.getValue()>node.getValue()){// Insert the left subtree
if(root.getLeft()! =null) {return insertNode(node,root.getLeft());
}else {
root.setLeft(node);
node.setParent(root);// Set the parent node
returnnode; }}else if (root.getValue() <node.getValue()){// Insert the right subtree
if(root.getRight() ! =null) {return insertNode(node,root.getRight());
}else {
root.setRight(node);
node.setParent(root);// Set the parent node
returnnode; }}else{// This node is obsolete
return null; }}Copy the codeInsert code and binary tree insert code, except for setting the parent node, everything else is the same
Balanced red black tree
The addition of nodes means that it is possible to change the balance of the tree. The next step is to adjust the tree according to the situation. The main operations of adjusting the tree are rotation and dyeing
The parent node is black
If the parent node is black, insert a red node without violating any properties
The parent node is red
When the parent node is red, the node violates property 4, and the red-black tree is repaired according to the situation
Tertiary nodes are red
All you have to do is make the parent node and the tertiary node black, and then make his grandfather node red, and then take the grandfather node as the current node, and continue balancing all the way to the root node
Tertiary nodes are black
Insert the node on the right branch of the parent node
When the parent node is on the left branch of the grandfather node, rotate left with the current node as the axis, change the structure to insert the node on the left node, then change the problem to insert the node on the left branch of the parent node, and the parent node is on the left branch of the grandfather node
When the parent node is on the right branch of the grandfather node, the parent node rotates to the left as the axis, and the parent node is set to black and the grandfather node is set to red
Insert nodes on the left branch of the parent node
When the parent node is on the left branch of the grandfather node, the parent node is right-handed as the axis, and the parent node is set to black and the grandfather node is set to red
When the parent node is on the right branch of the grandfather node, rotate right with the current node as the axis, change the structure to insert the node on the right node, then change the problem to insert the node on the right branch of the parent node, and the parent node on the right branch of the grandfather node
// Balance tree,
public void blanceTree(Node node){
if(node ==null) {return;
}
Node pNode = node.getParent();/ / the parent node
if(pNode ==null){
node.setColor(true);
return;
}
if(pNode.isColor()){// The parent is black
// System.out.println("-----");
return;
}
Node ppNode = pNode.getParent();// Grandfather node
if(ppNode.getLeft()! =null&&! ppNode.getLeft().isColor()&&ppNode.getRight()! =null&&! ppNode.getRight().isColor()){ ppNode.getRight().setColor(true);
ppNode.getLeft().setColor(true);
// Nodes are stained
ppNode.setColor(false);
blanceTree(ppNode);
return;
}
if(pNode == ppNode.getLeft()){// The parent node is on the left branch of the grandfather node
if(node == pNode.getLeft()){// This node is on the left branch of the parent node
rightRoate(pNode);
// Nodes are stained
ppNode.setColor(false);
pNode.setColor(true);
}else {// This node is on the right branch of the parent node
leftRoate(node);
rightRoate(node);
// Nodes are stained
node.setColor(true);
ppNode.setColor(false); }}else {// The parent node is on the right branch of the grandfather node
if(node == pNode.getLeft()){// This node is on the left branch of the parent node
rightRoate(node);
leftRoate(node);
// Nodes are stained
node.setColor(true);
ppNode.setColor(false);
}else {// This node is on the right branch of the parent node
leftRoate(pNode);
// Nodes are stained
pNode.setColor(true);
ppNode.setColor(false); }}}Copy the codeThe last step
Combine the insert and tree balance together, and complete the red-black tree insert
// Because it is possible to change the root node by rotation, always find the root node by looking for the parent node
public Node getRoot(a) {
Node root =tree;
while(root.getParent()! =null){
root = root.getParent();
}
tree = root;
return root;
}
// Insert a value
public void insert(int key){
Node node =createNode(key);
if(tree ==null) {// If the tree is empty
node.setColor(true);// Set it to black
tree =node;
return ;
}
Node insertNode = insertNode(node,getRoot());
// System.out.println(node.getValue());
blanceTree(insertNode);
}
Copy the codeconclusion
Red-black tree is a binary search tree balanced by rotation and coloring. Its complexity is nlogn, which is a good data structure.