我有一個關於Balanced BST的理論問題。完美平衡二叉搜索樹
我想建立Perfect Balanced Tree有2^k - 1節點，從一個普通unbalanced BST。我能想到的最簡單的解決方案是使用排序的Array/Linked list並遞歸地將數組分成子數組，並從中構建Perfect Balanced BST。
然而，在非常大的樹的尺寸的情況下，我將需要在相同的大小來創建Array/List所以這種方法會消耗大量的存儲器。
另一種選擇是使用AVL旋轉函數，逐個元素地插入並根據樹平衡因子 - 左右子樹的三個高度來平衡樹的旋轉。
我的問題是，我對我的假設是否正確？有沒有其他的方式來創建一個完美的BST從不平衡BST？
我還沒有找到需要一個完美平衡搜索樹的很好的情況。如果你的情況真的需要它，我想聽聽它。通常，擁有幾乎均衡的樹會更好更快。
如果你有一個大的搜索樹，扔掉所有現有的結構通常不是好主意。使用旋轉函數是獲得更平衡樹的好方法，同時保留大部分現有結構。但通常你使用合適的數據結構來確保你永遠不會有完全不平衡的樹。所謂的自平衡樹。
例如有一個AVL樹，一個紅黑樹或一個splay-tree，它們使用稍微不同的旋轉變體來保持樹的平衡。
如果你真的有一個完全不平衡的樹，你可能會有一個不同的問題。 - 在你的情況下旋轉它的AVL方式可能是修復它的最好方法。
AVL和類似樹木不是完美平衡，所以我不知道它們在這方面是如何有用。
您可以構建一個雙向鏈表出樹節點，使用代替forward和backward指針left和right指針。對列表進行排序，然後從下向上遞歸構建樹，從左到右使用列表。
構建大小爲1的樹很簡單：將最左邊的節點從列表中刪除。現在
如果你能建立大小N的一棵樹，你也可以建立規模2N+1樹：建築面積N的樹，然後咬掉一個節點，然後建立規模N的另一棵樹。單一節點將成爲較大樹的根，而兩個較小的樹將成爲其左側和右側的子樹。由於列表已排序，樹會自動成爲有效的搜索樹。
對於除2^k-1以外的其他尺寸，這也很容易修改。
更新：因爲你是從搜索樹開始，你可以直接從它O(N)時間和O(log N)空間（也許甚至在O(1)空間一點點巧思）建立一個排序列表，並建立樹自下而上還在O(N)時間和O(log N)（或O(1)）空間。
如果你的內存有限制，那麼你可以使用可以在O（log n）時間的AVL樹上完成的拆分和連接操作，並且我相信恆定的空間。
如果您還能夠維護訂單統計，那麼您可以拆分中位數，使LHS和RHS完美，然後加入。
僞代碼（遞歸版本）將
這可以在O（n）時間和O（log n）的空間來實現，我相信。
如果您有一棵大樹並且想要在不改變現有結構的情況下對樹進行轉換，則某些旋轉函數非常有用。 - 結果是否真的必須完美平衡？問題的背景是什麼？ – michas
是的，它必須完美平衡。這是一個學術項目的一部分。 「一些輪換功能」是什麼意思？據我所知，有四個旋轉函數很容易實現。 – OlejkaKL
不同種類的樹木使用稍微不同的旋轉方式。例如比較AVL和紅黑樹。 – michas