5 20 10 12 8 4 ?3 5 6 9
如何設計壹個內部電話號碼，讓話務員盡量少撥？
這是霍夫曼樹的應用。
壹種用於存儲和處理樹狀數據的數據結構，如家譜。
之所以應用廣泛，是因為根據數據結構理論，任何復雜的樹都可以轉化為二進制並進行處理。
二叉樹重排、搜索和大規模數據索引有許多應用。
二叉樹排序是簡單算法排序中最快的。
樹的壹大類是自平衡二叉查找樹(self-balanced BST)，有很多變種:RB樹是每個節點都是紅色或黑色，彩色返祖AVL樹是每個節點都包含壹個平衡因子，等於左高-右高；Splay tree是每個節點都有壹個帶有父節點的指針；Treap是每個節點有壹個隨機的優先級數，parent priority >；=子優先級.
自平衡二分搜索法樹經常出現在采訪中，但很少被互聯網編碼人員用於網頁。如果它們被用作映射，那麽直接使用散列表通常會更好。如果它們用於排序，最好直接使用排序算法...但也有有用的時候，比如求壹個數的上下界。
樹的另壹大類是Trie，它的特點是保證字典順序，存儲字典的空間壓縮率高，前綴搜索。Trie可用於常規匹配、數據壓縮和索引構建。還有很多變體:雙數組-trie的經典實現。
每個節點可以存儲壹個字符串而不僅僅是壹個字符Judy數組——基於256元基數樹，它使用20種壓縮方法，極其復雜...burst Trie——如果壹個子樹足夠小，它被存儲在二進制堆中。
但總的來說，HAT Trie-的壓縮效果壓縮率高，不易出現CPU緩存缺失，查找速度接近哈希表，占用內存少得多。節點可以是以下三種類型之壹:數組Hash、序列化桶、傳統Trie node Marisa Trie——壓縮率最高，支持mmap加載，也是壹個復雜的實現，有很多壓縮技術，就是構建時間長，不能動態更新。