balanced binary tree
Realization of left rotation and right rotation
Left rotation
//Left rotation
public void leftRotate() {
//Create a new node and assign the value of the current node to it
Node newNode = new Node(this.value);
//Set the left subtree of the new node as the left subtree of the current node
newNode.left = this.left;
//Set the right subtree of the new node as the left subtree of the right subtree of the current node
newNode.right = this.right.left;
//Replace the value of the current node with the value of the right child node
this.value = this.right.value;
//Set the right subtree of the current node as the right subtree of the right child of the current node
this.right = this.right.right;
//Set the left child node of the current node as a new node
this.left = newNode;
}
Right rotation
//Right rotation
public void rightRotate() {
//Create a new node and assign the value of the current node to the new node
Node newNode = new Node(this.value);
//Set the right subtree of the new node to the right subtree of the current node
newNode.right = this.right;
//Set the left subtree of the new node to the right subtree of the left subtree of the current node
newNode.left = this.left.right;
//Set the value of the current node to the value of the left child node of the current node
this.value = this.left.value;
//Set the right child node of the current node as a new node
this.right = newNode;
//Set the left sub node of the current node as the left sub tree of the left sub node
this.left = this.left.left;
}
Adding balanced binary tree
step
- If the node to be added is empty, exit the method directly
- Judge the relationship between the value of the incoming node and the root node of the current subtree
- The value of the node to be added is less than the value of the current node
- If the left child of the current node is empty, the node will be set as the left child of the current node
- If the left child node of the current node is not empty, recursively add to the left child tree
- The value of the node to be added is greater than the current node
- If the right child of the current node is empty, the node will be set as the right child of the current node
- If the right child node of the current node is not empty, recursively add to the right subtree
- After the addition is completed, the subtree at each level is judged
- If the height of the right subtree - the height of the left subtree > 1, rotate left
- If the height of the left subtree of the right subtree of the current node is greater than the height of the right subtree of the right subtree of the current node
- First, right rotate the right subtree of the current node
- Then rotate the current node to the left
- Return directly after the method is executed; So as to return to the previous stack and avoid the influence of the judgment condition of the height of the left subtree - the height of the right subtree > 1 on the tree
- If the height of the left subtree of the right subtree of the current node is greater than the height of the right subtree of the right subtree of the current node
- Height of the left subtree - if the height of the right subtree is > 1, the right rotation is performed
- If the height of the right subtree of the left subtree of the current node is greater than the height of the left subtree of the left subtree of the current node
- You need to rotate the left subtree of the current node first
- Then rotate the current node to the right
- return directly after the method is executed;
- If the height of the right subtree of the left subtree of the current node is greater than the height of the left subtree of the left subtree of the current node
- If the height of the right subtree - the height of the left subtree > 1, rotate left
- The value of the node to be added is less than the value of the current node
code implementation
class AVLTree {
private Node root;
public Node getRoot() {
return root;
}
//Add node
public void add(Node node) {
//If root is empty, let root point to node
if (this.root == null) {
this.root = node;
} else {
this.root.add(node);
}
}
//Medium order traversal
public void infixOrder() {
if (this.root == null) {
System.out.println("Binary sort tree is empty, unable to traverse!");
} else {
this.root.infixOrder();
}
}
}
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
//Left rotation
public void leftRotate() {
//Create a new node and assign the value of the current node to it
Node newNode = new Node(this.value);
//Set the left subtree of the new node as the left subtree of the current node
newNode.left = this.left;
//Set the right subtree of the new node as the left subtree of the right subtree of the current node
newNode.right = this.right.left;
//Replace the value of the current node with the value of the right child node
this.value = this.right.value;
//Set the right subtree of the current node as the right subtree of the right child of the current node
this.right = this.right.right;
//Set the left child node of the current node as a new node
this.left = newNode;
}
//Right rotation
public void rightRotate() {
//Create a new node and assign the value of the current node to the new node
Node newNode = new Node(this.value);
//Set the right subtree of the new node to the right subtree of the current node
newNode.right = this.right;
//Set the left subtree of the new node to the right subtree of the left subtree of the current node
newNode.left = this.left.right;
//Set the value of the current node to the value of the left child node of the current node
this.value = this.left.value;
//Set the right child node of the current node as a new node
this.right = newNode;
//Set the left sub node of the current node as the left sub tree of the left sub node
this.left = this.left.left;
}
//Returns the height of the tree with the current node as the root node
public int height() {
//Returns the larger height of the left subtree and the right subtree plus the height of the current node
return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}
//Returns the height of the left subtree
public int leftHeight() {
if (this.left == null) {
return 0;
}
return this.left.height();
}
//Returns the height of the right subtree
public int rightHeight() {
if (this.right == null) {
return 0;
}
return this.right.height();
}
//Add node
public void add(Node node) {
if (node == null) {
return;
}
//Judge the relationship between the value of the incoming node and the root node of the current subtree
//The value of the node to be added is less than the value of the current node
if (node.value < this.value) {
//The left child node of the current node is empty
if (this.left == null) {
this.left = node;
} else {
//Recursively add to the left subtree
this.left.add(node);
}
} else if (node.value > this.value) {//The value of the node to be added is greater than the value of the current node
//The right child node of the current node is empty
if (this.right == null) {
this.right = node;
} else {
//Recursively add to the right subtree
this.right.add(node);
}
}
//After adding a node, if the height of the right subtree - the height of the left subtree > 1, the left rotation
if (rightHeight() - leftHeight() > 1) {
//If the height of the left subtree of the right subtree of the current node is greater than the height of the right subtree of the right subtree of the current node
//You need to rotate the right subtree of the current node first
//Because rightheight() - leftheight() > 1, this Right is definitely not null
if (this.right.leftHeight() > this.right.rightHeight()) {
this.right.rightRotate();
}
//Left rotation
leftRotate();
//Be sure to return! Because it has been balanced after the rotation,
//If you still let the following judge, there is likely to be a problem
return;
}
//Height of left subtree - height of right subtree > 1, then rotate right
if (leftHeight() - rightHeight() > 1) {
//If the height of the right subtree of the left subtree of the current node is greater than the height of the left subtree of the left subtree of the current node
//You need to rotate the left subtree of the current node first
//Because leftheight() - rightheight() > 1, this Left is definitely not null
if (this.left.rightHeight() > this.left.leftHeight()) {
this.left.leftRotate();
}
//Right rotation
rightRotate();
return;
}
}
//Medium order traversal
public void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.infixOrder();
}
}
}
Deleting balanced binary tree
The deletion operation is also similar to the deletion of binary sort tree, but after deleting the end point, we need to re judge the depth of the left and right children. If there is an imbalance, we need to adjust it.
Three cases of deleting nodes in balanced binary tree
- The deleted node is a leaf node, and the node to be deleted is found
- The deleted node has left subtree or right subtree
- The deleted node has both left and right subtrees
Delete leaf node
Example 1:
- We delete 14 nodes and return recursively
- Return to parent node 10, judge the left and right depth of node 10, and find that the height of the left subtree of node 10 - the height of the right subtree =1, so there is no need to adjust, and return recursively
- Return to the root node 20, judge the left and right depth of node 20, and find that the height of the left subtree of node 20 - the height of the right subtree = -1, so no adjustment is needed
- Therefore, after adjustment, no adjustment is needed to get a balanced binary tree
Example 2:
When we delete node 7, we can find that it is a leaf node. Delete it directly to get the following binary tree:
It can be found that the height of the left and right subtrees of the parent node 8 of the original node 7 is 0, reaching a balance. Therefore, continue to look up and find that the difference between the left subtree height and the right subtree height of the parent node 20 of 8 is 2, that is, the node 20 is unbalanced. Adjustments are required. What adjustments should be made to this place? It is found that the height of the left subtree of node 30 is greater than that of the right subtree, so we need to rotate the subtree with node 30 as the root node to get the following figure.
Next, rotate the tree with 20 as the root node to the left, and get the following figure, which is the shape of the adjusted tree.
Example 3:
Delete node 8 in the above figure to get the following figure:
It can be observed that the tree is in an unbalanced state. Node 20 is in a balanced state, and the height difference between the left and right subtrees of node 25 is 2, which needs to be adjusted. We find the sub node 30 on the right sub tree of node 20, and find that the height of the left and right sub trees of node 30 is the same, so we only need to adjust the RR type, that is, rotate left once, and rotate counterclockwise according to node 30. The adjusted tree is as follows:
To delete a leaf node
- Delete the node directly from the tree
2. Upward recursion to judge whether the father or ancestor is unbalanced
3. If the parent node is not unbalanced, continue to search upward to calculate whether the parent node of the parent node is unbalanced... Repeat the judgment of 2 until the root node; If the imbalance is found in the upward calculation process, proceed to 4;
4. If its parent node is unbalanced
- When adjusting the parent node, if the height of the left subtree - the height of the right subtree is > 1, then rotate to the right. If the height of the right subtree of the left subtree of the current node is greater than the height of the left subtree of the left subtree of the current node, you need to rotate the left subtree of the current node first, and then rotate the parent node to the right;
- If the height of the right subtree - the height of the left subtree is > 1, rotate left. If the height of the left subtree of the right subtree of the current node is greater than the height of the right subtree of the right subtree of the current node, rotate right to the right subtree of the current node first, and then rotate left to the parent node.
5. If the height of the tree with the parent node as the root node changes after the balancing process, continue to calculate the retrieval of 2; If the height is consistent with the original height with the parent node as the root node, it can be explained that the balance factor of the parent node and the ancestor node of the parent node will not change, so the processing can be exited
Delete a node with only left subtree or only right subtree
Example 1:
In the balance tree, we want to delete the node with the value of 29. We replace the node with the left subtree of the node, and then delete the node with the value of 29. The shape of the tree is as follows:
You can see that the tree is in balance. No processing is required.
If you delete the node with a value of 40 in example 1, first replace it with its right subtree, and then delete the node, you can get the following shape:
The following operations are the same as deleting leaf nodes.
It can be found that the tree is out of balance. We find the node with a value of 50 and its parent node with a value of 30. Then find its left child, and the node value is 25. It is found that the right subtree of this node is higher than the left subtree. Therefore, we need to rotate left first, that is, rotate counterclockwise around the node with the value of 29, and get the following figure:
Next, rotate right to get the following figure.
Steps to delete nodes with left or right subtrees
- Replace the position of the original deleted node with the left subtree (right subtree)
2. Upward recursion to judge whether the father or ancestor is unbalanced
3. If the parent node is not unbalanced, continue to search upward to calculate whether the parent node of the parent node is unbalanced... Repeat the judgment of 2 until the root node; If the imbalance is found in the upward calculation process, proceed to 4;
4. If its parent node is unbalanced
- When adjusting the parent node, if the height of the left subtree - the height of the right subtree is > 1, then rotate to the right. If the height of the right subtree of the left subtree of the current node is greater than the height of the left subtree of the left subtree of the current node, you need to rotate the left subtree of the current node first, and then rotate the parent node to the right;
- If the height of the right subtree - the height of the left subtree is > 1, rotate left. If the height of the left subtree of the right subtree of the current node is greater than the height of the right subtree of the right subtree of the current node, rotate right to the right subtree of the current node first, and then rotate left to the parent node.
5. If the height of the tree with the parent node as the root node changes after the balancing process, continue to calculate the retrieval of 2; If the height is consistent with the original height with the parent node as the root node, it can be explained that the balance factor of the parent node and the ancestor node of the parent node will not change, so the processing can be exited
Deleting a node has both left and right subtrees
Example 1:
We delete node 20 from the balanced tree, and we analyze that the height of the left subtree of node 20 - the height of the right subtree =1, so we find the maximum value from the left subtree of node 20, and the maximum value is node 15. We replace the values of the two nodes. The resulting tree shape is as follows:
Next, delete node 20 to get the following figure.
It is found that the height of the left subtree - the height of the right subtree of the parent node 10 of the previously deleted node 20 =2, which is in an unbalanced state. Therefore, it is necessary to adjust the subtree with 10 as the root node. First, carry out a left rotation operation to get the following figure:
Perform another right-hand rotation operation. The final shape of the tree is as follows:
Steps to delete a node with left and right subtrees
- If the height of the left subtree of the current node is greater than or equal to the height of the right subtree, find the maximum value from the left subtree and replace it with the value of the node to be deleted
- If the height of the right subtree of the current node is greater than the height of the left subtree, find the minimum value from the right subtree and replace it with the value of the node to be deleted
- After the replacement, the node of the maximum value of the left subtree (the node of the minimum value of the right subtree) becomes the object we want to delete
- The maximum value in the left subtree is either a leaf node or a node without a right subtree, and the minimum value in the left subtree is either a leaf node or a node without a left subtree
- Finally, just delete the leaf node or the node with only one subtree
code implementation
This method is used to adjust the imbalance when the leaf node is deleted or there is a child node.
public void adjust(Node parent) {
while (parent != null) {
//If the height of the right subtree - the height of the left subtree > 1, rotate left
if (parent.rightHeight() - parent.leftHeight() > 1) {
//If the height of the left subtree of the right subtree of the current node is greater than the height of the right subtree of the right subtree of the current node
//You need to rotate the right subtree of the current node first
//Because rightheight() - leftheight() > 1, this Right is definitely not null
if (parent.right.leftHeight() > parent.right.rightHeight()) {
parent.right.rightRotate();
}
//Left rotation
parent.leftRotate();
}
//Height of left subtree - height of right subtree > 1, then rotate right
else if (parent.leftHeight() - parent.rightHeight() > 1) {
//If the height of the right subtree of the left subtree of the current node is greater than the height of the left subtree of the left subtree of the current node
//You need to rotate the left subtree of the current node first
//Because leftheight() - rightheight() > 1, this Left is definitely not null
if (parent.left.rightHeight() > parent.left.leftHeight()) {
parent.left.leftRotate();
}
//Right rotation
parent.rightRotate();
}
parent = searchParent(parent.value);
}
}
Complete code implementation
class AVLTree {
private Node root;
public Node getRoot() {
return root;
}
//Add node
public void add(Node node) {
//If root is empty, let root point to node
if (this.root == null) {
this.root = node;
} else {
this.root.add(node);
}
}
//Medium order traversal
public void infixOrder() {
if (this.root == null) {
System.out.println("Binary sort tree is empty, unable to traverse!");
} else {
this.root.infixOrder();
}
}
//Find the node to delete
public Node search(int value) {
if (this.root == null) {
return null;
} else {
return this.root.search(value);
}
}
public Node search(int value,Node virtualRoot) {
if (virtualRoot == null) {
return null;
} else {
return virtualRoot.search(value);
}
}
//Find the parent node of the node to delete
public Node searchParent(int value) {
if (this.root == null) {
return null;
} else {
return this.root.searchParent(value);
}
}
public Node searchParent(int value,Node virtualRoot) {
if (virtualRoot == null) {
return null;
} else {
return virtualRoot.searchParent(value);
}
}
public void adjust(Node parent) {
while (parent != null) {
//If the height of the right subtree - the height of the left subtree > 1, rotate left
if (parent.rightHeight() - parent.leftHeight() > 1) {
//If the height of the left subtree of the right subtree of the current node is greater than the height of the right subtree of the right subtree of the current node
//You need to rotate the right subtree of the current node first
//Because rightheight() - leftheight() > 1, this Right is definitely not null
if (parent.right.leftHeight() > parent.right.rightHeight()) {
parent.right.rightRotate();
}
//Left rotation
parent.leftRotate();
}
//Height of left subtree - height of right subtree > 1, then rotate right
else if (parent.leftHeight() - parent.rightHeight() > 1) {
//If the height of the right subtree of the left subtree of the current node is greater than the height of the left subtree of the left subtree of the current node
//You need to rotate the left subtree of the current node first
//Because leftheight() - rightheight() > 1, this Left is definitely not null
if (parent.left.rightHeight() > parent.left.leftHeight()) {
parent.left.leftRotate();
}
//Right rotation
parent.rightRotate();
}
parent = searchParent(parent.value);
}
}
/**
* @param node Incoming node
* @return Returns the value of the smallest node of a binary sort tree with node as the root node
*/
public Node findRightTreeMin(Node node) {
Node target = node;
while (target.left != null) {
target = target.left;
}
return target;
}
/**
* @param node Incoming node
* @return Returns the value of the largest node of a binary sort tree with node as the root node
*/
public Node findLeftTreeMax(Node node) {
Node target = node;
while (target.right != null) {
target = target.right;
}
return target;
}
//Delete Vertex
/*
The first case: delete leaf nodes (for example: 2, 5, 9, 12)
thinking
(1) You need to find the targetNode to delete first
(2) Find the parent node of the targetNode
(3) Determine whether the targetNode is the left child node or the right child node of the parent
(4) Delete the left child node parent according to the previous situation Left = null right child node parent right = null;
The second case: delete nodes with only one subtree, such as 1 idea
(1) You need to find the targetNode to delete first
(2) Find the parent node of the targetNode
(3) Determine whether the child node of the targetNode is a left child node or a right child node
(4) targetNode Is it the left child node or the right child node of the parent
(5) If the targetNode has a left child node
5. 1 If the targetNode is the left child of the parent
parent.left = targetNode.left;
5.2 If targetnode is the right child node of parent, parent right = targetNode. left;
(6) If the targetNode has a right child node
6.1 If targetnode is the left child node of parent, parent left = targetNode. right;
6.2 If targetnode is the right child node of parent, parent right = targetNode. right;
Case 3: delete the node with two subtrees (for example: 7, 3, 10)
thinking
(1) You need to find the targetNode to delete first
(2) Find the parent node of the targetNode
(3) Find the smallest node from the right subtree of the targetNode
(4) Save the value of the minimum node with a temporary variable temp = 11
(5) Delete the minimum node
(6) targetNode.value = temp
*/
public void delNode(int value) {
if (this.root == null) {
return;
} else {
//Find the node to delete
Node targetNode = search(value);
//Can't find
if (targetNode == null) {
return;
}
//If the binary tree has only one node, and the node to be deleted is found in the front
//Then the root node is the node we want to delete
if (this.root.left == null && this.root.right == null) {
this.root = null;
return;
}
//Find the parent node of targetNode
Node parent = searchParent(value);
//If the node to be deleted is a leaf node
if (targetNode.left == null && targetNode.right == null) {
//Determine whether the targetNode is the left child node or the right child node of the parent node
if (parent.left != null && parent.left.value == value) {
parent.left = null;
} else if (parent.right != null && parent.right.value == value) {
parent.right = null;
}
//After deletion, check whether each parent node is unbalanced and adjust it
adjust(parent);
//If the targetNode has left and right subtrees
} else if (targetNode.left != null && targetNode.right != null) {
//If the height of the left subtree of targetNode is greater than or equal to the height of the right subtree, find the maximum value from the left subtree and replace it with the value of the node to be deleted
//After the replacement, the node of the maximum value of the left subtree becomes the object we want to delete
//The maximum value in the left subtree is either a leaf node or a node without a right subtree
//Then you just need to delete the leaf node or the node with only one subtree
if (targetNode.leftHeight() - targetNode.rightHeight() >= 0) {
Node LeftMaxNode = findLeftTreeMax(targetNode.left);
int temp = LeftMaxNode.value;
LeftMaxNode.value = targetNode.value;
targetNode.value = temp;
delNode(LeftMaxNode.value,targetNode.left);
}else {
//If the height of the right subtree of the targetNode is greater than the height of the left subtree, find the minimum value from the right subtree and replace it with the value of the node to be deleted
//After the replacement, the node with the minimum value of the right subtree becomes the object we want to delete
//The minimum value in the left subtree is either a leaf node or a node without a left subtree
//Then you just need to delete the leaf node or the node with only one subtree
Node rightMaxNode = findRightTreeMin(targetNode);
int temp = rightMaxNode.value;
rightMaxNode.value = targetNode.value;
targetNode.value = temp;
delNode(rightMaxNode.value,targetNode.right);
}
} else { //Only one child node
//If the targetNode has a left child node
if (targetNode.left != null) {//Consider whether the deleted node is the root node
if (parent != null) {//When the node to be deleted is not the root node
//If the targetNode is the left child of the parent
if (parent.left.value == value) {
parent.left = targetNode.left;
} else {//targetNode is the right child node of parent
parent.right = targetNode.left;
}
} else {//The node to be deleted is the root node. No adjustment is required after deletion
this.root = targetNode.left;
}
} else { //targetNode has right child node
if (parent != null) {//The node to be deleted is not the root node
//targetNode is the left child node of parent
if (parent.left.value == value) {
parent.left = targetNode.right;
} else {//targetNode is the right child node of parent
parent.right = targetNode.right;
}
} else {//The node to be deleted is the root node
this.root = targetNode.right;
}
}
//After deletion, check whether each parent node is unbalanced and adjust it
adjust(parent);
}
}
}
//Overload deletion method, which is used to transform the deletion of nodes with left and right subtrees into the deletion of leaf nodes or single subtree nodes
public void delNode(int value,Node virtualRoot) {
if (virtualRoot == null) {
return;
} else {
//Find the node to delete
Node targetNode = search(value,virtualRoot);
//Can't find
if (targetNode == null) {
return;
}
//If the binary tree has only one node, and the node to be deleted is found in the front
//Then the root node is the node we want to delete
if (virtualRoot.left == null && virtualRoot.right == null) {
virtualRoot = null;
return;
}
//Find the parent node of targetNode
Node parent = searchParent(value,virtualRoot);
//If the node to be deleted is a leaf node
if (targetNode.left == null && targetNode.right == null) {
//Determine whether the targetNode is the left child node or the right child node of the parent node
if (parent.left != null && parent.left.value == value) {
parent.left = null;
} else if (parent.right != null && parent.right.value == value) {
parent.right = null;
}
//After deletion, check whether each parent node is unbalanced and adjust it
adjust(parent);
//If the targetNode has left and right subtrees
} else if (targetNode.left != null && targetNode.right != null) {
//If the height of the left subtree of targetNode is greater than or equal to the height of the right subtree, find the maximum value from the left subtree and replace it with the value of the node to be deleted
//After the replacement, the node of the maximum value of the left subtree becomes the object we want to delete
//The maximum value in the left subtree is either a leaf node or a node without a right subtree
//Then you just need to delete the leaf node or the node with only one subtree
if (targetNode.leftHeight() - targetNode.rightHeight() >= 0) {
Node LeftMaxNode = findLeftTreeMax(targetNode.left);
int temp = LeftMaxNode.value;
LeftMaxNode.value = targetNode.value;
targetNode.value = temp;
delNode(LeftMaxNode.value,virtualRoot);
}else {
//If the height of the right subtree of the targetNode is greater than the height of the left subtree, find the minimum value from the right subtree and replace it with the value of the node to be deleted
//After the replacement, the node with the minimum value of the right subtree becomes the object we want to delete
//The minimum value in the left subtree is either a leaf node or a node without a left subtree
//Then you just need to delete the leaf node or the node with only one subtree
Node rightMaxNode = findRightTreeMin(targetNode);
int temp = rightMaxNode.value;
rightMaxNode.value = targetNode.value;
targetNode.value = temp;
delNode(rightMaxNode.value,virtualRoot);
}
} else { //Only one child node
//If the targetNode has a left child node
if (targetNode.left != null) {//Consider whether the deleted node is the root node
if (parent != null) {//When the node to be deleted is not the root node
//If the targetNode is the left child of the parent
if (parent.left.value == value) {
parent.left = targetNode.left;
} else {//targetNode is the right child node of parent
parent.right = targetNode.left;
}
} else {//The node to be deleted is the root node. No adjustment is required after deletion
virtualRoot = targetNode.left;
}
} else { //targetNode has right child node
if (parent != null) {//The node to be deleted is not the root node
//targetNode is the left child node of parent
if (parent.left.value == value) {
parent.left = targetNode.right;
} else {//targetNode is the right child node of parent
parent.right = targetNode.right;
}
} else {//The node to be deleted is the root node
virtualRoot = targetNode.right;
}
}
//After deletion, check whether each parent node is unbalanced and adjust it
adjust(parent);
}
}
}
}
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
//Left rotation
public void leftRotate() {
//Create a new node and assign the value of the current node to it
Node newNode = new Node(this.value);
//Set the left subtree of the new node as the left subtree of the current node
newNode.left = this.left;
//Set the right subtree of the new node as the left subtree of the right subtree of the current node
newNode.right = this.right.left;
//Replace the value of the current node with the value of the right child node
this.value = this.right.value;
//Set the right subtree of the current node as the right subtree of the right child of the current node
this.right = this.right.right;
//Set the left child node of the current node as a new node
this.left = newNode;
}
//Right rotation
public void rightRotate() {
//Create a new node and assign the value of the current node to the new node
Node newNode = new Node(this.value);
//Set the right subtree of the new node to the right subtree of the current node
newNode.right = this.right;
//Set the left subtree of the new node to the right subtree of the left subtree of the current node
newNode.left = this.left.right;
//Set the value of the current node to the value of the left child node of the current node
this.value = this.left.value;
//Set the right child node of the current node as a new node
this.right = newNode;
//Set the left sub node of the current node as the left sub tree of the left sub node
this.left = this.left.left;
}
//Returns the height of the tree with the current node as the root node
public int height() {
//Returns the larger height of the left subtree and the right subtree plus the height of the current node
return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}
//Returns the height of the left subtree
public int leftHeight() {
if (this.left == null) {
return 0;
}
return this.left.height();
}
//Returns the height of the right subtree
public int rightHeight() {
if (this.right == null) {
return 0;
}
return this.right.height();
}
//Add node
public void add(Node node) {
if (node == null) {
return;
}
//Judge the relationship between the value of the incoming node and the root node of the current subtree
//The value of the node to be added is less than the value of the current node
if (node.value < this.value) {
//The left child node of the current node is empty
if (this.left == null) {
this.left = node;
} else {
//Recursively add to the left subtree
this.left.add(node);
}
} else if (node.value > this.value) {//The value of the node to be added is greater than the value of the current node
//The right child node of the current node is empty
if (this.right == null) {
this.right = node;
} else {
//Recursively add to the right subtree
this.right.add(node);
}
}
//After adding a node, if the height of the right subtree - the height of the left subtree > 1, the left rotation
if (rightHeight() - leftHeight() > 1) {
//If the height of the left subtree of the right subtree of the current node is greater than the height of the right subtree of the right subtree of the current node
//You need to rotate the right subtree of the current node first
//Because rightheight() - leftheight() > 1, this Right is definitely not null
if (this.right.leftHeight() > this.right.rightHeight()) {
this.right.rightRotate();
}
//Left rotation
leftRotate();
//Be sure to return! Because it has been balanced after the rotation,
//If you still let the following judge, there is likely to be a problem
return;
}
//Height of left subtree - height of right subtree > 1, then rotate right
if (leftHeight() - rightHeight() > 1) {
//If the height of the right subtree of the left subtree of the current node is greater than the height of the left subtree of the left subtree of the current node
//You need to rotate the left subtree of the current node first
//Because leftheight() - rightheight() > 1, this Left is definitely not null
if (this.left.rightHeight() > this.left.leftHeight()) {
this.left.leftRotate();
}
//Right rotation
rightRotate();
return;
}
}
//Medium order traversal
public void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.infixOrder();
}
}
//Find the node to delete
public Node search(int value) {
if (value == this.value) {
return this;
} else if (value < this.value) {//Look for the left subtree
if (this.left == null) {
return null;
}
return this.left.search(value);
} else {//Look for the right subtree
if (this.right == null) {
return null;
}
return this.right.search(value);
}
}
//Find the parent node of the node to delete
public Node searchParent(int value) {
//If the current node is the parent node, return directly
if ((this.left != null && this.left.value == value)
|| (this.right != null && this.right.value == value)) {
return this;
} else {
//If the value searched is less than the value of the current node
//And the left child node of the current node is not empty
if (value < this.value && this.left != null) {
//Left subtree recursive search
return this.left.searchParent(value);
} else if (value > this.value && this.right != null) {
//Rightward subtree
return this.right.searchParent(value);
}
}
//Can't find
return null;
}
}
Some explanations in the code:
Why overload delNode, searchParent, and search methods?
For the third case, there are both left and right subtrees. We replace the position of the maximum or minimum value in the node and subtree to be deleted, and replace the case of deleting the left subtree and right subtree with the case of deleting the leaf node or a child node. However, the position of the replacement is often inconsistent with the subtree where its value should be, For example, find the maximum value from the left subtree and exchange it with the node to be deleted (that is, the parent node of the left subtree). All the values of the left subtree are smaller than the parent node. At this time, it is equivalent to that there is a value greater than the root node in the left subtree. When searching, the value greater than the root node is in the right subtree by default. The default deletion method, search method and search method of the parent node are all searched from the root node, It is impossible to find the node to be deleted. At this time, it is necessary to overload these three methods and modify its root node to the root node of the incoming subtree, so that it can be found and deleted.