Résumé | In this talk, we consider weighted binary trees, i.e., binary trees whose leaves hold positive constants called weights. We survey different balance definitions for weighted binary trees and different algorithms to build them from a sequence of weights.
We consider the alphabetic version of the problem. In this case the leaves of the balanced alphabetic tree (read left-to-right) should be in the same order as in the original sequence. We present an incremental algorithm to build balanced alphabetic weighted trees in linear time. |