PS： Sorting and searching are inseparable , Order is to better find .

<>1, Binary sort tree

<>（1） definition

Binary sort tree ： Or an empty tree , Or a binary tree with the following characteristics ：
1） If the left subtree is not empty , Then the values of all nodes on the left subtree are less than those of the root node ;
2） If the right subtree is not empty , Then the values of all nodes on the right subtree are greater than those of the root node ;
3） Left , The right subtree is also a binary sort tree .

<>（2） Middle order traversal and binary sorting （ search ） Tree relationship

<>（3） Insert and generate

<>1） Insert according to rules , Deliberate maintenance

* An unordered sequence can be transformed into an ordered sequence by constructing a binary sort tree . The process of constructing a tree is the process of sorting unordered sequences .
* If the inserted nodes are in the leaf node position , No other nodes need to be moved . It is equivalent to inserting records on an ordered sequence without moving other records .
<>2） Schedule the insertion process in advance

<>3） Complete case graphic presentation

<>4）Java Code implementation binary sort ( search ) Insertion and generation of tree
/** * @author: He Jianguang ——hjg_5282 * @create: 2022-01-31 14:52 * PS ==> Binary sort / search tree */
public class BinarySortTreeDemo { public static void main(String[] args) { int[]
arr= {45,24,53,12,28,90,90}; BinarySortTree binarySortTree = new BinarySortTree
(); // Loop to add nodes to binary sort tree for(int i = 0; i< arr.length; i++) { binarySortTree.add(new
Node(arr[i])); } // Middle order traversal binary sort tree System.out.println(" Middle order traversal binary sort tree ~"); binarySortTree.
infixOrder(); // 1, 3, 5, 7, 9, 10, 12 } } class BinarySortTree{ private Node
root; public Node getRoot() { return root; } // Method of adding nodes public void add(Node node
) { if(root == null) { root = node;// If root If it is blank, let root point node } else { root.add(
node); } } // Middle order traversal public void infixOrder() { if(root != null) { root.infixOrder(
); } else { System.out.println(" Binary sort tree is empty , Cannot traverse "); } } } class Node{ int value;
Node left; Node right; public Node(int value) { this.value = value; } @Override
public String toString() { return "Node [value=" + value + "]"; } // Method of adding nodes
// Add nodes recursively , Note that the requirements of binary sort tree should be met public void add(Node node) { if(node == null) {
return; } if (node.value == this.value){ return; } // Judge the value of the incoming node , Value relationship with the root node of the current subtree if(
node.value < this.value) { // If the left child node of the current node is null if(this.left == null) { this.left =
node; } else { // Recursively add to the left subtree this.left.add(node); } } else { // The value of the added node is greater than Value of current node
if(this.right == null) { this.right = node; } else { // Recursive right subtree addition this.right.add(
node); } } } // Middle order traversal public void infixOrder() { if(this.left != null) { this.left
.infixOrder(); } System.out.println(this); if(this.right != null) { this.right.
infixOrder(); } } }
<>（4） Search and delete binary sort tree

<>1） Situation 1 ： Delete leaf node

thinking
(1) You need to find the node to delete first targetNode
(2) find targetNode of Parent node parent
(3) determine targetNode yes parent Left child node of Or right child node
(4) Delete the left child node according to the previous situation parent.left = null
Right child node parent.right = null;

<>2） Situation II ： The deleted node has only left subtree or right subtree

thinking

* (1) You need to find the node to delete first targetNode
* (2) find targetNode of Parent node parent
* (3) determine targetNode Is the child node of a left child node or a right child node
* (4)targetNode yes parent Is the left child node or the right child node
* (5) If targetNode With left child node
_5.1 If targetNode yes parent Left child node of
parent.left = targetNode.left;
_5.2 If targetNode yes parent Right child node of
parent.right = targetNode.left;
* (6) If targetNode Right child node
_6.1 If targetNode yes parent Left child node of
parent.left = targetNode.right;
_6.2 If targetNode yes parent Right child node of
parent.right = targetNode.right
<>3） Situation III ： The deleted node has both left and right subtrees

thinking
(1) You need to find the node to delete first targetNode
(2) find targetNode of Parent node parent
(3) from targetNode Find the smallest node in the right subtree of
(4) Use a temporary variable , take Save the value of the minimum node temp
(5) Delete the minimum node
(6)targetNode.value = temp

