Path Length of Binary Search Trees (Q5650276)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3380502
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Path Length of Binary Search Trees |
scientific article; zbMATH DE number 3380502 |
Statements
Path Length of Binary Search Trees (English)
0 references
1972
0 references
0.8890554904937744
0 references
0.8498255610466003
0 references
0.8498255610466003
0 references
0.8443057537078857
0 references
An algorithm is given for constructing a binary tree of minimum weighted path length and with restricted maximum path length. (Huffman's tree is a binary tree of minimum weighted path length with no restriction on maximum path length.) When an alphabetical ordering of the terminal nodes is introduced, the binary tree is called an alphabetic binary tree. We show that Huffman's algorithm for optimal binary trees coincides with the T-C algorithm for optimal alphabetic binary trees when the terminal nodes have monotonically increasing weights from left to right.
0 references
