# 手写 avl tree

##### 为什么需要 avl tree

avl tree 又称 平衡二叉树。主要在排序二叉树的基础上进行的一个优化。避免排序二叉树不平衡，从而严重影响查询效率

##### avl tree 实现
/**
* @author shengjk1
* @date 2020/6/23
*/
public class AvlTreeDemo {
public static void main(String[] args) {
int[] arr = {10, 11, 7, 6, 8, 9};
//		int[] arr = {4, 3, 6, 5, 7, 8};
//		int[] arr = {10, 12, 8, 9, 7, 6};
AVLTree avlTree = new AVLTree();
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
System.out.println("中序遍历");
avlTree.infixOrder();

System.out.println("在平衡处理~");
System.out.println("树的高度=" + avlTree.getRoot().height());
System.out.println("树的左子树的高度=" + avlTree.getRoot().leftHight());
System.out.println("树的右子树的高度=" + avlTree.getRoot().rightHeight());
System.out.println("当前的根节点=" + avlTree.getRoot());

}
}

class AVLTree {
private Node root;

public Node getRoot() {
return root;
}

if (root == null) {
root = node;
} else {
}
}

public void infixOrder() {
if (root != null) {
root.infixOrder();
} else {
System.out.println("avl tree is empty");
}
}
}

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

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

//返回左子树的高度
public int leftHight() {
if (left == null) {
return 0;
}
return left.height();
}

//返回右子树的高度
public int rightHeight() {
if (right == null) {
return 0;
}
return right.height();
}

//返回以该节点为根节点的树的高度
public int height() {
return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}

//左旋转
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;
}

//查找要删除的节点
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);
}
}

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

//添加节点
//满足二叉排序树
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() - leftHight() > 1) {
//如果它的右子树的左子树的高度大于它的右子树的右子树的高度
if (right.leftHight() > right.rightHeight()) {
//先对右子节点进行右旋转
right.rightRotate();
//然后对当前节点进行左旋转
leftRotate();
} else {
//直接进行左旋转
leftRotate();
}
//			return;
} else if (leftHight() - rightHeight() > 1) {
if (left.rightHeight() > left.leftHight()) {
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();
}
}
}

0 条评论

• ### 排序二叉树-删除节点

我们已经了解了什么是排序二叉树以及排序二叉树的遍历和添加元素，现在我们一起来看一下，排序二叉树是如何删除元素的。

• ### 工作中用到的sh脚本(持续更新)

day=(date−d‘−0day′‘+echo“(date−d‘−0day′‘+echo“(date -d ‘-0 day’ ‘+%Y-%m-%d’) e...

• ### 排序算法-快速排序

排序算法-快速排序 <?php /** * 快速排序. * * @param array \$value 待排序数组 * @param array \$...

• ### shell 脚本编程

从程序员的角度来看， Shell本身是一种用C语言编写的程序，从用户的角度来看，Shell是用户与Linux操作系统沟通的桥梁。用户既可以输入命令执行，又可...

• ### 学界 | 神经网络的气宗与剑宗之争：先验强大的网络甚至不需要训练

AI 科技评论按：深度神经网络中有许多连接权重，这些权重的值对网络表现有巨大影响；通过反向传播可以定向优化这些权重，提高网络的表现，这个过程被称作「训练」；训练...

• ### 详解HttpURLConnection

http://blog.csdn.net/woxueliuyun/article/details/43267365