//与Binary_search_tree一样的建立过程，但是由于AVL树的特殊性，需要左旋和右旋的操作，代码如下
class AVLTree<Key extends Comparable<? super Key>, Value> {
private class Node {
Key key;
Value value;
int height;
Node left;
Node right;
public Node(Key key, Value value) {
this.key = key;
this.value = value;
this.left = null;
this.right = null;
int height = 1;
}
}
public Node root;
public int size;
public int rHeight;
public int lHeight;
public int leaf;
public AVLTree() {
this.leaf = 0;
this.root = null;
this.size = 0;
this.rHeight = 0;
this.lHeight = 0;
}
private void replaceNode(Node src, Node tar) {
tar.key = src.key;
tar.value = src.value;
}
private int height(Node node) {
if (node != null) {
return node.height;
}
return 0;
}
public int height() {
return height(root);
}
private int max(int a, int b) {
return a > b ? a : b;
}
private void preOrder(Node node) {
if (node != null) {
System.out.print(node.key+" ");
preOrder(node.left);
preOrder(node.right);
}
}
public void preOrder() {
preOrder(root);
}
private void inOrder(Node node) {
if (node != null) {
inOrder(node.left);
System.out.print(node.key+" ");
inOrder(node.right);
}
}
public void inOrder() {
inOrder(root);
}
public void postOrder(Node node) {
if (node != null) {
postOrder(node.left);
postOrder(node.right);
System.out.print(node.key+" ");
}
}
public void postOrder() {
postOrder(root);
}
private Node search(Node node, Key key) {
if (node == null) {
return null;
} else if (key.compareTo(node.key) == 0) {
return node;
} else if (key.compareTo(node.key) < 0) {
return search(node.left, key);
} else {//key.compareTo(node.key) > 0
return search(node.right, key);
}
}
public Node search(Key key) {
return search(root, key);
}
private Node minNode(Node node) {
if (node == null) {
return null;
} else if (node.left == null) {
return node;
} else {
return minNode(node.left);
}
}
public Node minNode() {
return minNode(root);
}
private Node maxNode(Node node) {
if (node == null) {
return null;
} else if (node.right == null) {
return node;
} else {
return maxNode(node.right);
}
}
public Node maxNode() {
return maxNode(root);
}
private Node leftLeftRotation(Node k1) {
Node k2 = k1.left;
k1.left = k2.right;
k2.right = k1;
k1.height = max(height(k1.left), height(k1.right)) + 1;
k2.height = max(height(k2.left), k1.height) + 1;
return k2;
}
public Node rightRightRotation(Node k1) {
Node k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = max(height(k1.left), height(k1.right)) + 1;
k2.height = max(k1.height, height(k2.right)) + 1;
return k2;
}
public Node leftRightRotation(Node k1) {
k1.left = rightRightRotation(k1.left);
return leftLeftRotation(k1);
}
public Node rightLeftRotation(Node k1) {
k1.right = leftLeftRotation(k1.right);
return rightRightRotation(k1);
}
private Node insert(Node node, Key key, Value value) {
if (node == null) return new Node(key, value);
if (key.compareTo(node.key) == 0) {
node.value = value;
} else if (key.compareTo(node.key) < 0) {
node.left = insert(node.left, key, value);
if (height(node.left) - height(node.right) == 2) {
if (key.compareTo(node.left.key) < 0) {
node = leftLeftRotation(node);
} else {
node = leftRightRotation(node);
}
}
} else {
node.right = insert(node.right, key, value);
if (height(node.right) - height(node.left) == 2) {
if (key.compareTo(node.right.key) > 0) {
node = rightRightRotation(node);
} else {
node = rightLeftRotation(node);
}
}
}
node.height = max(height(node.left), height(node.right)) + 1;
return node;
}
public void insert(Key key, Value value) {
this.root = insert(this.root, key, value);
this.size++;
}
public Node remove(Node node, Node target) {
if (node == null || target == null) return node;
if (target.key.compareTo(node.key) < 0) {
node.left = remove(node.left, target);
if (height(node.right) - height(node.left) == 2) {
if (height(node.right.left) <= height(node.right.right)) {
node = rightRightRotation(node);
} else {
node = rightLeftRotation(node);
}
}
} else if (node.key.compareTo(target.key) < 0) {
node.right = remove(node.right, target);
if (height(node.left) - height(node.right) == 2) {
if (height(node.left.right) <= height(node.left.left)) {
node = leftLeftRotation(node);
} else {
node = rightRightRotation(node);
}
}
} else {
if (node.left == null) {
return node.right;
} else if (node.right == null) {
return node.left;
} else {
if (height(node.left) > height(node.right)) {
Node predecessor = maxNode(node.left);
replaceNode(predecessor, node);
node.left = remove(node.left, predecessor);
} else {
Node successor = minNode(node.right);
replaceNode(successor, node);
node.right = remove(node.right, successor);
}
}
}
return node;
}
public void remove(Key key) {
Node z;
if ((z = search(root, key)) != null)
root = remove(root, z);
}
public int getSize(){
return this.size;
}
public int getLeaf(Node root){
if(root.left!=null&&root.right!=null){
getLeaf(root.left);
getLeaf(root.right);
}
else if(root.left!=null&&root.right==null){
getLeaf(root.left);
}
else if(root.right!=null&&root.left==null){
getLeaf(root.right);
}
else{
this.leaf++;
}
return this.leaf;
}
public void getHeight(Node root,int height){
if(root.left!=null&&root.right!=null){
getHeight(root.left,this.lHeight++);
getHeight(root.right,this.rHeight++);
}
else if(root.left!=null&&root.right==null){
getHeight(root.left,this.lHeight++);
}
else if(root.right!=null&&root.left==null){
getHeight(root.right,this.rHeight++);
}
}
public int getHeight(){
getHeight(this.root,0);
return max(this.lHeight,this.rHeight);
}
}
//测试类
public class Exp42 {
public static void main(String[] args) {
AVLTree<Integer,Integer> at = new AVLTree<>();
at.insert(3,3);
at.insert(1,1);
at.insert(4,4);
at.insert(6,6);
at.insert(9,9);
at.insert(7,7);
at.insert(5,5);
at.insert(2,2);
System.out.println(at.getLeaf(at.root));
at.preOrder();
System.out.println();
at.inOrder();
System.out.println();
at.postOrder();
System.out.println();
System.out.println(at.getHeight());
System.out.println(at.getSize());
}
}
