What is the use of binary search tree?

Binary search trees are mainly used for search and dynamic sorting. The time complexity of "insertion/query/deletion" of binary trees is "O(log(n))", but it is usually not used in actual use. It's so fast because the "middle" used in the insertion order is usually not that accurate.

The role of binary search tree

The main role I know is search and dynamic sorting, The time complexity of inserting/querying/deleting in a binary tree is O(log(n)). However, it is usually not so fast in actual use, because the middle used in the insertion order is usually not so accurate. Especially when the order of inserting data is ordered or basically ordered, the binary tree will be seriously unbalanced. In the worst case it will drop to the same level as a linked list.

The main operations of binary sorting tree are:

1. Search: recursively search whether the key exists.

2. Insertion: The key does not exist in the original tree. If the key is inserted, it returns true, otherwise it returns false.

3. Construction: cyclic insertion operation.

4. Delete: (1) Leaf node: delete directly without affecting the original tree.

(2) Only nodes with left or right subtrees: After the node is deleted, just move its entire left subtree or right subtree to the position of the deleted node, and the son will inherit the father's legacy.

(3) Nodes with both left and right subtrees: Find the direct predecessor or direct successor s of the node p that needs to be deleted, replace the node p with s, and then delete the node s.

The above is the detailed content of What is the use of binary search tree?. For more information, please follow other related articles on the PHP Chinese website!