!=
@apu629phy
Sun, Sep 5, 2021 2:21 AM
[資結廢]
先來打個昨天看的醒醒腦，然後先繼續run過一次有個概念。
延伸二元樹:
之前n個節點的二元樹我們用link list來表達，原本只向nullptr的pointer我們另外定義成外部節點，原本存在的就是內部節點，又root到內部節點的路徑稱為內部路徑長I，root到外部節點的路徑稱為外部路徑長E，然後有個定理E=I+2N。
此外我們可以對外部節點進行權重的乘算，如何獲得最小的min weighted external path length可以用Huffman algorithm進行求解，有關於編碼解碼的這部分我覺得還滿有趣的，而且解出來的訊息還是唯一的
掰噗~
@baipu
覺得
Sun, Sep 5, 2021 2:21 AM
不要問, 很恐怖
!=
@apu629phy
Sun, Sep 5, 2021 2:22 AM
Optimal prefix code，哇看起來是Huffman在他碩二或是博一的時候寫的論文...
!=
@apu629phy
Sun, Sep 5, 2021 2:24 AM
AVL Tree:
對於資料更新頻繁的狀況下，我們希望BST不管是Insert/Search/Delete都能保持在複雜度O(log n)的worst case，因此有了AVL Tree的存在
!=
@apu629phy
Sun, Sep 5, 2021 2:25 AM
對於每個節點定義Balace Factor，其操作為左子樹高-右子樹高，而平衡樹的要求則是每個點的BF只有-1,0,1的可能
!=
@apu629phy
Sun, Sep 5, 2021 2:27 AM
先討論四種不平衡的情況，LL LR RL RR，其中L、R代表左子樹、又子樹方向，從靠近新增的點的不平衡點起算
!=
@apu629phy
Sun, Sep 5, 2021 2:28 AM
如果不平衡處位於子樹，那只需要調整子樹即可，不用全調整
!=
@apu629phy
Sun, Sep 5, 2021 2:28 AM
不然調出什麼鬼樹都不知道
!=
@apu629phy
Sun, Sep 5, 2021 2:30 AM
好，沒意外看接下來是B tree和紅黑樹的部分，看看這些樹有什麼樣的操作或是運用
載入新的回覆
先來打個昨天看的醒醒腦，然後先繼續run過一次有個概念。
延伸二元樹:
之前n個節點的二元樹我們用link list來表達，原本只向nullptr的pointer我們另外定義成外部節點，原本存在的就是內部節點，又root到內部節點的路徑稱為內部路徑長I，root到外部節點的路徑稱為外部路徑長E，然後有個定理E=I+2N。
此外我們可以對外部節點進行權重的乘算，如何獲得最小的min weighted external path length可以用Huffman algorithm進行求解，有關於編碼解碼的這部分我覺得還滿有趣的，而且解出來的訊息還是唯一的
對於資料更新頻繁的狀況下，我們希望BST不管是Insert/Search/Delete都能保持在複雜度O(log n)的worst case，因此有了AVL Tree的存在
不然調出什麼鬼樹都不知道