替罪羊樹(shù) —— 暴力也是種優(yōu)雅

???作為一棵二叉搜索樹(shù)，那么最重要的就是如何保持自己的平衡，為了保持平衡，二叉搜索樹(shù)們八仙過(guò)海各顯神通
，如AVL樹(shù)、紅黑樹(shù)、Treap樹(shù)、伸展樹(shù)等等，但萬(wàn)變不離其宗，他們的方法都是基于旋轉(zhuǎn)，然后更改節(jié)點(diǎn)間的關(guān)系。

????尤其是一些二叉搜索樹(shù)實(shí)現(xiàn)起來(lái)非常非常繁瑣，像紅黑樹(shù)，增加和刪除節(jié)點(diǎn)總共大約需要處理十來(lái)種情況，寫(xiě)完debug完估計(jì)天都已經(jīng)黑了幾次了。

????而替罪羊樹(shù)就是一棵與眾不同的樹(shù)，當(dāng)遇見(jiàn)不平衡的情況時(shí)，不會(huì)想法子調(diào)整平衡，直接對(duì)她進(jìn)行暴力重建。

重建



????上面的這棵子樹(shù)，很明顯是不平衡的，雖然暫時(shí)不知道基于什么條件來(lái)判斷是否平衡。我們直接將這棵子樹(shù)拍扁，從小到大進(jìn)行排列（中序遍歷）。



????將中間的元素當(dāng)做新的根節(jié)點(diǎn)，兩邊的元素分別作為孩子。這樣對(duì)她的重建就完成了，這種感覺(jué)就好像是從中間拎起來(lái)，兩邊耷拉下去一樣。重建后的二叉樹(shù)
基本為滿二叉樹(shù)，效率極高。



????那么替罪羊樹(shù)又是如何判斷一棵樹(shù)是否需要平衡呢。也非常簡(jiǎn)單，每棵樹(shù)都會(huì)取一個(gè)平衡因子alpha，范圍是0.5到1之間。假如某棵樹(shù)的總節(jié)點(diǎn)數(shù) *
alpha < 某個(gè)孩子樹(shù)的總結(jié)點(diǎn)，那么就是不平衡的。例如最上圖中，以6為根節(jié)點(diǎn)的子樹(shù)一共有7個(gè)節(jié)點(diǎn)，6的左孩子是以5為根節(jié)點(diǎn)的子樹(shù)，一共有5個(gè)節(jié)點(diǎn)，
假設(shè)alpha取 0.7 ， 7 * 0.7 < 5， 因此是不平衡的。


????對(duì)于alpha的取值，如果alpha越小，那么對(duì)平衡的要求更高，重建的次數(shù)會(huì)更多；alpha越大，樹(shù)的平衡程度就會(huì)降低，重建的次數(shù)也隨之減少。一般而言，alpha取
0.7 比較適中。

插入


????插入操作開(kāi)始階段和普通的二叉樹(shù)沒(méi)有區(qū)別，將值插入到合適的葉子節(jié)點(diǎn)上后，開(kāi)始調(diào)整平衡。如果自插入的節(jié)點(diǎn)從下而上調(diào)整，調(diào)整完較深層次的子樹(shù)后再向上回溯，如果較低層次的樹(shù)不滿足平衡，所有的子樹(shù)仍需要進(jìn)行重建，那么有很多重建是無(wú)意義的。因此
重建都應(yīng)該從根節(jié)點(diǎn)開(kāi)始，至上向下地判斷是否需要重建。不需要對(duì)所有節(jié)點(diǎn)進(jìn)行判斷，只需要判斷從根節(jié)點(diǎn)到新插入的葉子節(jié)點(diǎn)的路徑中所經(jīng)過(guò)的節(jié)點(diǎn)即可。

????只要發(fā)生了一次重建那么也不必再向下遞歸了，因此任意插入一個(gè)數(shù)，至多發(fā)生一次重建。

刪除

????刪除有許多種做法：

*
每刪除一個(gè)節(jié)點(diǎn)，都進(jìn)行一次至上而下的判斷是否需要重建。

*
每刪除一個(gè)節(jié)點(diǎn)并不是真正的刪除，只是標(biāo)記一下不參與查找。當(dāng)某個(gè)子樹(shù)中已刪除的節(jié)點(diǎn)的比例大于某個(gè)值時(shí)直接進(jìn)行重建，這個(gè)比例可以直接取
alpha，也可以由我們自由控制。

*
每刪除一個(gè)節(jié)點(diǎn)并不是真正的刪除，只是標(biāo)記一下不參與查找。當(dāng)某一次插入操作導(dǎo)致不再平衡觸發(fā)重建時(shí)，順便將標(biāo)記刪除的節(jié)點(diǎn)挪出去不參與重建。

???第二種方式和第三種方式區(qū)別不大，都是惰刪除，具體使用哪種方式都行。

代碼

???暫時(shí)只實(shí)現(xiàn)了插入操作，刪除操作后續(xù)會(huì)補(bǔ)完整。

樹(shù)節(jié)點(diǎn)結(jié)構(gòu)
public class ScapegoatTreeNode<E> { // 以此節(jié)點(diǎn)為根的子樹(shù)的總節(jié)點(diǎn)個(gè)數(shù) 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(); } }
原文首發(fā)于 www.peihuan.net <https://www.peihuan.net/>，轉(zhuǎn)載請(qǐng)注明出處

• ? 上一篇：通俗易懂設(shè)計(jì)模式解析——享元模式
• ? 下一篇： 做了2個(gè)多月的設(shè)計(jì)和編碼，我梳理了Flutter動(dòng)態(tài)化的方案對(duì)比及最佳實(shí)現(xiàn)