<>4） Find the target node and its corresponding parent node code

Find the parent node here searchParent The method is true, a little helpless , If the information of the parent node is saved in the child node, you don't need to write this method ,
With parent and child nodes , We deleted the child node , You can graft the rest to the parent node
// establish Node node class Node { int value; Node left; Node right; public Node(int value
) { this.value = value; } // Find the node to delete /** * * @param value The value of the node you want to delete * @return
If found, return to the node , Otherwise return null */ public Node search(int value) { if(value == this.value) {
// Find the node return this; } else if(value < this.value) {// If the value found is less than the current node , Left subtree recursive search
// If the left child node is empty if(this.left == null) { return null; } return this.left.search(value)
; } else { // If the value searched is not less than the current node , Recursive search of right subtree if(this.right == null) { return null; }
return this.right.search(value); } } // Find the parent node of the node to delete /** * * @param value
The value of the node to find * @return Returns the parent node of the node to be deleted , If not, return null */ public Node searchParent(int
value) { // If the current node is the parent node of the node to be deleted , Just return if((this.left != null && this.left.value ==
value) || (this.right != null && this.right.value == value)) { return this; }
else { // If the searched value 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) { return this.left.searchParent(value); // Left subtree recursive search } else if (value >=
this.value && this.right != null) { return this.right.searchParent(value);
// Recursive search of right subtree } else { return null; // Parent node not found } } } }
<>5） Codes corresponding to the above three deletion situations （ Situation III - The grafted left subtree is the smallest ）
// Writing method : //1. Returned with node The value of the smallest node of the binary sort tree with the root node //2. delete node The smallest node of a binary sort tree with a root node /** *
@param node Incoming node ( As the root node of binary sort tree ) * @return Returned with node The value of the smallest node of the binary sort tree with the root node */ public
int delRightTreeMin(Node node) { Node target = node; // Circular lookup left child node , The minimum value will be found while(
target.left != null) { target = target.left; } // At this time target It points to the smallest node // Delete minimum node
delNode(target.value); return target.value; } // Delete Vertex public void delNode(int
value) { if(root == null) { return; }else { //1. To find a demand node, delete it first targetNode Node
targetNode= search(value); // If the node to be deleted is not found if(targetNode == null) { return; }
// If we find that the current binary sort tree has only one node , Root node if(root.left == null && root.right == null) { root =
null; return; } // To find targetNode Parent node of Node parent = searchParent(value);
// Situation 1 ： If the node to be deleted is a leaf node if(targetNode.left == null && targetNode.right == null) {
// judge targetNode It is the left child node of the parent node , Or right child node if(parent.left != null && parent.left.value ==
value) { // Is the left child node parent.left = null; } else if (parent.right != null && parent.
right.value == value) {// Right child node parent.right = null; } // Situation III ： Delete a node with two subtrees } else if
(targetNode.left != null && targetNode.right != null) { int minVal =
delRightTreeMin(targetNode.right); targetNode.value = minVal; // Situation II ： Delete nodes with only one subtree
} else { // If the node to be deleted is only Left child node if(targetNode.left != null) { if(parent != null) {
// If targetNode yes parent Left child node of if(parent.left.value == value) { parent.left =
targetNode.left; } else { // targetNode yes parent Right child node of parent.right = targetNode
.left; } } else { root = targetNode.left; } // If the node to be deleted is only Right child node } else { if(parent
!= null) { // If targetNode yes parent Left child node of if(parent.left.value == value) {
parent.left = targetNode.right; } else { // If targetNode yes parent Right child node of parent.
right= targetNode.right; } } else { root = targetNode.right; } } } } }
<>6） Codes corresponding to the above three deletion situations （ Situation III - Grafted right subtree maximum ）

Modify two places

