1. Start with a need
You are given a sequence of numbers (7, 3, 10, 12, 5, 1, 9) that can be efficiently queried and added to data
1.1 Using Arrays
Array not sorted, advantage: add directly at the end of the array, fast. Disadvantages: Slow search speed.
Array sort, advantage: can use binary search, fast search, disadvantage: in order to ensure the array order, when adding new data, find the insertion bit
1.2 Use chained storage – linked list
Lists are slow to find whether they are ordered or not, and data is added faster than arrays without moving the data as a whole. [Schematic diagram]
1.3 Using a binary sort tree
Binary Sort Tree: BST: (Binary Sort(Search) Tree) for any non-leaf node in the Binary Sort Tree, the value of the left child is required to be smaller than the value of the current node, and the value of the right child is required to be larger than the value of the current node. 天安门事件
Note: If you have the same value, you can put the node on the left child node or the right child node
For example, for the previous data (7, 3, 10, 12, 5, 1, 9), the corresponding binary sorting tree is:
Binary sort tree creation and traversal
Array(7, 3, 10, 12, 5, 1, 9); Array(7, 3, 10, 12, 1, 9);
3. Delete binary sort tree
The deletion of binary sort tree is complicated, and the following three cases need to be considered
- Remove leaf nodes (e.g., 2, 5, 9, 12)
- (1) Need to find the node targetNode to delete first
- (2) Find the parent of targetNode
- (3) Determine whether targetNode is the left or right child of parent
- (4) Delete according to the previous situation
Parent. left = null
Parent. right = null;
- Delete a node with only one subtree (e.g. : 1)
(1) Need to find the node targetNode to delete first
(2) Find the parent of targetNode
(3) Determine whether the child of targetNode is left child or right child
(4) Is targetNode the left child or the right child of parent
(5) If targetNode has left children
5.1 If targetNode is the left child of parent
parent.left = targetNode.left;
5.2 If targetNode is the right child of parent
parent.right = targetNode.left;
(6) If targetNode has right children
6.1 If targetNode is the left child of parent
parent.left = targetNode.right;
6.2 If targetNode is the right child of parent
parent.right = targetNode.right
- Delete a node with two subtrees (e.g., 7, 3,10).
(1) Need to find the node targetNode to delete first
(2) Find the parent of targetNode
(3) Find the smallest node from the right subtree of targetNode
(4) Use a temporary variable, save the value of the smallest node temp = 11
(5) Delete the minimum node
(6)targetNode.value = temp
4. Code implementation
1. Create a Node
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
// Find the node to delete
/ * * * *@paramValue Specifies the value * of the node that you want to delete@returnReturns the node if found, null */ otherwise
public Node search(int value) {
if(value == this.value) { // find this node
return this;
} else if(value < this.value) {// If the value is smaller than the current node, recurse to the left subtree
// If the left child is empty
if(this.left == null) {
return null;
}
return this.left.search(value);
} else { If the value is not less than the current node, recurse to the right subtree
if(this.right == null) {
return null;
}
return this.right.search(value); }}// Find the parent of the node to be deleted
/ * * * *@paramValue Specifies the value of the node to be found *@returnReturns the parent of the node to be deleted, or null */ if not
public Node searchParent(int value) {
Return if the current node is the parent of the node to be deleted
if((this.left ! =null && this.left.value == value) ||
(this.right ! =null && this.right.value == value)) {
return this;
} else {
// If the value is less than the value of the current node and the left child of the current node is not null
if(value < this.value && this.left ! =null) {
return this.left.searchParent(value); // Recursive search to left subtree
} else if (value >= this.value && this.right ! =null) {
return this.right.searchParent(value); // Find the right subtree recursively
} else {
return null; // No parent is found}}}@Override
public String toString(a) {
return "Node [value=" + value + "]";
}
// The method of adding nodes
// Add nodes recursively. Note that it needs to meet the requirements of binary sorting tree
public void add(Node node) {
if(node == null) {
return;
}
// Determine the relationship between the value of the node passed in and the value of the root of the current subtree
if(node.value < this.value) {
// If the current node's left child is null
if(this.left == null) {
this.left = node;
} else {
// Add recursively to the left subtree
this.left.add(node); }}else { // The value of the added node is greater than the value of the current node
if(this.right == null) {
this.right = node;
} else {
// Add recursively to the right subtree
this.right.add(node); }}}// middle order traversal
public void infixOrder(a) {
if(this.left ! =null) {
this.left.infixOrder();
}
System.out.println(this);
if(this.right ! =null) {
this.right.infixOrder(); }}}Copy the code2. Create a binary sort tree
class BinarySortTree {
private Node root;
public Node getRoot(a) {
return root;
}
// Find the node to delete
public Node search(int value) {
if(root == null) {
return null;
} else {
returnroot.search(value); }}// Find the parent
public Node searchParent(int value) {
if(root == null) {
return null;
} else {
returnroot.searchParent(value); }}// Write method:
//1. Return the value of the smallest node in the binary sort tree with node as the root
//2. Delete the smallest node in the binary sort tree where node is the root node
/ * * * *@paramThe node passed in as the root of the binary sort tree *@returnReturns the value */ of the smallest node in the binary sorting tree with node as the root
public int delRightTreeMin(Node node) {
Node target = node;
// Loop through the left child node to find the minimum
while(target.left ! =null) {
target = target.left;
}
// Target is the smallest node
// Delete the smallest node
delNode(target.value);
return target.value;
}
// Delete the node
public void delNode(int value) {
if(root == null) {
return;
}else {
//1. Need to find the node targetNode to delete
Node targetNode = search(value);
// If no node to delete is 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;
}
// find the parent of the targetNode
Node parent = searchParent(value);
// If the node to be deleted is a leaf node
if(targetNode.left == null && targetNode.right == null) {
// Determine whether targetNode is the left or right child of the parent
if(parent.left ! =null && parent.left.value == value) { // is the left child
parent.left = null;
} else if(parent.right ! =null && parent.right.value == value) {// is made of children
parent.right = null; }}else if(targetNode.left ! =null&& targetNode.right ! =null) { // Delete the node with two subtrees
int minVal = delRightTreeMin(targetNode.right);
targetNode.value = minVal;
} else { // Delete a node with only one subtree
// If the node to be deleted has a left child
if(targetNode.left ! =null) {
if(parent ! =null) {
// If targetNode is the left child of parent
if(parent.left.value == value) {
parent.left = targetNode.left;
} else { // targetNode is the right child of parentparent.right = targetNode.left; }}else{ root = targetNode.left; }}else { // If the node to be deleted has a right child
if(parent ! =null) {
// If targetNode is the left child of parent
if(parent.left.value == value) {
parent.left = targetNode.right;
} else { // If targetNode is the right child of parentparent.right = targetNode.right; }}else {
root = targetNode.right;
}
}
}
}
}
// The method of adding nodes
public void add(Node node) {
if(root == null) {
root = node;// If root is empty, direct root to node
} else{ root.add(node); }}// middle order traversal
public void infixOrder(a) {
if(root ! =null) {
root.infixOrder();
} else {
System.out.println("Binary sort tree is empty and cannot be traversed."); }}}Copy the code3. The test
public static void main(String[] args) {
int[] arr = {7.3.10.12.5.1.9.2};
BinarySortTree binarySortTree = new BinarySortTree();
// loop to add nodes to the binary sort tree
for(int i = 0; i< arr.length; i++) {
binarySortTree.add(new Node(arr[i]));
}
// The middle order traverses the binary sort tree
System.out.println("Middle order traversal binary sort tree ~");
binarySortTree.infixOrder(); // 1, 3, 5, 7, 9, 10, 12
// Test removing leaf nodes
binarySortTree.delNode(12);
binarySortTree.delNode(5);
binarySortTree.delNode(10);
binarySortTree.delNode(2);
binarySortTree.delNode(3);
binarySortTree.delNode(9);
binarySortTree.delNode(1);
binarySortTree.delNode(7);
System.out.println("root=" + binarySortTree.getRoot());
System.out.println("After deleting the node");
binarySortTree.infixOrder();
}
Copy the code