Optimal binary search tree

Binary search tree

Is an empty tree or satisfies the following properties ：

Each node is used as the search object , Its keywords are different from each other .
For all nodes in the tree , If it has a left subtree , Then the keywords of all nodes on the left subtree are less than the keywords of the node .
For all nodes in the tree , If it has a right subtree , Then the keywords of all nodes on the right subtree are greater than the keywords of the node .

search process ：

Start at root , If the root is empty , Then the search is unsuccessful ; Otherwise, use the value to be searched to compare with the root node , If the value to be searched is equal to the root node keyword , If the search is successful, return , If it is less than the root node , Search to the left subtree ; If it is larger than the root node , Then search the right subtree .
For a given set of keywords , There may be several different binary search trees
For example, a subset of reserved words
Name： 1 2 3 4 5
for if loop repeat while
The two binary search trees are

consider a Map and b The worst comparison times and average comparison times in the figure
Constructing different binary search trees has different performance characteristics .
Binary search tree a In the worst case, finding an identifier requires 4 Compare it to , and b In the worst case, the binary search tree only needs 3 Compare it to .
Suppose that only successful retrieval is made and the probability of retrieving each identifier is the same , Then the two binary search trees each need 12/5 and 11/5 Compare it to .

The best binary search tree

There are two problems

1 In practice, unsuccessful retrieval will also be encountered .
2 In practice, , Different identifiers have different retrieval probabilities .
For a given set of identifiers , Hope to give a method of constructing binary search tree , The binary search tree has the best performance .

In practice, unsuccessful retrieval will also be encountered

Expand the binary tree ： When an empty subtree appears in a binary tree , Add new 、 Special nodes —— Empty leaves . For the original binary tree, the degree is 1 Branch node of , Add an empty leaf under it ; For the leaves of the original binary tree , Add two empty leaves under it .
An extended binary tree is a full binary tree , New empty leaves （ Hereinafter referred to as external node ） The number of nodes of the original binary tree （ Hereinafter referred to as internal nodes ） Number plus 1.

Search for an element in a binary search tree x

set up S={x1, x2, ···, xn} Is an ordered set , And x1, x2, ···, xn A binary search tree representing an ordered set uses the vertices of the binary tree to store the elements in the ordered set , And it has properties ：
Elements stored in each vertex x Larger than the element stored in any vertex of its left subtree , Smaller than the element stored in any vertex of its right subtree . The leaf vertices in a binary tree are shaped like (xi, xi+1) The open range of .
(1) Find... At the inner vertex of the binary tree ： x = xi
(2) Determine in the leaf vertices of a binary tree ： x∈ (xi , xi+1)

In practice, , Different identifiers have different retrieval probabilities .

Using dynamic programming to construct pairs of identifier sets
{a1, a2, …, an} Optimal binary search tree algorithm （ Including successful retrieval and unsuccessful retrieval ）.
example Identifier set {1, 2, 3}＝{do, if, stop} The possible binary search tree is ：

Set each inner 、 The retrieval probability of outer nodes is the same ：pi=qi=1/7,
Find the average number of comparisons for each tree （ cost ）.
if P1=0.5, P2=0.1, P3=0.05,
q0=0.15, q1=0.1, q2=0.05, q3=0.05, Find the average number of comparisons for each tree （ cost ）.
In the retrieval process , Every comparison , Just go to the next floor , For successful retrieval , The number of comparisons is the number of layers plus 1.
For unsuccessful retrieval , The retrieved key belongs to the set of possible keys represented by the external node , The number of comparisons is equal to the number of layers of this external node .

example ：

analysis
For the inner nodes of a graph , The first 0 The number of operations that the layer needs to compare is 1, The first 1 Layers need to be compared 2 Time , The first 2 Layers need 3 Time
Pb(n)=1 × p1 + 2 × p3+3 × p2 + 1×q0 + 3×( q2 + q3 )
=1 × 0.5+ 2 × 0.05 + 3 ×0.1 + 1×0.15 +2×0.05+ 3×( 0.05 + 0.05 )
=1.6
Pc(n)=1 × p2 + 2 × (p1 + p3) + 2×(q0 +q1 +q2 + q3 )
=1 × 0.1+ 2 × (0.5 + 0.05) + 2×(0.15 + 0.1 + 0.05 + 0.05)
=1.9
Pd(n)=1 × p3 + 2 × p1+3 × p2 + 1 × q3+2 × q0 +3 × (q1+ q2)
=1 × 0.05 + 2 × 0.5 + 3 × 0.1 + 1×0.05 + 2 × 0.15 + 3 × (0.1 + 0.05)
=2.15
Pe(n)=1 × p3 + 2 × p1+3 × p2 + 1 × q3+2 × q0 +3 × (q1 + q2)
=1 × 0.05 + 2 × 0.5 + 3 × 0.1 + 1×0.05 + 2 × 0.15 + 3 × (0.1 + 0.05)
=2.15
Element found x = xi The probability of is bi; determine x∈ (xi , xi+1) The probability of is ai. It is agreed that x0= －∞ , xn+1= + ∞ , Yes

In an expression S Two fork tree T in , Set storage element xi The node depth of is ci; leaf （xj,xj＋1） The node depth of is dj .

In binary search tree T The average number of comparisons required to make a search in .P Also known as binary search tree T Average road length , In general , The average path length of different binary search trees is different .

Description of optimal binary search tree problem

For ordered sets S And its access probability distribution （a0, b1, a1, ···, bn, an）, In all representations of ordered sets S Find a binary search tree with the minimum average path length .
The deeper the node is in the binary search tree , The more times you need to compare , So we should construct a minimum binary tree , Generally, try to put the nodes with higher search probability at a higher level .

Optimal substructural properties

Suppose you choose k For the root of a tree , be 1, 2, …, k-1 and a0, a1, …, ak-1 Will be located in the left subtree L On , Other nodes (k+1, …, n and ak, ak+1, …, an) Located in the right subtree R On .



set up COST(L) and COST They are binary search trees T Cost of the left and right subtrees of the .
Then the search tree T The cost of is ：
P(k)+ COST(L) + COST + ……
if T It's the best , Then the above formula and COST(L) and COST Must all take the minimum value .
Welcome to join me for wechat exchange and discussion （ Please note csdn Add ）