二叉查找树 （BST）
二叉查找树：中序遍历是一个递增的序列。父节点的左子树的所有结点都比父节点小，父节点右子树的结点比父节点都大。
在一颗随机构造的BST上，查找一个元素的时间复杂度位O(logn) ,但是如果我们有序的插入结点，那么BST的高度将位N，时间复杂度位O(n) 。
import java.util.Scanner;
public class Main {
static class Node {
Node l;
Node r;
int value;
}
static Node insert(Node node, int value) {
if (node == null) {
node = new Node();
node.value = value;
return node;
}
if (node.value > value) {
node.l = insert(node.l, value);
} else {
node.r = insert(node.r, value);
}
return node;
}
static void dfs(Node node) {
if (node.l != null) {
dfs(node.l);
}
System.out.print(node.value + " ");
if (node.r != null) {
dfs(node.r);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Node root = new Node();
root.value = sc.nextInt();
for (int i = 1; i < n; i++) {
int value = sc.nextInt();
insert(root, value);
}
dfs(root);
}
}
堆
堆的性质：堆顶元素为所有元素中最小（或者最大）。父结点 的左节点和右节点都比父节点大。
一维数组即可实现，父节点索引为 x ，左儿子索引为x 乘 2 ,右儿子索引 x 乘 2+1
核心操作：
down ： 如果自己比两个儿子结点大，那么跟其中最小的进行换位。递归操作
up：同down差不多
删除堆顶元素 ： 直接将最后一个元素提到堆顶，然后进行down操作
插入元素：插入最后一个位置，然后up操作
import java.util.Scanner;
public class Main {
static int h[] = new int[200010];
static int n;
static void down(int index) {
int a = h[index * 2];
int b = h[index * 2 + 1];
if (index * 2 > n) {
a = 1000000000;
}
if (index * 2 + 1 > n) {
b = 1000000000;
}
if (a < b && a < h[index]) {
int tmp = h[index];
h[index] = a;
h[index * 2] = tmp;
down(index * 2);
}
if (b <= a && b < h[index]) {
int tmp = h[index];
h[index] = b;
h[index * 2 + 1] = tmp;
down(index * 2 + 1);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
int m = sc.nextInt();
for (int i = 1; i <= n; i++) {
h[i] = sc.nextInt();
}
for (int i = n / 2; i != 0; i--) {
down(i);
}
for (int i = 1; i <= n; i++) {
// System.out.println(h[i]);
}
while (m-- != 0) {
System.out.print(h[1] + " ");
h[1] = h[n--];
down(1);
}
}
}
Treap
Treap 就是 Tree + Heap
我们知道，一个BST可能面临退化为链表的问题。那么我们在属性Key（代表当前存储的值）之外，可以给结点加一个属性为Value 。在插入时，我们用随机函数给Value属性随机生成一个值。然后我们先把结点按照BST的性质（中序遍历输出属性K为递增）插入到对应的位置。但是到对应位置之后，当前的这颗树可能不符合堆的结构，我们递归的调用左旋，右旋去维护堆的性质。
那左旋和右旋是什么呢？就是保证不打乱树的中序遍历的情况下，交换两个结点。
```java
import java.util.Random;
import java.util.Scanner;
/**
* Main
*/
public class Main {
static int N = 100010;
static int INF = 100000000;
static int idx = 0;
static Random random = new Random();
static class Node {
Node l, r;
int key, value;
int cnt, size;
Node(int key) {
this.key = key;
this.value = random.nextInt();
this.cnt = this.size = 1;
}
};
static Node root = null;
static void pushup(Node node) {
node.size = node.cnt;
if (node.l != null) {
node.size += node.l.size;
}
if (node.r != null) {
node.size += node.r.size;
}
}
static void build() {
Node node1 = new Node(INF);
Node node2 = new Node(-INF);
node1.l = node2;
root = node1;
if (node1.value < node2.value)
root = zig(root);
pushup(root);
}
static Node zig(Node node) {
Node lt = node.l;
node.l = lt.r;
lt.r = node;
node = lt;
pushup(node.r);
pushup(node);
return lt;
}
static Node zag(Node node) {
Node rt = node.r;
node.r = rt.l;
rt.l = node;
node = rt;
pushup(node.l);
pushup(node);
return rt;
}
static Node insert(Node node, int key) {
if (node == null) {
return new Node(key);
} else if (node.key == key) {
node.cnt++;
} else if (node.key > key) {
node.l = insert(node.l, key);
if (node.l.value > node.value) {
node = zig(node);
}
} else {
node.r = insert(node.r, key);
if (node.r.value > node.value) {
node = zag(node);
}
}
pushup(node);
return node;
}
static Node remove(Node node, int key) {
if (node == null) {
return null;
}
if (node.key == key) {
if (node.cnt > 1) {
node.cnt--;
pushup(node);
return node;
} else {
if (node.l == null && node.r == null)
return null;
if (node.l == null) {
node = zag(node);
node.l = remove(node.l, key);
} else if (node.r == null) {
node = zig(node);
node.r = remove(node.r, key);
} else if (node.l.value < node.r.value) {
node = zag(node);
node.l = remove(node.l, key);
} else {
node = zig(node);
node.r = remove(node.r, key);
}
}
} else {
if (node.key > key) {
node.l = remove(node.l, key);
} else {
node.r = remove(node.r, key);
}
}
pushup(node);
return node;
}
static int get_rank_by_key(Node node, int key) {
if (node == null) {
return 1;
}
int lsize = node.l == null ? 0 : node.l.size;
if (key == node.key) {
return lsize + 1;
} else if (node.key > key) {
return get_rank_by_key(node.l, key);
} else {
return lsize + node.cnt + get_rank_by_key(node.r, key);
}
}
static int get_key_by_rank(Node node, int rank) {
int lsize = node.l == null ? 0 : node.l.size;
if (lsize < rank && lsize + node.cnt >= rank) {
return node.key;
} else if (lsize >= rank) {
return get_key_by_rank(node.l, rank);
} else {
return get_key_by_rank(node.r, rank - node.cnt - lsize);
}
}
static int get_prev(Node node, int key) {
if (node == null)
return -INF;
if (node.key >= key) {
return get_prev(node.l, key);
}
return Math.max(node.key, get_prev(node.r, key));
}
static int get_next(Node node, int key) {
if (node == null) {
return INF;
}
if (node.key <= key) {
return get_next(node.r, key);
}
return Math.min(node.key, get_next(node.l, key));
}
public static void main(String[] args) {
build();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
while (n-- != 0) {
int opt, x;
opt = sc.nextInt();
x = sc.nextInt();
if (opt == 1) {
root = insert(root, x);
} else if (opt == 2) {
root = remove(root, x);
} else if (opt == 3) {
System.out.println(get_rank_by_key(root, x) - 1);
} else if (opt == 4) {
System.out.println(get_key_by_rank(root, x + 1));
} else if (opt == 5) {
System.out.println(get_prev(root, x));
} else {
System.out.println(get_next(root, x));
}
}
}
}
Splay
Splay 是为了解决BST退化的另一个方案。
基于程序局部性原理的假设，在一个结点被访问后，我们将把他放到树根的位置。
在把这个结点推向树根的过程中，我们对于不同的情况，选的不同的左旋和右旋方案，在完成操作的同时，减少树的层数，解决BST退化的问题。
标签：node,Node,int,value,二叉,Treap,static,key,Spaly From： https://www.cnblogs.com/x1uc/p/18076113