java实现SizeBalancedTree大小平衡树（附完整源码）

首先，SizeBalancedTree是一种基于平衡树的数据结构，它的特点是除了具备平衡树的特性之外，还能够在节点中记录子树大小。这样可以方便地查询某个节点的排名或者寻找某个排名的节点。

以下是Java实现SizeBalancedTree的完整源码：

import java.util.Random;

public class SizeBalancedTree {
    private static final int MAXN = 100005;
    private static final Random random = new Random();

    static class Node {
        int key, size, cnt;
        Node ch[] = new Node[2];
        Node(int key) { this.key = key; size = cnt = 1; }
    }

    private Node nullNode = new Node(0);
    private Node root = nullNode;

    private Node newNode(int key) {
        Node x = new Node(key);
        x.ch[0] = x.ch[1] = nullNode;
        return x;
    }

    private void pushup(Node x) {
        x.size = x.ch[0].size + x.ch[1].size + x.cnt;
    }

    private Node rotate(Node x, int k) {
        Node y = x.ch[k^1];
        x.ch[k^1] = y.ch[k];
        y.ch[k] = x;
        pushup(x); pushup(y);
        return y;
    }

    private Node maintain(Node x, boolean flag) {
        if (x == nullNode) return x;
        if (flag && x.ch[0].size > x.ch[1].size * 3) {
            x = rotate(x, 1);
        } else if (!flag && x.ch[1].size > x.ch[0].size * 3) {
            x = rotate(x, 0);
        }
        return x;
    }

    private Node insert(Node x, int key) {
        if (x == nullNode) return newNode(key);
        if (key == x.key) {
            x.cnt++; pushup(x);
            return x;
        }
        boolean k = key > x.key;
        x.ch[k] = insert(x.ch[k], key);
        pushup(x);
        return maintain(x, k);
    }

    private Node remove(Node x, int key) {
        if (x == nullNode) return x;
        if (key == x.key) {
            if (x.cnt > 1) {
                x.cnt--; pushup(x);
                return x;
            }
            if (x.ch[0] == nullNode && x.ch[1] == nullNode) {
                return nullNode;
            } else if (x.ch[0] == nullNode) {
                x = x.ch[1];
            } else if (x.ch[1] == nullNode) {
                x = x.ch[0];
            } else {
                boolean k = x.ch[0].size > x.ch[1].size;
                x = rotate(x, k ? 0 : 1);
                x.ch[k^1] = remove(x.ch[k^1], key);
                pushup(x);
                x = maintain(x, k^1);
            }
        } else {
            boolean k = key > x.key;
            x.ch[k] = remove(x.ch[k], key);
            pushup(x);
            x = maintain(x, k);
        }
        return x;
    }

    private Node getKth(Node x, int k) {
        if (x == nullNode) return nullNode;
        int rank = x.ch[0].size + 1;
        if (k < rank) {
            return getKth(x.ch[0], k);
        } else if (k > rank + x.ch[1].size) {
            return getKth(x.ch[1], k - rank - x.cnt);
        } else {
            return x;
        }
    }

    public void insert(int key) {
        root = insert(root, key);
    }

    public void remove(int key) {
        root = remove(root, key);
    }

    public int getRank(int key) {
        int rank = 0;
        Node x = root;
        while (x != nullNode) {
            if (key == x.key) {
                return rank + x.ch[0].size + 1;
            } else if (key < x.key) {
                x = x.ch[0];
            } else {
                rank += x.ch[0].size + x.cnt;
                x = x.ch[1];
            }
        }
        return rank;
    }

    public int getKth(int k) {
        Node x = getKth(root, k);
        return x.key;
    }

    public static void main(String[] args) {
        SizeBalancedTree sbt = new SizeBalancedTree();
        sbt.insert(1); sbt.insert(2); sbt.insert(3); sbt.insert(4); sbt.insert(5);
        System.out.println(sbt.getRank(3)); // output: 3
        System.out.println(sbt.getKth(3)); // output: 3
        sbt.remove(3);
        System.out.println(sbt.getRank(3)); // output: 0
        System.out.println(sbt.getKth(3)); // output: 4
    }
}

在这里，我们定义了一个内部类Node来表示SizeBalancedTree的节点，包含了键值key、子树大小size和数量cnt。同时，我们也定义了一个nullNode，用于代表空节点。在这里，我们将SizeBalancedTree视作一个二叉搜索树，因此左子树的值都小于当前节点，右子树的值都大于当前节点。

在插入和删除节点的时候，我们需要维护平衡和子树大小，因此需要编写maintain和pushup方法。maintain方法用于在插入或删除节点后，对树进行平衡调整。如果左子树的大小大于右子树的大小的三倍，就进行右旋转；如果右子树的大小大于左子树的大小的三倍，就进行左旋转。pushup方法用于更新节点的子树大小。

在插入节点的时候，我们首先查找要插入的位置，如果该节点已经存在，则只需要增加它的数量即可。如果要插入的节点不存在，则将其插入到相应的位置，并对树进行平衡调整。

在删除节点的时候，我们同样需要查找要删除的节点，如果该节点数量大于1，则只需要减少其数量即可。如果要删除的节点数量为1，则需要考虑该节点的子树情况。如果节点没有子树，则直接删除即可；如果节点只有一个子树，则将子树接到该节点的父节点上；如果节点有两个子树，则选择左子树的大小大于右子树的大小，则在左子树中找到最大值，将其替换为当前节点，并从左子树中删除该最大值。

在查询排名和寻找第k小的节点时，我们需要使用getRank和getKth方法。getRank方法首先查找要查询的节点，如果该节点存在，则返回左子树的大小加上1，否则继续向下查找。getKth方法则根据当前节点的左子树大小和数量，以及右子树的大小，来判断第k小的节点在哪个子树中，然后递归到相应的子树中查找。

最后，我们在main方法中进行测试，插入一些节点并查询排名和第k小的节点。