替罪羊树 —— 暴力也是种优雅

佚名 5年前 (2019-09-15) 算法 1304人围观抢沙发百度已收录

作为一棵二叉搜索树，那么最重要的就是如何保持自己的平衡，为了保持平衡，二叉搜索树们八仙过海各显神通，如AVL树、红黑树、Treap树、伸展树等等，但万变不离其宗，他们的方法都是基于旋转，然后更改节点间的关系。

尤其是一些二叉搜索树实现起来非常非常繁琐，像红黑树，增加和删除节点总共大约需要处理十来种情况，写完debug完估计天都已经黑了几次了。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

而替罪羊树就是一棵与众不同的树，当遇见不平衡的情况时，不会想法子调整平衡，直接对她进行暴力重建。

重建

上面的这棵子树，很明显是不平衡的，虽然暂时不知道基于什么条件来判断是否平衡。我们直接将这棵子树拍扁，从小到大进行排列（中序遍历）。

将中间的元素当做新的根节点，两边的元素分别作为孩子。这样对她的重建就完成了，这种感觉就好像是从中间拎起来，两边耷拉下去一样。重建后的二叉树基本为满二叉树，效率极高。

那么替罪羊树又是如何判断一棵树是否需要平衡呢。也非常简单，每棵树都会取一个平衡因子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，转载请注明出处