* Add a method to find the largest subtree // Writing method : //1. Returned with node The value of the maximum node of the binary sort tree with the root node //2. delete node
The largest node of a binary sort tree that is the root node /** * @param node Incoming node ( As the root node of binary sort tree ) * @return Returned with node
The value of the maximum node of the binary sort tree with the root node */ public int delLeftTreeMax(Node node) { Node target = node;
// Circular lookup left child node , The minimum value will be found while(target.right != null) { target = target.right; } // At this time
target It points to the smallest node // Delete minimum node delNode(target.value); return target.value; }
* Modify the corresponding called method

* Test it
Look at the diagram again

<>（5） Analysis of searching process of binary sort tree

<>2, Balanced binary sort tree

<>（1） Pain points solved

<>（2） definition

The common implementation methods of balanced binary tree are red black tree ,AVL, scapegoat tree ,Treap, Stretch trees, etc

<>（3） Balanced binary tree balance adjustment

<>（4） Adjustment type （4 Species also 2 species : Sinistral , Dextral ）

<>（5） Case illustration demonstration

<>（6） Sinistral , Dextral Java code

// Left rotation method private void leftRotate() { // Create a new node , Based on the value of the current root node Node newNode = new Node(
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 to the left subtree of the right subtree of your past node
newNode.right = right.left; // Replace the value of the current node with the value of the right child node value = right.value;
// Set the right subtree of the current node as the right subtree of the right subtree of the current node right = right.right; // The left subtree of the current node ( Left child node ) Set as a new node left =
newNode; }

// Right rotation private void rightRotate() { Node newNode = new Node(value); newNode.
right= right; newNode.left = left.right; value = left.value; left = left.left;
right= newNode; }
<>（7） Complete code , Keep turning left and right during insertion , balance

