# 平衡二叉树（AVL）

1)new.value = old.value

2)new.left = old.left

3)new.right = old.right.left

4)old.value = old.right.value

5)old.right = old.right.right

6)old.left = new

1)new.value = old.value

2)new.left = old.left.right

3)new.right = old.right

4)old.value = old.left.value

5)old.left= old.left.left

6)old.right = new

```public class AVLTreeDemo {

public static void main(String[] args) {
int[] arr = {4, 3, 6, 5, 7, 8};
int[] arr2 = {10, 12, 8, 9, 7, 6};
int[] arr3 = {10, 11, 7, 6, 8, 9};
AVLTree avlTree = new AVLTree();
for (int i = 0; i < arr3.length; i++) {
}
avlTree.infixOrder();
System.out.println(avlTree.getRoot().height());
System.out.println(avlTree.getRoot().leftHeight());
System.out.println(avlTree.getRoot().rightHeight());
}
}

class AVLTree {
private Node root;

public Node getRoot() {
return root;
}

public void setRoot(Node root) {
this.root = root;
}

public void add(Node node) {
if (root == null) {
root = node;
} else {
}
}

public void infixOrder() {
if (root != null) {
root.infixOrder();
}
}

public Node search(int value) {
if (root == null) {
return null;
} else {
return root.search(value);
}
}

public Node searchParent(int value) {
if (root == null) {
return null;
} else {
return root.searchParent(value);
}
}

public int delRightTreeMin(Node node) {
Node target = node;
while (target.right != null) {
target = target.right;
}
delete(target.value);
return target.value;
}

public void delete(int value) {
if (root == null) {
return;
} else {
Node targetNode = search(value);
if (targetNode == null) {
return;
}
if (root.left == null && root.right == null) {
root = null;
return;
}

Node parent = searchParent(value);
if (targetNode.left == null && targetNode.right == null) {
if (parent.left != null && parent.left == targetNode) {
parent.left = null;
} else if (parent.right != null && parent.right == targetNode) {
parent.right = null;
}
} else if (targetNode.left != null && targetNode.right != null) {
int minVal = delRightTreeMin(targetNode.left);
targetNode.value = minVal;
} else {
if (targetNode.left != null) {
if (parent != null) {
if (parent.left.value == value) {
parent.left = targetNode.left;
} else {
parent.right = targetNode.left;
}
} else {
root = targetNode.left;
}
} else {
if (parent != null) {
if (parent.left.value == value) {
parent.left = targetNode.right;
} else {
parent.right = targetNode.right;
}
} else {
root = targetNode.right;
}
}
}
}
}
}

class Node {
int value;
Node left;
Node right;

public Node(int value) {
this.value = value;
}

@Override
public String toString() {
return "Node[" +
"value=" + value +
‘]‘;
}

public void add(Node node) {
if (node == null) {
return;
}
if (node.value < this.value) {
if (this.left == null) {
this.left = node;
} else {
}
} else {
if (this.right == null) {
this.right = node;
} else {
}
}
if (rightHeight() - leftHeight() > 1) {
if (right != null && right.rightHeight() < right.leftHeight()) {
right.rightRotate();
leftRotate();
} else {
leftRotate();
}
return;//!!!!!
}
if (leftHeight() - rightHeight() > 1) {
if (left != null && left.rightHeight() > left.leftHeight()) {
left.leftRotate();
rightRotate();
} else {
rightRotate();
}
}
}

public void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.infixOrder();
}
}

public Node search(int value) {
if (value == this.value) {
return this;
} else if (value < this.value) {
if (this.left == null) {
return null;
}
return this.left.search(value);
} else {
if (this.right == null) {
return null;
}
return this.right.search(value);
}
}

/**
* @param value 要找的值
* @return 要删除节点的父节点 没有返回null
*/
public Node searchParent(int value) {
if ((this.left != null && this.left.value == value) ||
(this.right != null && this.right.value == value)) {
return this;
} else {
if (value < this.value && this.left != null) {
return this.left.searchParent(value);
} else if (value >= this.value && this.left != null) {
return this.right.searchParent(value);
} else {
return null;
}
}
}

public int height() {
return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}

public int leftHeight() {
if (left == null) {
return 0;
}
return left.height();
}

public int rightHeight() {
if (right == null) {
return 0;
}
return right.height();
}

//左旋转
private void leftRotate() {
Node newNode = new Node(value);
newNode.left = left;
newNode.right = right.left;
value = right.value;
right = right.right;
left = newNode;
}

//右旋转
private void rightRotate() {
Node newNode = new Node(value);
newNode.right = right;
newNode.left = left.right;
value = left.value;
left = left.left;
right = newNode;
}
}```

## 算法学习笔记 平衡二叉树 AVL树

AVL树是最先发明的自平衡二叉查找树, 其增删查时间复杂度都是 O(logn), 是一种相当高效的数据结构.当面对需要频繁查找又经常增删这种情景时,AVL树就非常的适用.[ 博客地址:http://blog.csdn.net/thisinnocence ] AVL树定义 AVL树诞生于 1962 年,由 G.M. Adelson-Velsky 和 E.M. Landis 发明.AVL树首先是一种二叉查找树.二叉查找树是这么定义的,为空或具有以下性质: 若它的左子树不空,则左子树上所有的点的值均小

## java数据结构与算法之平衡二叉树(AVL树)的设计与实现

[版权申明]未经博主同意,不允许转载!(请尊重原创,博主保留追究权) http://blog.csdn.net/javazejian/article/details/53892797 出自[zejian的博客] 关联文章: java数据结构与算法之顺序表与链表设计与实现分析 java数据结构与算法之双链表设计与实现 java数据结构与算法之改良顺序表与双链表类似ArrayList和LinkedList(带Iterator迭代器与fast-fail机制) java数据结构与算法之栈(Stack)设