替罪羊樹 —— 暴力也是種優雅
- 2019 年 10 月 3 日
- 筆記
作為一棵二叉搜索樹，那麼最重要的就是如何保持自己的平衡，為了保持平衡，二叉搜索樹們八仙過海各顯神通，如AVL樹、紅黑樹、Treap樹、伸展樹等等，但萬變不離其宗，他們的方法都是基於旋轉，然後更改節點間的關係。
尤其是一些二叉搜索樹實現起來非常非常繁瑣，像紅黑樹，增加和刪除節點總共大約需要處理十來種情況，寫完debug完估計天都已經黑了幾次了。
而替罪羊樹就是一棵與眾不同的樹，當遇見不平衡的情況時，不會想法子調整平衡，直接對她進行暴力重建。
重建
上面的這棵子樹，很明顯是不平衡的，雖然暫時不知道基於什麼條件來判斷是否平衡。我們直接將這棵子樹拍扁，從小到大進行排列（中序遍歷）。
將中間的元素當做新的根節點，兩邊的元素分別作為孩子。這樣對她的重建就完成了，這種感覺就好像是從中間拎起來，兩邊耷拉下去一樣。重建後的二叉樹基本為滿二叉樹，效率極高。
那麼替罪羊樹又是如何判斷一棵樹是否需要平衡呢。也非常簡單，每棵樹都會取一個平衡因子alpha，範圍是0.5到1之間。假如某棵樹的總節點數 * alpha < 某個孩子樹的總結點，那麼就是不平衡的。例如最上圖中，以6為根節點的子樹一共有7個節點，6的左孩子是以5為根節點的子樹，一共有5個節點， 假設alpha取 0.7 ， 7 * 0.7 < 5， 因此是不平衡的。
對於alpha的取值，如果alpha越小，那麼對平衡的要求更高，重建的次數會更多；alpha越大，樹的平衡程度就會降低，重建的次數也隨之減少。一般而言，alpha取 0.7 比較適中。
插入
插入操作開始階段和普通的二叉樹沒有區別，將值插入到合適的葉子節點上後，開始調整平衡。如果自插入的節點從下而上調整，調整完較深層次的子樹後再向上回溯，如果較低層次的樹不滿足平衡，所有的子樹仍需要進行重建，那麼有很多重建是無意義的。因此重建都應該從根節點開始，至上向下地判斷是否需要重建。不需要對所有節點進行判斷，只需要判斷從根節點到新插入的葉子節點的路徑中所經過的節點即可。
只要發生了一次重建那麼也不必再向下遞歸了，因此任意插入一個數，至多發生一次重建。
刪除
刪除有許多種做法：
-
每刪除一個節點，都進行一次至上而下的判斷是否需要重建。
-
每刪除一個節點並不是真正的刪除，只是標記一下不參與查找。當某個子樹中已刪除的節點的比例大於某個值時直接進行重建，這個比例可以直接取 alpha，也可以由我們自由控制。
-
每刪除一個節點並不是真正的刪除，只是標記一下不參與查找。當某一次插入操作導致不再平衡觸發重建時，順便將標記刪除的節點挪出去不參與重建。
第二種方式和第三種方式區別不大，都是惰刪除，具體使用哪種方式都行。
代碼
暫時只實現了插入操作，刪除操作後續會補完整。
樹節點結構
public class ScapegoatTreeNode<E> { // 以此節點為根的子樹的總節點個數 private int size = 1; private E value; private ScapegoatTreeNode<E> leftChild; private ScapegoatTreeNode<E> rightChild; ScapegoatTreeNode(E value) { this.value = value; } public int getSize() { return size; } public void setSize(int size) { this.size = size; } public E getValue() { return value; } public void setValue(E value) { this.value = value; } public ScapegoatTreeNode<E> getLeftChild() { return leftChild; } public void setLeftChild(ScapegoatTreeNode<E> leftChild) { this.leftChild = leftChild; } public ScapegoatTreeNode<E> getRightChild() { return rightChild; } public void setRightChild(ScapegoatTreeNode<E> rightChild) { this.rightChild = rightChild; } }插入操作
public class ScapegoatTree<E extends Comparable<E>> { private ScapegoatTreeNode<E> root; private static final double ALPHA_MAX = 1; private static final double ALPHA_MIN = 0.5; private double alpha = 0.7; private List<ScapegoatTreeNode<E>> insertPath = new ArrayList<>(); public ScapegoatTree() { } public ScapegoatTree(double alpha) { if (alpha < 0.5) { alpha = 0.5; } if (alpha > 1) { alpha = 0.99; } this.alpha = alpha; } public void insert(E value) { ScapegoatTreeNode<E> node = new ScapegoatTreeNode<>(value); if (root == null) { root = new ScapegoatTreeNode<>(value); } else { boolean successfullyInsertion = insertValue(root, node); if (successfullyInsertion) { insertPath.forEach(node->node.size++); tryAdjust(); } clearInsertPath(); } } private boolean insertValue(ScapegoatTreeNode<E> parent, ScapegoatTreeNode<E> node) { if (parent == null || node == null) { return false; } insertPath.add(parent); int com = node.getValue().compareTo(parent.getValue()); if (com < 0) { if (parent.getLeftChild() != null) { return insertValue(parent.getLeftChild(), node); } else { parent.setLeftChild(node); return true; } } else if (com > 0) { if (parent.getRightChild() != null) { return insertValue(parent.getRightChild(), node); } else { parent.setRightChild(node); return true; } } return false; } private void tryAdjust() { for (int i = 0; i < insertPath.size(); i++) { ScapegoatTreeNode<E> node = insertPath.get(i); int leftChildNodeCount = Optional.ofNullable(node.getLeftChild()) .map(left -> left.size) .orElse(0); if (leftChildNodeCount > (int)(node.size * alpha) || leftChildNodeCount < (int)(node.size * (1 - alpha))) { rebuild(node, i == 0 ? null : insertPath.get(i - 1)); return; } } } private void rebuild(ScapegoatTreeNode<E> root, ScapegoatTreeNode<E> parent) { List<E> elements = new ArrayList<>(); inOrderTraversal(root, elements); ScapegoatTreeNode<E> newRoot = reBuildCore(elements,0, elements.size() - 1); if (parent == null) { this.root = newRoot; } else if (parent.getLeftChild() == root) { parent.setLeftChild(newRoot); } else { parent.setRightChild(newRoot); } } private void inOrderTraversal(ScapegoatTreeNode<E> root, List<E> elements) { if (root == null) { return; } inOrderTraversal(root.getLeftChild(), elements); elements.add(root.getValue()); inOrderTraversal(root.getRightChild(), elements); } private ScapegoatTreeNode<E> reBuildCore(List<E> elements, int start, int end) { if (start > end) { return null; } int middle = (int)Math.ceil((start + end) / 2.0); if (middle >= elements.size()) { return null; } ScapegoatTreeNode<E> root = new ScapegoatTreeNode<>(elements.get(middle)); root.size = end - start + 1; root.setLeftChild(reBuildCore(elements, start, middle - 1)); root.setRightChild(reBuildCore(elements, middle + 1, end)); return root; } private void clearInsertPath() { insertPath.clear(); } }原文首發於 www.peihuan.net，轉載請註明出處
