[ scapegoat tree ] 替罪羊樹

替罪羊樹論文其中一個作者，Ronald Linn Rivest，同時也是RSA加密算法的R
替罪羊樹是一種不需要旋轉的平衡樹，它會要求使用者給定一個\(\alpha\)值，其值介於0.5到1之間，\(\alpha\)越大，插入就越快，查詢就越慢，實驗發現\(\alpha\)介於0.55~0.75是最佳的，但是具體的值要看使用者的要求
其平衡滿足:
1.
    \(\alpha*size(o) \le size(o \to left)\)
    \(\alpha*size(o) \le size(o \to right)\)
2.
    \(deep(o) \le log_{1/\alpha} (size(tree))\)
當插入節點導致條件2.不滿足時，會往上回溯到第一個不滿足的節點，然後重建這顆節點的子樹成為完美平衡的二元樹
刪除可以用一般的BST刪除法，當不滿足條件時往上回溯到最先不滿足的節點，重建子樹，也可以懶惰刪除，先設立一個標記， 要刪除這個節點就把它做記號，當\(\alpha\)*全部的節點數量>實際上存在的節點數量，就重建這顆子樹
本文提供一般刪除的方法

其實替罪羊樹的節點是不需要記錄其size的，因為若需要重建，求得size的時間複雜度與重建的時間複雜度相等，這裡為了支援其它有如rank等操作才將size域附加在節點中

插入刪除的均攤時間複雜度為\(\ord{logN}\)，相較之下朝鮮樹只是他的劣質仿冒品，其複雜度證明請參考此論文

以下為模板:

這裡也提供不需要記錄節點大小(size)的平衡方式，相對的一些需要用到附加size域的函數將不能被使用，但插入刪除的效率不變


如果編譯發現沒有__lg()這個函數的話，請在程式碼開頭附上這份code: