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

This article mainly explains "how to implement a binary search tree through code". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "how to implement a binary search tree through code".

First of all, what exactly is a binary search tree?

Binary search tree (BST) is a special type of tree data structure, which is composed of nodes and their child nodes, which are also regarded as "descendants". It can be thought of as an inverted tree or the root of a tree.

Each node can only have at most two child nodes: the left node and the right node. In order for it to be an effective binary search tree, the value of the left node must always be smaller than that of the parent node, and the value of the right node must always be greater than the parent node. BST without any gaps, that is, each node has a left node and a right node of the binary search tree, is called a "perfect" tree.

In the perfect tree, when traversing the tree, the number of nodes in each level doubles, and adding all the previous nodes and adding "1" to that number gives the total number of nodes at the bottom.

When searching for an element in a balanced binary search tree, the average amount of time spent is O (log n), and in the worst case, O (n) is required. You can think of the search in the binary search tree as a "choose your own adventure" model, starting with the top node, then going down the tree and asking the same two questions at each node you arrive.

Is the value I am looking for less than the current node? If so, go left.

Is the value I am looking for greater than the current node? If so, go right.

Inserts and deletions are also very fast, taking an average of O (log n) time. But one drawback is that you can't get random elements like an array.

When can I use a binary search tree?

Suppose you need to design a database for social media applications like Facebook. The database needs to process millions of user names, and one of them needs to be quickly retrieved during login. Since there are newly registered or deleted accounts every day, you also need to facilitate insertions and deletions.

A binary search through a sorted array can be very fast (it takes O (log n) time), but inserting or deleting a user name causes the entire array to be reordered, which takes O (n) time, depending on the size of the array and may be relatively slow. If we use a binary search tree, the insertion or deletion time will be much faster (taking O (log n) time).

If there is a binary search tree with a name (such as this finding Nemo tree), it can be arranged in alphabetical order.

In the alphabet, Dory comes before Marlin, so it is the node on the left, while Moonfish comes after Marlin, so it is the node on the right. Similarly, searching at the next level follows this rule. Bruce comes before Crush, as well as Dory and Marlin. Darla comes after Crush, but before Dory and Marlin.

Now get ready, it's time to find Nemo!

Looking for Nemo!

Suppose you already have a valid binary search tree and you need to find Nemo. Because we know that the nodes in the tree are sorted alphabetically, this should be quite simple.

Starting with Marlin, there is Dory on the left and Moonfish on the right. We know that Nemo comes after Marlin in the alphabet, so we will traverse to the correct node (Moonfish). Nemo is alphabetically listed after Moonfish, so move on to the right child node of Moonfish. Luckily, that's... Nemo! Found Nemo!

It's very efficient. Binary search tree reduces the time complexity of the whole search process! What if the tree is not classified and is just an ordinary tree structure? Or to prove that this is a binary search tree? There are currently two different search technologies that can achieve this.

What is breadth-first search?

Breadth-first search is a method of traversing one level at a time in a tree (or graph), moving between nodes from left to right each time.

In the case of finding Nemo, Marlin will first ask Dory, "do you know where my son Nemo is?" If it says no, Marlin will ask Moonfish the same question. If it says no, Marlin will go down and ask Crush, Gill, and Mr. Ray, and Marlin will find Nemo!

Breadth first search

If you do not find Nemo,Marlin after Mr. Ray, you will go to the next level to ask Bruce, Darla, and so on Use breadth-first search to find the shortest distance between the start node (Marlin) and the target node (Nemo). The time complexity is O (n), because in the worst case, each node needs to be checked to find the Nemo.

What is depth-first search?

Depth-first search (Depth first search) is a way to traverse the tree (or graph) from the top node down to its farthest child node, and then go back and try another path when the target node is not found.

In the case of finding Nemo, Marlin will first ask Dory, "do you know where Nemo is?" If she doesn't know, he asks Crush the same question because Crush is the leftmost child node of the Dory. If Crush says no, Marlin will move to the next level to ask Bruce, although he is afraid of becoming a shark snack, he will also ask him if he has seen his son.

Depth first search

If Bruce says he doesn't see Nemo and assures Marlin that "fish are friends, not food," Marlin needs to go back to his superiors and find another node he hasn't asked about. When he goes back to Crush, he will find that the next step is to ask Darla. Since all the offspring of Crush have now been interrogated, Marlin will go back to Dory to check on the rest of her offspring. Marlin needs to question each role before finding Nemo.

Depth first search order

Like breadth-first search, depth-first search also includes time complexity O (n), but space complexity may be different. Depth-first search usually takes up less memory or space, assuming that the target node can be found before traversing the entire tree.

Because each additional level of nodes in the binary search tree doubles (at least for the balanced tree), if the missing node (Nemo) is lower in the tree, depth-first search can be used to save memory. In the worst case, the space complexity of both methods is O (n).

There is still a lot to learn about binary search trees and how to implement them in code, but this interesting case will be a starting point for you to understand data structures.

At this point, I believe you have a deeper understanding of "how to achieve a binary search tree through code". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.