<> code
public class BinarySortTree_AVLTree { public static void main(String[] args) {
//int[] arr = {4,3,6,5,7,8}; //int[] arr = { 10, 12, 8, 9, 7, 6 }; // int[] arr
= { 10, 11, 7, 6, 8, 9 }; int[] arr = {16,3,7,11,9,26,18,14,15}; // Create a
AVLTree object AVLTree avlTree = new AVLTree(); // Add node for(int i=0; i < arr.length; i
++) { avlTree.add(new Node(arr[i])); } // ergodic System.out.println(" Middle order traversal "); avlTree.
infixOrder(); System.out.println(" In balance processing ~~"); System.out.println(" Height of tree =" +
avlTree.getRoot().height()); //3 System.out.println(" Height of the left subtree of the tree =" + avlTree.getRoot
().leftHeight()); // 2 System.out.println(" Height of right subtree of tree =" + avlTree.getRoot().
rightHeight()); // 2 System.out.println(" Current root node =" + avlTree.getRoot());//8
System.out.println(" Left child of root node "+avlTree.getRoot().right); System.out.println(
" Right child node of root node "+avlTree.getRoot().left); } } // establish AVLTree class AVLTree { private
Node root; public Node getRoot() { return root; } // Find the node to delete public Node search
(int value) { if (root == null) { return null; } else { return root.search(value
); } } // Find parent node public Node searchParent(int value) { if (root == null) { return
null; } else { return root.searchParent(value); } } // Writing method : // 1. Returned with node
The value of the smallest node of the binary sort tree with the root node // 2. delete node The smallest node of a binary sort tree with a root node /** * * @param node *
Incoming node ( As the root node of binary sort tree ) * @return Returned with node The value of the smallest node of the binary sort tree with the root node */ public int
delRightTreeMin(Node node) { Node target = node; // Circular lookup left child node , The minimum value will be found while (
target.left != null) { target = target.left; } // At this time target It points to the smallest node // Delete minimum node
delNode(target.value); return target.value; } // Delete Vertex public void delNode(int
value) { if (root == null) { return; } else { // 1. You need to find the node to delete first targetNode Node
targetNode= search(value); // If the node to be deleted is not found if (targetNode == null) { return; }
// If we find that the current binary sort tree has only one node if (root.left == null && root.right == null) { root =
null; return; } // To find targetNode Parent node of Node parent = searchParent(value); //
If the node to be deleted is a leaf node if (targetNode.left == null && targetNode.right == null) { //
judge targetNode It is the left child node of the parent node , Or right child node if (parent.left != null && parent.left.value ==
value) { // Is the left child node parent.left = null; } else if (parent.right != null && parent.
right.value == value) {// Is a child node parent.right = null; } } else if (targetNode.
left!= null && targetNode.right != null) { // Delete a node with two subtrees int minVal =
delRightTreeMin(targetNode.right); targetNode.value = minVal; } else { //
There is only one subtree to delete // If the node to be deleted has a left child node if (targetNode.left != null) { if (parent != null)
{ // If targetNode yes parent Left child node of if (parent.left.value == value) { parent.left
= targetNode.left; } else { // targetNode yes parent Right child node of parent.right =
targetNode.left; } } else { root = targetNode.left; } } else { // If the node to be deleted has a right child node
if (parent != null) { // If targetNode yes parent Left child node of if (parent.left.value ==
value) { parent.left = targetNode.right; } else { // If targetNode yes parent
Right child node of parent.right = targetNode.right; } } else { root = targetNode.right; } } }
} } // Method of adding nodes public void add(Node node) { if (root == null) { root = node;//
If root If it is blank, let root point node } else { root.add(node); } } // Middle order traversal public void
infixOrder() { if (root != null) { root.infixOrder(); } else { System.out.
println(" Binary sort tree is empty , Cannot traverse "); } } } // establish Node node class Node { int value; Node left;
Node right; public Node(int value) { 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(); } // return 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 method
private void leftRotate() { // Create a new node , Based on the value of the current root node Node newNode = new Node(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 to the left subtree of the right subtree of your past node newNode
.right = right.left; // Replace the value of the current node with the value of the right child node value = right.value;
// Set the right subtree of the current node as the right subtree of the right subtree of the current node right = right.right; // The left subtree of the current node ( Left child node ) Set as a new node left =
newNode; } // Right rotation private void rightRotate() { Node newNode = new Node(value);
newNode.right = right; newNode.left = left.right; value = left.value; left =
left.left; right = newNode; } // Find the node to delete /** * * @param value * The value of the node you want to delete *
@return If found, return to the node , Otherwise return null */ public Node search(int value) { if (value == this.
value) { // Find the node return this; } else if (value < this.value) {//
If the value found is less than the current node , Left subtree recursive search // If the left child node is empty if (this.left == null) { return null; } return
this.left.search(value); } else { // If the value searched is not less than the current node , Recursive search of right subtree if (this.right ==
null) { return null; } return this.right.search(value); } } // Find the parent node of the node to delete /**
* * @param value * The value of the node to find * @return Returns the parent node of the node to be deleted , If not, return null */ public Node
searchParent(int value) { // If the current node is the parent node of the node to be deleted , Just return if ((this.left != null &&
this.left.value == value) || (this.right != null && this.right.value == value))
{ return this; } else { // If the searched value 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) { return this.left.searchParent(value); // Left subtree recursive search } else
if (value >= this.value && this.right != null) { return this.right.searchParent(
value); // Recursive search of right subtree } else { return null; // Parent node not found } } } @Override public
String toString() { return "Node [value=" + value + "]"; } // Method of adding nodes //
Add nodes recursively , Note that the requirements of binary sort tree should be met public void add(Node node) { if (node == null) { return
; } // Judge the value of the incoming node , Value relationship with the root node of the current subtree if (node.value < this.value) { // If the left child node of the current node is null
if (this.left == null) { this.left = node; } else { // Recursively add to the left subtree this.left.add(
node); } } else { // The value of the added node is greater than Value of current node if (this.right == null) { this.right =
node; } else { // Recursive right subtree addition this.right.add(node); } } // After adding a node , If :
( Height of right subtree - Height of left subtree ) > 1 , Left rotation if(rightHeight() - leftHeight() > 1) {
// If the height of the left subtree of its right subtree is greater than the height of the right subtree of its right subtree if(right != null && right.leftHeight() > right.
rightHeight()) { // Rotate the right child node first right.rightRotate(); // Then rotate the current node to the left leftRotate()
; // Left rotation .. } else { // Just rotate left leftRotate(); } return ; // Must !!! }
// After adding a node , If ( Height of left subtree - Height of right subtree ) > 1, Right rotation if(leftHeight() - rightHeight() > 1) {
// If the height of the right subtree of its left subtree is greater than the height of its left subtree if(left != null && left.rightHeight() > left.
leftHeight()) { // First, the left node of the current node ( Left subtree )-> Left rotation left.leftRotate(); // Then right rotate the current node
rightRotate(); } else { // Just rotate right rightRotate(); } } } // Middle order traversal public void
infixOrder() { if (this.left != null) { this.left.infixOrder(); } System.out.
println(this); if (this.right != null) { this.right.infixOrder(); } } }
<> effect

<>（8） Keep turning left and right when deleting , balance —— No,

Technology
Daily Recommendation