AVLTree
这个树很好玩啊，有个博客讲得非常好，要点非常清晰
我觉得最核心的一点就是对树的四种操作。
（图中k的交标代表了在图中的大小顺序，1最小。比如图中有三个节点k1,k2,k3，关系就是k1<k2<k3)
- LL：新插入一个节点后，某一个节点的左子树的左子树深度过大，造成了不平衡
k2 k1
/ \ / \
k1 C ===> A k2
/ \ / \
A B B C
操作的方式是，把k1设置成根节点，所以k2就要变成k1的右子树，但是k1本来可能也有右子树，这个右子树就要过继给k2当它的左子树。
造型变换以后，需要更新各个节点的height，从下往上更新，先更新k2的，再更新k1的，然后返回k1（因为它是现在的根节点）
代码如下：
private Node LL(Node k2) {
Node k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
k1.height = Math.max(height(k1.left), height(k2)) + 1;
return k2;
}
- RR： 新插入一个节点以后，某一个节点的右子树的右子树深度过大，造成了不平衡
k1 k2
/ \ / \
A k2 ===> k1 C
/ \ / \
B C A B
操作的方式是，把k2设置成根节点，所以k1就要变成k2的左子树，但是k2本来可能也有左子树，所以k2的右子树就要过继给k1当它的右子树。
造型变换以后，需要更新各个节点的height，从下往上更新，先更新k1的，再更新k2的，然后返回k2
代码如下：
private Node RR (Node k1){
Node k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
k2.height = Math.max(height(k1), height(k2)) + 1;
return k2;
}
* LR: 新插入一个节点以后，某一个节点的左子树的右子树深度过大，造成了不平衡 图示 ``` k3 k3 k2 / \ / \ / \ k1 D ===> k2 D ===> k1 k3 / \ / \ / \ / \ A k2 k1 C A B C D / \ / \ B C A B ``` 操作的方式是，我们先忽略k3这个节点，只看k1,k2构成的树，这是一棵失衡的RR树，所以先对k1k2进行RR操作，然后捋顺了之后出现中间图的情况：一棵LL树，再对k3进行LL操作 因为RR和LL操作里面自带了height的调整，所以这里就不需要单独操作了 代码如下：
private Node LR(Node k3) {
k3.left = RR(k3.left);
return LL(k3);
}
* RL : 新插入一个节点以后，某一个节点的右子树的左子树深度过大，造成了不平衡 ``` k1 k1 k2 / \ / \ / \ A k3 ===> A k2 ===> k1 k3 / \ / \ / \ / \ k2 D B k3 A B C D / \ / \ B C C D ``` 操作的方式是，我们先忽略k1这个节点，只看k2,k3构成的树，这是一棵失衡的LL树，所以先对k2k3进行LL操作，然后捋顺了之后出现中间图的情况：一棵RR树，再对k1进行RR操作 因为RR和LL操作里面自带了height的调整，所以这里就不需要单独操作了 代码如下：
private Node RL(Node k1) {
k1.right = LL(k1.right);
return RR(k1);
}
有了这四种基础的操作，insert就比较好完成了 思路如下 ``` 如果root == null 创建root点 如果key > root.key(也就是说，需要插入的节点在根节点的右侧) root.right = insert(key, root.right); 因为右侧新加了节点，所以有可能失衡，如果右侧的左右高度差变成了2，就需要调整： 如果key比root.right的值要大，也就是一棵失衡的RR树： RR(root) 否则，就是右子树的左子树出了问题， RL(root) 否则（也就是需要插入的节点在根节点的左子树上） root.left = insert(key, root.left) 因为左侧新加了节点，所以有可能失衡，如果左侧的左右高度差变成了2，就需要调整： 如果key比root.right的值要大，也就是一棵失衡的LR树： LR(root) 否则，就是左子树的左子树出了问题， LL(root) 返回root ``` 代码如下：
public void insert(int key, int value) {
root = insert(key, value, root);
}
private Node insert(int key, int value, Node root) {
if(root == null) {
root = new Node(key, value);
} else if(root.key == key){
root.value = value;
} else if(root.key > key) {
root.left = insert(key, value, root.left);
if(height(root.left) - height(root.right) == 2) {
if(root.key > key) {
root = LL(root);
} else {
root = LR(root);
}
}
} else {
root.right = insert(key, value, root.right);
if(height(root.right) - height(root.left) == 2) {
if(root.key > key) {
root = RL(root);
} else{
root = RR(root);
}
}
}
root.height = Math.max(height(root.left), height(root.right)) + 1;
return root;
}
就是这样了~ Node本身的结构
class Node {
int key;
int value;
int height;
Node left;
Node right;
public Node(int key, int value) {
this.key = key;
this.value = value;
this.height = 0;
}
}
两个辅助函数
public void print() {
if(root == null) {
return;
}
int curLevel = 1;
int nextLevel = 0;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
Node cur = queue.poll();
System.out.println((cur.key + ": " + cur.value) + " ");
curLevel--;
if(cur.left != null) {
queue.offer(cur.left);
nextLevel++;
}
if(cur.right != null) {
queue.offer(cur.right);
nextLevel++;
}
if(curLevel == 0) {
System.out.println();
curLevel = nextLevel;
nextLevel = 0;
}
}
}
public int height(Node root) {
if(root == null) {
return 0;
}
return root.height;
}
//随手search功能
public int search(int key) {
Node res = searchHelper(key, root);
return res == null? -1: res.value;
}
private Node searchHelper(int key, Node root) {
if(root == null) {
return null;
} else if(root.key == key) {
return root;
} else if(root.key < key) {
return searchHelper(key, root.right);
} else {
return searchHelper(key, root.right);
}
}
删除会死，我就不写了 完整代码
public class AVLTree {
class Node {
int key;
int value;
int height;
Node left;
Node right;
public Node(int key, int value) {
this.key = key;
this.value = value;
this.height = 0;
}
}
Node root;
public int height(Node root) {
if(root == null) {
return 0;
}
return root.height;
}
private Node LL(Node k2) {
Node k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
k1.height = Math.max(height(k1.left), height(k2)) + 1;
return k2;
}
private Node RR (Node k1){
Node k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
k2.height = Math.max(height(k1), height(k2)) + 1;
return k2;
}
private Node LR(Node k3) {
k3.left = RR(k3.left);
return LL(k3);
}
private Node RL(Node k1) {
k1.right = LL(k1.right);
return RR(k1);
}
public void insert(int key, int value) {
root = insert(key, value, root);
}
private Node insert(int key, int value, Node root) {
if(root == null) {
root = new Node(key, value);
} else if(root.key == key){
root.value = value;
} else if(root.key > key) {
root.left = insert(key, value, root.left);
if(height(root.left) - height(root.right) == 2) {
if(root.key > key) {
root = LL(root);
} else {
root = LR(root);
}
}
} else {
root.right = insert(key, value, root.right);
if(height(root.right) - height(root.left) == 2) {
if(root.key > key) {
root = RL(root);
} else{
root = RR(root);
}
}
}
root.height = Math.max(height(root.left), height(root.right)) + 1;
return root;
}
public int search(int key) {
Node res = searchHelper(key, root);
return res == null? -1: res.value;
}
private Node searchHelper(int key, Node root) {
if(root == null) {
return null;
} else if(root.key == key) {
return root;
} else if(root.key < key) {
return searchHelper(key, root.right);
} else {
return searchHelper(key, root.right);
}
}
public void print() {
if(root == null) {
return;
}
int curLevel = 1;
int nextLevel = 0;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
Node cur = queue.poll();
System.out.println((cur.key + ": " + cur.value) + " ");
curLevel--;
if(cur.left != null) {
queue.offer(cur.left);
nextLevel++;
}
if(cur.right != null) {
queue.offer(cur.right);
nextLevel++;
}
if(curLevel == 0) {
System.out.println();
curLevel = nextLevel;
nextLevel = 0;
}
}
}
public static void main(String[] args) {
AVLTree map = new AVLTree();
map.insert(1, 2);
map.print();
map.insert(2, 3);
map.print();
map.insert(3, 4);
map.print();
}
}