#1337 : 平衡树·SBT

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

小Ho：小Hi，之前你不是讲过Splay和Treap么，那么还有没有更简单的平衡树呢？

小Hi：但是Splay和Treap不是已经很简单了么？

小Ho：是这样没错啦，但是Splay和Treap和原来的二叉搜索树相比都有很大的改动，我有点记不住。

小Hi：这样啊，那我不妨再给你讲解一个新的平衡树算法好了。和二叉搜索树相比，它只需要修改insert函数，就可以做到高度的平衡。

小Ho：好，我就喜欢这样的！

输入

第1行：1个正整数n，表示操作数量，10≤n≤100,000

第2..n+1行：每行1个字母c和1个整数k：

若c为'I'，表示插入一个数字k到树中，-1,000,000,000≤k≤1,000,000,000

若c为'Q'，表示询问树中第k小数字，保证1≤k≤树的节点数量

输出

若干行：每行1个整数，表示针对询问的回答，保证一定有合法的解

样例输入

5I 3I 2Q 1I 5Q 2

样例输出

23

---恢复内容结束---

动态查询Ktop系列

1.对于固定的Ktop系列，可以使用 优先队列，最小堆，Treap,BST,SBT

2.动态的Ktop Treap,BST,SBT 效率： BST<Treap<SBT

解法一 使用二叉搜索树： 此方法是直接建立起二叉树，对于树不做调整，这会造成树变得很长！

遇到的坑： Java swap不能像C++那样，C++可以传地址，传值，传应用但是Java并不是，Java只能传值，并且传递参数的时候，使用的是深copy,也就是参数的对象和本尊不是同一个对象地址，而仅仅是和它拥有相同数值的不同对象。所以swap不能像C++那样.

1 import java.util.Scanner; 2  3 /** 4  * author: 龚细军 5  * class-aim: 6  */ 7  8 class Node { 9     public Integer key;10     public long size;11     public Node left;12     public Node right;13 14     public Node() {15         size = 0;16         key = null;17         left = right = null;18     }19 }20 21 /*二叉排序树,此题不需要调解平衡*/22 class BSTree {23     private static final int DEFAULT_INITIAL_CAPACITY = 1;24 25     public static int query(Node node, int kMin) {26         Long flag = node.left.size - kMin + 1;27         if (flag == 0) return node.key;28         if (flag < 0) return query(node.right, (int) abs(flag));29         return query(node.left, kMin);30     }31 32     private static long abs(Long flag) {33         return flag > 0 ? flag : -1 * flag;34     }35 36     public static void insert(Node node, int data) {37         if (node.size > 0) {38             node.size++;39             insert(data > node.key ? node.right : node.left, data);40         } else {41             node.key = data;42             node.size = DEFAULT_INITIAL_CAPACITY;43             node.left = new Node();44             node.right = new Node();45         }46     }47 48 }49 50 public class Main {51 52     public static void main(String args[]) {53         int num, val;54         String cmd;55         Scanner scanner = new Scanner(System.in);56         while (scanner.hasNext()) {57             num = scanner.nextInt();58             Node root = new Node();59             while (num-- > 0) {60                 cmd = scanner.next();61                 val = scanner.nextInt();62                 if (cmd.equals("I")) BSTree.insert(root, val);63                 else {64                     System.out.println(BSTree.query(root, val));65                 }66             }67         }68     }69 70 }

解法二： SBT树 平衡树，在解法一基础上进行优化，也就每次对其不满足这样条件的进行调整：

   node.left.size >= max(node.right.right.size,node.right.left.size);

   node.right.size >= max(node.left.right.size , node.left.left.size);

进行平衡调整.这样就可以使其查询数据降到O（lgn）

1 import java.util.Scanner;  2   3 /**  4  * author: 龚细军  5  * class-aim:  6  */  7   8 class Node {  9     public int key, size; 10     public Node left, right; 11  12     public Node() { 13         this.size = 0; 14         this.left = null; 15         this.right = null; 16     } 17  18     public void clone(Node node) { 19         this.key = node.key; 20         this.size = node.size; 21         this.left = node.left; 22         this.right = node.right; 23     } 24 } 25  26 public class Main { 27     private static final int DEFAULT_INITIAL_CAPACITY = 1; 28  29     public static int getSize(Node node) { 30         return node == null ? 0 : node.size; 31     } 32  33     public static int compare(Node a, int key) { 34         return a.key - key; 35     } 36  37     public static void update(Node node) { 38         if (node == null) return; 39         node.size = getSize(node.left) + getSize(node.right) + 1; 40     } 41  42     public static void rightRotate(Node master, Node node) { 43         Node newNode = new Node(); 44         newNode.clone(master); 45         newNode.left = node.right; 46         node.right = newNode; 47         update(newNode); 48         update(node); 49         master.clone(node); 50     } 51  52     public static void leftRotate(Node master, Node node) { 53         Node tmpNode = new Node(); 54         tmpNode.clone(master); 55         tmpNode.right = node.left; 56         node.left = tmpNode; 57         update(tmpNode); 58         update(node); 59         master.clone(node); 60     } 61  62     public static void insert(Node master, int key) { 63  64         if (master.size == 0) { 65             master.left = new Node(); 66             master.right = new Node(); 67             master.size = DEFAULT_INITIAL_CAPACITY; 68             master.key = key; 69         } else if (compare(master, key) > 0) { 70             insert(master.left, key); 71             if (getSize(master.left.left) > getSize(master.right)) { 72                 //右旋转 73                 rightRotate(master, master.left); 74             } 75         } else { 76             insert(master.right, key); 77             if (getSize(master.right.right) > getSize(master.left)) { 78                 //左旋转 79                 leftRotate(master, master.right); 80             } 81         } 82  83         update(master); 84  85     } 86  87     private static int abs(int flag) { 88         return flag > 0 ? flag : -1 * flag; 89     } 90  91     public static int query(Node node, int kMin) { 92  93         int flag = node.left.size - kMin + 1; 94         if (flag == 0) return node.key; 95         if (flag < 0) return query(node.right, abs(flag)); 96         return query(node.left, kMin); 97     } 98  99     public static void main(String args[]) {100         int num, val;101         String cmd;102         Scanner scanner = new Scanner(System.in);103         while (scanner.hasNext()) {104             num = scanner.nextInt();105             Node root = new Node();106             while (num-- > 0) {107                 cmd = scanner.next();108                 val = scanner.nextInt();109                 if (cmd.equals("I"))110                     Main.insert(root, val);111                 else112                     System.out.println(Main.query(root, val));113             }114         }115     }116 }