См. Википедию:
Типы бинарных деревьев
- Идеальное двоичное дерево - это полное двоичное дерево, в котором все листья находятся на одной глубине или на одном уровне. (Это также неоднозначно называется полным двоичным деревом.)
- Полное двоичное дерево - это двоичное дерево, в котором каждый уровень, за исключением, возможно, последнего, полностью заполнен, а все узлы расположены как можно левее.
Так что здесь присутствует двусмысленность. С определением complete = perfect эти два не являются полными. Но со вторым определением, первое, так как, за исключением нижнего уровня, оно идеально, и все листья на нижнем уровне находятся в крайнем левом углу дерева.
В качестве примечания, википедия ссылается на NIST, а страница NIST указывает это в идеальном двоичном дереве:
This kind of tree is called "complete" by some authors ([CLR90, page 95], Leighton) and "full" by others (Budd page 331, Carrano & Prichard page 429, Ege, [HS83, page 225], and Sahni page 461).
Для тех, кто не распознает, CLR составляет Corman, Leiserson, Rivest, которые являются авторами Introduction to Algorithms.
С другой стороны, второе определение используется в KDE «Искусство компьютерного программирования» (см. Complete Binary Tree в Wolfram Mathworld) , которая является одной из немногих книг в области алгоритмов, которая имеет больший вес чем CLR.