一、为什么要有平衡二叉树
二叉平衡搜索树一定程度上可以提高搜索效率，但是当原序列有序时.例如序列 A = {6,8,10,11,13,15,17}，构造二叉搜索树如图a 。依据此序列构造的二叉搜索树为右斜树，同时二叉树退化成单链表，搜索效率降低为 O(n)。
在此二叉搜索树中查找元素17, 需要查找 7 次。
二叉搜索树的查找效率取决于树的高度，因此保持树的高度最小，即可保证树的查找效率。同样的序列 A，将其改为图b 的方式存储，查找元素 17 时只需比较 3 次，查找效率提升一倍多。
可以看出当结点数目一定时，保持树的左右两端保持平衡，树的查找效率最高。
这种左右子树的高度相差不超过 1 的树为平衡二叉树。
二、平衡二叉查找树定义
平衡二叉查搜索树：简称平衡二叉树。由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉树，根据科学家的英文名也称为 AVL 树。
它具有如下几个性质：
- 1.可以是空树。
- 2.假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1。
平衡之意，如天平，即两边的分量大约相同。
三、平衡因子
定义：某节点的左子树与右子树的高度(深度)差即为该节点的平衡因子（BF,Balance Factor），平衡二叉树中不存在平衡因子大于 1 的节点。在一棵平衡二叉树中，节点的平衡因子只能取 0 、1 或者 -1 ，分别对应着左右子树等高，左子树比较高，右子树比较高。
四、具体代码
上面给大家解释了平衡二叉树,下面是具体实现的代码
利用java实现二叉平衡搜索树,可以实现添加结点,删除结点,中序遍历等等,具体功能代码里面都有注释
public class AVLTreeDemo {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6};
AVLTree avlTree = new AVLTree();
for (int a : arr) {
avlTree.add(new Node(a));
}
System.out.println("二叉平衡树,中序编列的结果为:");
avlTree.infixOrder();
System.out.println("左子树的高度:" + avlTree.getRoot().leftHeight());
System.out.println("右子树的高度:" + avlTree.getRoot().rightHeight());
System.out.println("二叉树的总高度:" + avlTree.getRoot().height());
System.out.println("根节点的值为:" + avlTree.getRoot());
}
}
//二叉平衡搜索树
class AVLTree {
private Node root;
public AVLTree() {
}
public AVLTree(Node root) {
this.root = root;
}
public Node getRoot() {
return root;
}
//查找待删除结点
public Node sreach(int value) {
if (root == null) {
return null;
} else {
return root.sreach(value);
}
}
//查找待删除结点的父节点
public Node sreachParent(int value) {
if (root == null) {
return null;
} else {
return root.sreachParent(value);
}
}
/**
* 查找以当前结点为根结点的二叉树的最小值，并删除该结点
*
* @param node 需要查找的根节点
* @return 返回以node为根节点的二叉树的最小值
*/
public int delRightTreeMin(Node node) {
Node target = node.right;
while (target.left != null) {
target = target.left;
}
delNode(target.value);
return target.value;
}
/**
* 查找当前结点为根节点的二叉树的最大值，并删除该结点
*
* @param node 需要查找的二叉树的根节点
* @return 返回以node为根节点的二叉树的最大值
*/
public int delLeftTreeMax(Node node) {
Node target = node.left;
while (target.left != null) {
target = target.left;
}
delNode(target.value);
return target.value;
}
public void delNode(int value) {
if (root == null) {
return;
}
Node target = sreach(value);
Node parent = sreachParent(value);
if (target != null && parent != null) {
//判断当前结点是不是叶子结点
if (target.left == null && target.right == null) {
if (parent.left != null && parent.left.value == value) {
parent.left = null;
} else if (parent.right != null && parent.right.value == value) {
parent.right = null;
}
} else if (target.left != null && target.right != null) {
target.value = delRightTreeMin(target);
} else {
if (parent.left != null && parent.left.value == value && target.left != null) {
parent.left = target.left;
} else if (parent.left != null && parent.left.value == value && target.right != null) {
parent.left = target.right;
} else if (parent.right != null && parent.right.value == value && target.right != null) {
parent.right = target.right;
} else if (parent.right != null && parent.right.value == value && target.left != null) {
parent.right = target.left;
}
}
} else if (target != null && parent == null) {
//判断当前结点是不是叶子结点
if (target.left == null && target.right == null) {
target = null;
} else if (target.left != null && target.right != null) {
target.value = delRightTreeMin(target);
} else {
if (target.left != null) {
target = target.left;
} else if (target.right != null) {
target = target.right;
}
}
}
}
public void add(Node node) {
if (root == null) {
root = node;
} else {
root.add(node);
}
}
public void infixOrder() {
if (root == null) {
System.out.println("二叉树为空，中序遍历失败！");
} else {
root.infixOrder(root);
}
}
}
class Node {
int value; //该结点的值
Node left; //该结点的左子树
Node right; //该结点的右子树
public Node(int value) {
this.value = value;
}
//右转
private void rightRotate() {
Node newNode = new Node(value);
newNode.right = right;
newNode.left = left.right;
value = left.value;
left = left.left;
right = newNode;
}
//左转
private void leftRotate() {
Node newNode = new Node(value);
newNode.left = left;
newNode.right = right.left;
value = right.value;
right = right.right;
left = newNode;
}
//判断当前结点左子树的高度
public int leftHeight() {
if (left == null) {
return 0;
} else {
return left.height();
}
}
//判断当前结点右子树的高度
public int rightHeight() {
if (right == null) {
return 0;
} else {
return right.height();
}
}
//判断当前结点的高度
public int height() {
return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}
//查找当前结点
public Node sreach(int value) {
if (this.value == value) {
return this;
} else {
if (this.left != null && value < this.value) {
return this.left.sreach(value);
} else if (this.right != null && this.value < value) {
return this.right.sreach(value);
} else {
return null;
}
}
}
//查找当前结点的父节点
public Node sreachParent(int value) {
if (this.left == null && this.right == null) {
return null;
} else {
if (this.left != null && this.left.value == value) {
return this;
} else if (this.right != null && this.right.value == value) {
return this;
} else if (this.left != null && this.value > value) {
return this.left.sreachParent(value);
} else if (this.right != null && this.value < value) {
return this.right.sreachParent(value);
} else {
return null;
}
}
}
//添加结点
public void add(Node node) {
if (node == null) {
return;
}
if (node.value < this.value) {
if (this.left == null) {
this.left = node;
} else {
this.left.add(node);
}
} else {
if (this.right == null) {
this.right = node;
} else {
this.right.add(node);
}
}
if (leftHeight() - rightHeight() > 1) {
if (left != null && left.rightHeight() > left.leftHeight()) {
left.leftRotate();
rightRotate();
} else {
rightRotate();
}
return;
} else if (rightHeight() - leftHeight() > 1) {
if (right != null && right.leftHeight() > right.rightHeight()) {
right.rightRotate();
leftRotate();
} else {
leftRotate();
}
return;
}
}
//中序遍历二叉树
public void infixOrder(Node root) {
if (root == null) {
return;
}
if (root.left != null) {
root.left.infixOrder(root.left);
}
System.out.println(root);
if (root.right != null) {
root.right.infixOrder(root.right);
}
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
}