Shulou(Shulou.com)06/03 Report--

In this issue, the editor will bring you about the role of binary search tree. The article is rich in content and analyzed and described from a professional point of view. I hope you can get something after reading this article.

Binary search tree is mainly used for search and dynamic sorting. The time complexity of binary tree for "insert / query / delete" is "O (log (n))", but it is usually not so fast in actual use, because the "middle" used in the insertion order is usually not so accurate.

The function of binary search tree

The main role I know is search and dynamic sorting, and the time complexity of binary tree insert / query / delete is O (log (n)). But the actual use is usually not so fast, because the middle you use to insert the order is usually not so accurate, especially when the order of inserting data is orderly or basically orderly, the binary tree will be seriously unbalanced and, in the worst case, it will drop to the same as the linked list.

The main operations of a binary sort tree are:

1. Lookup: recursively looks for the existence of key.

two。 Insert: key does not exist in the original tree, insert key returns true, otherwise returns false.

3. Construction: the insert operation of a loop.

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

(2) only the node with left or right subtree: after the node is deleted, the whole left or right subtree can be moved to the position where the node is deleted, and the child inherits the work of the parent.

(3) nodes with both left and right subtrees: find the direct precursor or direct successor s of the node p to be deleted, replace node p with s, and then delete node s.

The above is the role of the binary search tree shared by the editor. If you happen to have similar doubts, you might as well refer to the above analysis to understand. If you want to know more about it, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.