Data structure: binary search tree

concept

Binary search tree is a kind of data structure, using the tree structure of graph, data stored in each node of binary search tree.

Binary search tree is also called binary search tree or binary sort tree.

The figure shows an example of a binary lookup tree.

Like a heap, each node has at most two children
The value of each node is greater than the value of any node in its left subtree
The value of each node is less than the value of any node in its right subtree
To find the minimum value in a binary tree, start at the top and find its left subtree
To find the maximum value in a binary tree, start at the top and find its right subtree

Start by finding the position of the number from the top node of the binary search tree
Compare the value of the node you want to add to that node
If the value of the node to be added is less than the value of the current node move to the left otherwise move to the right
After moving left or right, it continues to compare with its child node, and repeat Step 3 to determine whether to move left or right
When the child node to the current node does not exist, the data is inserted

Example 1, insert the number 1 into a two-lookup tree.

The inserted data is compared to the top node of the tree, with 1<15 moving to the left
After the left shift, compared with the child node 9 of 15, the data of 1<9 moves to the left
After moving to the left, compared with the child node 3 of 9, the data of 1<3 moves to the left. Since 3 has no children, 1 is added to the lower left as a new node
At this point, the addition of 1 is complete

Example 2, insert the number 4 into a binary lookup tree.

As in the example 1 step, compare with the node at the top of the binary tree, because 4<15, the data moves to the left
Compare the inserted node with the child node 9 of 15, 4<9, and the data moves to the left
Compare the inserted node with the child node 3 of 9, 4>3, and the data moves right
Compare the inserted node with the child of 3, 8, 4>8, the data moves to the left, 8 has no children, so add 4 as a new node to the lower left
At this point, the addition of 4 is complete

When deleting a node, determine whether the node to be deleted has children. If the children do not exist, delete them directly
If the node to be deleted has only one child, delete the target node first and then move the child node to the location of the deleted node
If the node to be deleted has multiple children, delete the target node first, then search for the maximum node in the left subtree of the deleted node, and finally move the maximum node to the position of the deleted node. If the node to be moved still has children, recurse the previous operation.
When there are multiple children, the smallest node can also be found in the right subtree of the deleted node and moved to the location of the deleted node.

Example 1, delete the node with the number 28

Example 2, delete node 8

Example 3, delete node 9

First, start at the top of the binary tree and work your way down.
As with adding data, the nodes to be looked up are compared to those in the tree, smaller than that and moved to the left, otherwise to the right

For example, find node 12 in the tree

Start from the top node of the binary search tree to search down, the node 12 to be queried is compared with the top node 15,12<15, the data moves to the left
After moving to the left, the node 12 to be queried is compared with the child node 4 of node 15, 5<12, and the data is moved to the right
After moving to the right, node 12 is found and the query ends

The pictures used in this article are from “my first algorithm book”, if infringement, please leave a message in the comment section, the author immediately delete the relevant pictures.
If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
This article was first published in nuggets. Reprint is prohibited without permission 💌