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

This article mainly explains "how to understand and master Java binary search tree". Interested friends may wish to have a look at it. The method introduced in this paper is simple, fast and practical. Now let the editor take you to learn "how to understand and master the Java binary search tree"!

I. introduction

Binary search tree, English full name: Binary Search Tree, abbreviated as: BST, it is the earliest practical tree structure in computer science, and its characteristics are as follows:

If the left subtree is not empty, the value of all nodes on the left subtree is less than the value of its root node.

If the right subtree is not empty, the value of all nodes on the right subtree is greater than or equal to the value of its root node.

Its left and right subtrees are also binary search trees, respectively.

The definition of properties is extensive, so there is a variety of tree structures, such as the following figure:

The above three graphs a, b, c all meet the above characteristics, also known as binary search tree, although a valid array can be obtained by traversing the middle order: [1, 2, 3, 4, 5, 6, 7, 8]. However, in terms of search efficiency, there are some differences, such as querying the content with a target of 8, starting from the root directory, and the structure is as follows:

A figure, need 5 times

B figure, need 3 times

C figure, need 8 times

Thus it can be seen that the number of searches is different for different shapes, which will be described in detail when we introduce the data structure of balanced binary search tree and red-black tree.

Although the binary search tree has different search efficiency under different shapes, it is the basis for learning other tree structures. I believe it will be much easier to understand other binary tree structures after understanding the algorithm of binary search trees.

Second, the idea of algorithm

2.1. Add

Adding an element means adding an element to the binary tree, which is relatively simple. If the binary tree is empty, the default first element is the root node. If the binary tree is not empty, the left and right nodes are added based on the above-mentioned characteristics.

2.2, find

The lookup element means to find the element from the root node. if the root node is empty, the null value is returned directly. if it is not empty, it is judged on the basis that the left child tree is smaller than the parent node and the right child tree is larger than the parent node. then look for the element recursively until the target element is found.

2.3. Delete

Deleting an element means removing the element to be deleted from the binary tree, and the logic is slightly more complicated. Similarly, it is necessary to determine whether the root node is empty, if so, return directly, and if not, consider the situation.

Deleted node, the right subtree is empty

In this scenario, you only need to move the parent node of the left child tree of the deleted element to the parent node of the deleted element, and then remove the deleted element.

Deleted node, left subtree is empty

In this scenario, similar to the above, you only need to move the parent node of the right child tree of the deleted element to the parent node of the deleted element, and then remove the deleted element.

Deleted node, left and right subtrees are not empty

In this kind of scene, if it is a little more complicated, we first locate the target element to be deleted. According to the characteristics that the content of the left child node must be smaller than that of the current node, we find the left subtree of the target element. Through recursive traversal, we find the right subtree of the left subtree of the target element, find the end element, replace it with the target element, and finally remove the end element.

2.4, ergodic

The traversal of binary trees can be divided into two categories:

Hierarchical traversal, starting from the root node

Depth traversal can be divided into three ways: pre-order, middle order and post-order traversal.

2.4.1, hierarchical traversal

Hierarchical traversal, the idea of the algorithm is relatively simple, starting from the root node, hierarchical traversal elements from left to right.

2.4.2, depth traversal

There are three kinds of depth traversal in the starting position of traversal, which are pre-order traversal, mid-order traversal and post-order traversal, and the output results of each traversal mode are different.

Preorder traversal: start from the root-> left subtree-> right subtree

Traversal in the middle order: start with the outermost left subtree-> tree root-> right subtree

Traversal after order: from the end of the left subtree-> the right subtree-> to the root of the tree

Although there are many ways to traverse the binary tree, it will be much easier as long as we master the train of thought and principle and then realize it.

Third, code practice

First, create an entity data structure BSTNode, which is as follows:

Then, create a binary lookup tree operation class BinarySearchTree, which reads as follows:

Finally, let's test it. The code is as follows:

Output result:

= insert element = insert keyword key=5 insert keyword insert keyword key=2 insert keyword key=7 insert keyword key=1 insert keyword key=6 insert keyword key=4 insert keyword key=8 insert keyword key=9 insert keyword key=10 = order traversal element = key:1 key:2 key:3 key:4 key:5 key:6 key:7 key:8 key:9 key:10 = find elements with key 9 = search keyword key=9 search path [5-> 7-> 8-> 9->] True = delete the element with key 10 = delete the keyword key=10 to start searching for the target element [5-> 7-> 8-> 9-> 10->], and delete the result successfully: true = iterate through the element again = key:1 key:2 key:3 key:4 key:5 key:6 key:7 key:8 key:9 to this I believe you have a deeper understanding of "how to understand and master the Java binary search tree". 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.