What is a binary search tree

Binary search tree is also called binary search tree or binary sorting tree. A binary search tree is organized as a binary tree and can be represented by a linked list data structure, in which each node is An object; generally, in addition to key and satellite data, each node also contains attributes lchild, rchild and parent.

Binary Search Tree (Binary Search Tree), (also: binary search tree, binary sorting tree) it is either an empty tree, or is a binary tree with the following properties: If its left subtree is not empty, then the values ​​of all nodes on the left subtree are less than the value of its root node; If its right subtree is not empty, then the values ​​of all nodes on the right subtree are less than the value of its root node. The values ​​of all nodes are greater than the value of its root node; its left and right subtrees are also binary sorted trees respectively. As a classic data structure, binary search tree has the characteristics of fast insertion and deletion operations of linked lists, and the advantage of fast search of arrays. Therefore, it is widely used. For example, it is generally used in file systems and database systems. Data structures perform efficient sorting and retrieval operations.

Principle

Binary search tree (BST) is also called binary search tree or binary sorting tree. A binary search tree is organized as a binary tree and can be represented by a linked list data structure, in which each node is an object. Generally, in addition to key and satellite data, each node also contains attributes lchild, rchild, and parent, which point to the node's left child, right child, and parents (parent nodes) respectively. If a child node or parent node does not exist, the value of the corresponding attribute is NIL. The root node is the only node in the tree whose parent pointer is NIL, and the child node pointers of leaf nodes are also NIL.

Structure

Binary search tree is a data structure that can efficiently perform the following operations.

1. Insert a value

2. Query whether a certain value is included

3. Delete a certain value

The above is the detailed content of What is a binary search tree. For more information, please follow other related articles on the PHP Chinese website!