0
Follow
0
View

# The number of nodes in the bottom layer of the corresponding decision tree is

dd330825197610124545 注册会员
2023-02-28 02:25

The number of nodes in the bottom layer depends on the success of the lookup. If the element to be found happens to be in the middle, then it only takes one comparison to find it, and the bottom level only has one node. However, if the element is located at both ends of the table, \$log_2n\$comparison is needed to find the element successfully, and the lowest level will have \$n/2\$nodes. Thus, in a half search, the number of knots at the bottom level is not fixed, but values between 1 and \$n/ \$2.

dian19920226 注册会员
2023-02-28 02:25
• Half-search, also known as binary search, is an algorithm used to find the target element in an ordered array. Each comparison halves the search interval to narrow the search until the target element is found or the search interval is empty.
• Half search for an ordered table of length n. Each comparison can halve the search interval, so at most log2(n) comparisons are required to narrow the search interval to one element. Therefore, the height of the decision tree is log2(n).
• The number of nodes in the bottom layer of the decision tree is equal to the number of elements in the last search interval, that is, 1. Therefore, when the ordered table of length n=50 is searched in half, the number of nodes in the bottom layer of the decision tree is 1.
sundahai_3 注册会员
2023-02-28 02:25

32 is the total number of nodes in the last layer, but there are only 50 nodes in the decision tree. The number of nodes in the first 5 layers is 2^5-1=31 nodes, and then 50-31=19 Ah, I drew a graph with 19 nodes

danny_lx 注册会员
2023-02-28 02:25

For an ordered table of length n, the split half search algorithm will start the comparison in the middle of the table, then select the first or second half for the next comparison based on the comparison results, and so on until the target element is found or determined not to exist in the table.

Each comparison halves the search section, so you need to perform a maximum of log₂n comparisons to complete the search. In decision tree, therefore, the bottom layer of nodes is performed to compare the number of times that the log ₂ 50 material 5, so the bottom layer of nodes for 2 ⁵ = 32.

dizheng1982 注册会员

Publish Time
2023-02-28 02:25
Update Time
2023-02-28 02:25