Technology Sharing

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Binary Search Tree Concept

A binary search tree, also known as a binary sorted tree or a binary search tree, is a type of binary tree that has the following three characteristics.

1.二叉搜索树的左子树上的所有节点的val值均小于根节点的val值；
2.二叉搜索树的右子树上的所有节点的val值均大于根节点的val值；
3.二叉搜索树树的做右子树均为二叉搜索树。
1
2
3

Simply put, all nodes of this binary tree satisfy: left child < parent node < right child.

Binary Search Tree Operations

Searching a binary search tree

The search of a binary search tree is a bit like a binary search. If the value is smaller than the root node, go to the left subtree, and if it is larger than the root node, go to the right subtree. You can search at most times. If you reach the empty space and still can't find the value, it means that the value does not exist.

Insertion into a binary search tree

First, follow the search method, and insert the node if it is empty, thus completing the insertion of the binary search tree.

Deletion in a binary search tree

Deleting nodes in a binary search tree needs to be done according to different situations.

1.删除节点没有孩子，则可以直接删除。
2.删除节点有左孩子，被删除节点的父节点指向左孩子，然后直接删除该节点、
3.删除节点有右孩子，被删除节点的父节点指向右孩子，然后直接删除该节点。
4.删除节点有左右孩子，则找到右孩子中的最小值（中序遍历可以找到），用这个最小值取代该节点。
1
2
3
4