algorithm on optimization binary search tree

Question

I am reading about optimal BST algorithm at

http://www.cs.yorku.ca/~andy/courses/3101/lecture-notes/OptBST.pdf

Here on page 3 author mentioned as below

More specifically, we start the induction with minimum cost trees each of which contains exactly one key, and proceed by constructing minimum cost trees with 2, 3, . . . , n successive keys. Note that there are exactly n - d +1 groups of d successive keys for each d = 1, . . . , n. Thus, instead of considering all possible trees with n nodes we consider only n (minimum cost) trees with 1 node each, n -1 (minimum cost) trees with 2 nodes each, . . ., 1 minimum cost tree with n nodes, i.e. a total of n(n +1)/2 trees.

On above text

What does author mean by "there are there are exactly n - d +1 groups" ?
Another question what does author mean by (n-1) minimum cost trees with 2 nodes, n-2 minimum cost trees with 3 nodes?

Sparrow · Accepted Answer · 2015-09-09 11:51:40Z

0

It seems d is count of nodes (keys) in group;

so if there is 1 node in group, there are n groups;

if there are 2 nodes in group, n - 2 + 1 = n - 1 groups

n nodes in group: n - n + 1 = 1 group

answered Sep 9, 2015 at 11:51

Sparrow

887 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

algorithm on optimization binary search tree

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related