News for hackers. Stuff that matters.

CLRS and Knuth disagree in the definition of “complete k-ary tree”

In CLRS (as recently as the fourth edition), a "complete k-ary tree" is defined as a tree in which "all leaves have the same depth and all internal nodes have degree k".

Knuth (as well as nearly every other source I'm aware of) uses an entirely different definition: "a k-ary tree in which all levels are filled except possibly the last, and in the last level, all nodes (which must be leaves) are as far to the left as possible".

One consequence is that the Knuth definition allows leaves at different depths. For example, a tree with two nodes: one root and a child, is a complete binary tree according to Knuth, but not according to CLRS.

I emailed the authors of CLRS a few months ago before the fourth edition was released, and was told that they acknowledge the difference, but did not have space to mention it because they were up against a publisher-enforced page count.

( 9 comments | 10 points | on HN )
Re:CLRS and Knuth disagree in the definition of “complete k-... by Ferrotin on Saturday April 09, 2022 @10:25PM (#30973947)
The good news is, a “complete K-ary tree with N nodes” is unambiguous.

> One consequence is that the Knuth definition allows leaves at different depths. For example, a tree with two nodes: one root and a child

But that only has one leaf.

Re:CLRS and Knuth disagree in the definition of “complete k-... by xdavidliu on Sunday April 10, 2022 @12:20AM (#30974450)
yes, one leaf satisfies Knuth's definition: it has all levels full (the root) except for possibly the last (the leaf).
Re:CLRS and Knuth disagree in the definition of “complete k-... by Ferrotin on Sunday April 10, 2022 @01:10AM (#30974627)
I’m saying, that’s not an example of leaves on different levels.
Re:CLRS and Knuth disagree in the definition of “complete k-... by kazinator on Sunday April 10, 2022 @12:48AM (#30974549)
It seems to be that Knuth's definition requires the word "complete" to have a meaning that is quite disconnected from its ordinary one.
Re:CLRS and Knuth disagree in the definition of “complete k-... by taktoa on Saturday April 09, 2022 @11:34PM (#30974273)
I always learned/used the CLRS definition, despite having never read that book.
Re:CLRS and Knuth disagree in the definition of “complete k-... by xdavidliu on Sunday April 10, 2022 @12:21AM (#30974453)
out of curiosity, is there anywhere else that uses the CLRS definition? All other sources, including wikipedia and academic papers that I've found use the Knuth definition.
Re:CLRS and Knuth disagree in the definition of “complete k-... by Pet_Ant on Sunday April 10, 2022 @07:28AM (#30976154)
Anyone care to spell out which book CLRS is?
Re:CLRS and Knuth disagree in the definition of “complete k-... by chronal on Sunday April 10, 2022 @10:53AM (#30977421)
Re:CLRS and Knuth disagree in the definition of “complete k-... by Pet_Ant on Tuesday April 12, 2022 @12:39PM (#31004992)
Okay, so I'm guessing CLRS comes from the last names of the authors:

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein