System.out.println("Height of right subtree:" + avlTree.getRoot().rightHeight());
System.out.println("root = " + avlTree.getRoot());
System.out.println("root.left = " + avlTree.getRoot().left);
System.out.println("root.left.left = " + avlTree.getRoot().left.left);
}
}
class AVLTree{
private SNode root;
//Find nodes to delete
public SNode getRoot() {
return root;
}
public SNode searchDelNode(int value) {
if(root == null) {
return null;
} else {
return root.searchDelNode(value);
}
}
//Find the parent node of the node you want to delete
public SNode searchParent(int value) {
if(root == null) {
return null;
} else {
return root.searchParent(value);
}
}
/**
*@ param node incoming node (as the root node of binary sort tree)
*@ return returns the value of the smallest node of the binary sort tree with node as the root node
*/
public int delRightTreeMin(SNode node) {
SNode target = node;
//Loop through the left node to find the minimum value
while(target.left != null) {
target = target.left;
}
delNode(target.value);// !!!
return target.value;// !!!
}
// Delete node
public void delNode(int value) {
if(root == null) {
return;
} else {
// Delete node not found
SNode targetNode = searchDelNode(value);
// Can't find
if(targetNode == null) {
return;
}
// If it is found that the current binary tree has only one node
if(root.left == null && root.right == null) {
root = null;
return;
}
// To find the parent node of targetNode
SNode parent = searchParent(value);
// If the deleted node is a leaf node
if(targetNode.left == null && targetNode.right == null) {
// Judge 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;
}
} else if(targetNode.left != null && targetNode.right != null) { // There are left and right child nodes
int delRightTreeMin = delRightTreeMin(targetNode.right);
targetNode.value = delRightTreeMin;
} else {// Only one child node
// Only the left node is to be deleted
if(targetNode.left != null) {
if(parent != null) {
// If the targetNode is the left child node of the parent
if(parent.left.value == value) {
parent.left = targetNode.left;
} else {
parent.right = targetNode.left;
}
} else {
root = targetNode.left;
}
} else {// The node to be deleted has a right child node
if(parent != null) {
if(parent.left.value == value) {
parent.left = targetNode.right;
} else {
parent.right = targetNode.right;
}
} else {
root = targetNode.right;
}
}
}
}
}
// Medium order traversal
public void infixOrder() {
if(root == null) {
System.out.println("Empty tree!");
} else {
root.infixOrder();
}
}
// add to
public void add(SNode node) {
if(root == null) {
root = node;
} else {
root.add(node);
}
}
}
class SNode{
protected int value;
protected SNode left;
protected SNode right;
public SNode(int value) {
// TODO Auto-generated constructor stub
this.value = value;
}
// Returns the height of the left subtree
public int leftHeight() {
if(left == null) {
return 0;
}
return left.height();
}
// Returns the height of the right subtree
public int rightHeight() {
if(right == null) {
return 0;
}
return right.height();
}
// Returns the height of the current node and the height of the tree with this node as the root node
public int height() {
return Math.max(left == null ? 0: left.height(), right == null ? 0 : right.height()) + 1;
}
// Left rotation
private void leftRotate() {
// Create a new node to the value of the current root node
SNode newNode = new SNode(value);
// Set the left subtree of the new node as the left subtree of the current node
newNode.left = left;
// Set the right subtree of the new node as the left subtree of the right subtree of the current node
newNode.right = right.left;
// Replace the value of the current node with the value of the right child node
value = right.value;
// Replace the right subtree of the current node with the right subtree of the right subtree
right = right.right;
// Set the left subtree of the current node as a new node
left = newNode;
}
// Right rotation
private void rightRotate() {
SNode newNode = new SNode(value);
newNode.right = right;
newNode.left = left.right;
value = left.value;
left = left.left;
right = newNode;
}
@Override
public String toString() {
// TODO Auto-generated method stub
return "Node = [value = " + value + "]";
}
// Add node
public void add(SNode node) {
if(node == null) {
return;
}
if(node.value < this.value) {
if(this.left == null) {
this.left = node;
} else {
this.left.add(node);
}
} else {
if(this.right == null) {
this.right = node;
} else {
this.right.add(node);
}
}
// After adding, if the height of the right subtree - the height of the left subtree > 1, rotate left
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
if(right != null && (right.leftHeight() > rightHeight() ) ) {
right.rightRotate();
leftRotate();
} else {
leftRotate();
}
return;//!!!!
}
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
if (left != null && (left.rightHeight() > left.leftHeight())) {
// First, rotate the left node of the current node
left.leftRotate();
// Then right rotate the current node
rightRotate();
} else {
rightRotate();
}
}
}
// 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 nodes to delete
public SNode searchDelNode(int value) {
if(this.value == value) {
return this;
} else if(this.value > value) {
// If the left child node is empty
if(this.left == null) {
return null;
}
summary
I personally think that if you want to get your favorite offer by relying on the test questions on the back, it's not too much to describe a toad wanting to eat swan meat. Presumably, everyone can feel that the interview is becoming more and more difficult, and it is also becoming more and more difficult to find the job they want. They can't envy high paying jobs, but they are not very satisfied with their current salary. After working for several years, they can't even compare with the salary of a fresh student. After all, they are wrongly paid, and they don't improve their skills.
The purpose of sharing these interview questions to you is actually to hope that you can analyze your technology stack through the interview questions of large factories and sort out a more clear learning direction for yourself. When you are ready to interview large factories, you have a bottom in your heart and probably know how wide and deep the interviewer will ask, so as to avoid asking three questions during the interview.
You can summarize and extend the knowledge of Java foundation, JVM, concurrent programming, MySQL, Redis, Spring, Spring cloud, etc., and then carry out the operation. Otherwise, you can't learn by just remembering. Here I also provide some brain pictures to share with you:
I hope you don't hesitate after reading this article, pay close attention to your study, review your knowledge, and prepare to get your favorite offer in next year's gold, silver and four. Come on, migrant workers!
s. Spring, Spring cloud, etc. make a knowledge summary and extension, and then carry out the operation. Otherwise, you can't learn to remember only. Here I also provide some brain maps to share with you:
[external chain picture transferring... (img-4li26v88-1628674453327)]
[external chain picture transferring... (img-BQ1XB1tE-1628674453330)]
[external chain picture transferring... (img-lbWI7dpQ-1628674453331)]
I hope you don't hesitate after reading this article, pay close attention to your study, review your knowledge, and prepare to get your favorite offer in next year's gold, silver and four. Come on, migrant workers!