Binary decision tree, also called binary sort tree, is either an empty tree or a binary tree, and has the following properties:

(1) If the left subtree is not empty, the values of all nodes in the left subtree are less than the values of their root nodes;

(2) If the right subtree is not empty, the values of all nodes on the right subtree are greater than or equal to the values of their root nodes;

(3) The left and right subtrees are also binary sort trees.

Extended data:

seek

Steps:

binary tree

If the keyword value of the root node is equal to the searched keyword, it is successful.

Otherwise, if it is less than the key value of the root node, the left subtree is checked recursively.

If it is greater than the key value of the root node, recursively check the subtree on the right.

If the subtree is empty, the search is unsuccessful.

Average situation analysis (if two kinds are successfully found):

In general, let P(n, I) be the average search length when the number of nodes in its left subtree is I, as shown in the figure, the number of nodes is n = 6 and I = 3；; Then p (n, I) = p (6,3) = [1+(p (3)+1) * 3+(p (2)+1) * 2]/6 = [1+.

Note: P(3) and P(2) are the average search lengths of binary classification trees with 3 nodes and 2 nodes. Generally speaking, P(i) is the average search length of a binary classification tree with I nodes. Average search length = total depth of each node/total points.

Baidu Encyclopedia-Binary Sort Tree