某天albus YY出來了一個沒有旋轉操作的平衡樹，由於albus的真名(华中科技大学附属中学 金正中)聽起來很像朝鮮主席，所以就叫朝鮮樹了！
朝鮮樹是一種不需旋轉的 自平衡二元搜尋樹，利用當深度大於max_deep(通常取sqrt(N))時暴力重建的方式讓平均時間為\(\ord{N*sqrt(N)}\)，是一種很糟糕的平衡樹，但是我們還是要理解他，因為這樣暴力重建的概念會在其他樹上用到。
若題目的要求數據量<=500000時可以使用
所有操作都與本篇其他樹差不多只多了個rebuild函數，它會暴力將整顆樹重建成深度logN的平衡樹
對於重建的部分則使用了拍扁重建法，將樹先拍扁成鍊表後重建，只需要花費\(\ord 1\)的空間複雜度
以下提供模板:
沒有留言:
張貼留言