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

This article is about how Java implements a binary sort tree. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

An overview of 1 binary sort tree

For common search algorithms, such as sequential search, binary search, insert search, Fibonacci search is not clear, you can read this article: detailed explanation of common search algorithms and the implementation of Java code.

Assuming that the dataset you are looking for is stored in an ordinary order, then the insert operation is to put the records at the end of the table and add one to the number of table records, and the delete operation can be deleted, the subsequent records move forward, or the elements to be deleted are interchanged with the last element, and the number of table records is subtracted by one. Anyway, the whole dataset does not have any order, which is also very efficient. It should be said that inserts and deletions are acceptable for sequential storage structures, but such tables are inefficient because of disorder.

If the data set you are looking for is an ordered linear table and is stored sequentially, the search can be achieved by using search algorithms such as halving, interpolation, Fibonacci and so on. Unfortunately, because of the order, in order to maintain the order of insert and delete operations, it takes a lot of time to move a large number of elements.

Is there an algorithm that can not only make insertion and deletion efficient, but also achieve search efficiently? This is the binary sort tree.

Binary sort tree (Binary Sort Tree), also known as binary search tree / binary search tree (binary search tree). It is a binary tree with the following properties:

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

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

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

A binary sort tree can also be an empty tree.

The main purpose of constructing a binary sort tree is not to sort, but to improve the speed of finding, inserting and deleting keywords, and to improve the comprehensive ability of the data structure. In any case, the search speed on an ordered data set is always faster than that of an unordered data set, and the non-linear structure of binary sort tree is also conducive to the implementation of insertion and deletion.

2 Construction of binary sort tree 2.1 class architecture

First of all, the simplest node object still requires a data domain and two reference domains.

You also need a reference to the comparator, because you need to sort the elements, so you naturally need to compare the size of the elements. if a comparator is passed externally, compare it with a user-specified comparator, otherwise, the data type E must be a subclass of the Comparable interface, otherwise an error will be reported because it cannot be compared.

In addition, you need to provide a method of traversing the middle order, which will display the results of the binary sort tree sequentially.

Public class BinarySearchTree {/ * externally saves the reference to the root node * / private BinaryTreeNode root; / * * Custom comparator * / private Comparator

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.