There are several ways to implement a binary search tree

One way to implement a binary search tree is to use a linked list. A linked list is a non-continuous and non-sequential storage structure on a physical storage unit. The logical order of data elements is linked through pointers in the linked list. It is implemented sequentially, and the linked list is composed of a series of nodes, and the nodes can be dynamically generated at runtime.

Binary Search Tree

Binary Search Tree is a pair of A special binary tree that is useful for sorting and searching

Definition: left subtree< root node< right subtree

Implementation method: Generally, a linked list is used to implement the

operation set : Create a binary tree, determine whether it is empty, traverse, search, find the smallest element, find the largest element, insert, delete

Time complexity: bestO(logN) worstO(N)

Related introduction:

The linked list is a non-continuous and non-sequential storage structure on the physical storage unit. The logical order of the data elements is through the linked list. Pointer link order is implemented. A linked list consists of a series of nodes (each element in the linked list is called a node), and nodes can be dynamically generated at runtime. Each node consists of two parts: one is the data field that stores data elements, and the other is the pointer field that stores the address of the next node. Compared with the linear table sequence structure, the operation is complicated. Since it does not have to be stored in order, the linked list can achieve O(1) complexity when inserting, which is much faster than another linear list, sequential list, but finding a node or accessing a specific numbered node requires O(n) time, and the corresponding time complexities of linear tables and sequential tables are O(logn) and O(1) respectively.

Using the linked list structure can overcome the shortcoming of the array linked list that the data size needs to be known in advance. The linked list structure can make full use of the computer memory space and achieve flexible dynamic memory management. However, the linked list loses the advantage of random reading of the array, and at the same time, the space overhead of the linked list is relatively large due to the increase of the pointer field of the node. The most obvious benefit of a linked list is that the way a regular array arranges associated items may be different from the order in which these data items are arranged in memory or on disk, and access to data often requires switching between different arrangements. Linked lists allow insertion and removal of nodes at any location on the list, but do not allow random access. There are many different types of linked lists: one-way linked lists, doubly linked lists, and circular linked lists. Linked lists can be implemented in a variety of programming languages. The built-in data types of languages ​​like Lisp and Scheme include the access and operation of linked lists. Programming or object-oriented languages ​​such as C, C and Java rely on mutable tools to generate linked lists.

The above is the detailed content of There are several ways to implement a binary search tree. For more information, please follow other related articles on the PHP Chinese website!