1. 概念
平衡二叉树是一种特殊的二叉排序树，其左右子树都是平衡二叉树。所谓平衡，即节点的左右子树高度差不超过1。
平衡因子=左子树高度-右子树高度
对于平衡二叉树，树中所有节点的平衡因子的取值只能是-1、0、1三个值
2. 节点失衡原因及平衡调整问题
- 左旋
/**
* 40 node 50
* \ 左旋 / \
* 50 child -》 40 60
* / \ \
* 45 60 45
*
* 以node为根节点，进行左旋转操作(节点失衡由于右孩子的右子树太高引起)
* 左旋以后，返回树的新的根节点
* @param node
* @return
*/
public Entry<T> leftRotate(Entry<T> node) {
//左旋
Entry<T> child = node.right;
node.right = child.left;
child.left = node;
//更新节点高度值
node.high = Math.max(height(node.left), height(node.right)) + 1;//先更新孩子
child.high = Math.max(height(child.left), height(child.right)) + 1;//再更新双亲
return child;
}
- 右旋
/**
* 40 node 30
* / 右旋 / \
* 30 child -》 20 40
* / \ /
* 20 35 35
* 以node为根节点，进行右旋转操作(节点失衡由于左孩子的左子树太高引起)
* 右旋以后，返回树的新的根节点
* @param node
* @return
*/
public Entry<T> rightRotate(Entry<T> node) {
//右旋
Entry<T> child = node.left;
node.left = child.right;
child.right = node;
//更新节点高度值
node.high = Math.max(height(node.left), height(node.right)) + 1;
child.high = Math.max(height(child.left), height(child.right)) + 1;
return child;
}
- 左平衡
/**
* 40 40 node
* / 左旋 / 右旋 30
* 20 node -》 30 child -》 / \
* \ / 20 40
* 30 child 20
* 以node的左孩子为根节点，进行左-右旋转(左平衡操作)
* 节点失衡由于左孩子的右子树太高引起
* @param node
* @return
*/
public Entry<T> leftBalance(Entry<T> node) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
- 右平衡
/**
* 40 40 node
* \ 右旋 \ 左旋 50
* 60 node -》 50 child -》 / \
* / \ 40 60
* 50 child 60
* 以node的右孩子为根节点，进行右-左旋转(右平衡操作)
* 节点失衡由于右孩子的左子树太高引起
* @param node
* @return
*/
public Entry<T> rightBalance(Entry<T> node) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
3. 算法实现
- 节点类型
/**
* 节点类型
*/
static class Entry<T extends Comparable<T>> {
private T data;
private Entry<T> left;
private Entry<T> right;
private int high;
public Entry(T data) {
this(data, null, null, 1);
}
public Entry(T data, Entry<T> left, Entry<T> right, int high) {
this.data = data;
this.left = left;
this.right = right;
this.high = high;
}
}
- 插入操作
/**
* 插入
* 递归实现，首先从根节点开始，先进行递归，直到找到节点是null的位置
*/
private Entry<T> insert(Entry<T> root, T val) {
if (root == null) {
return new Entry<>(val);
}
if (root.data.compareTo(val) > 0) {
root.left = insert(root.left, val);
//左子树太高
if (height(root.left) - height(root.right) > 1) {
//左子树的左子树太高,进行右旋
if (height(root.left.left) >= height(root.left.right)) {
root = rightRotate(root);
} else {
//左子树的右子树太高，进行左-右旋转操作(左平衡)
root = leftBalance(root);
}
}
} else if (root.data.compareTo(val) < 0) {
root.right = insert(root.right, val);
//右子树太高
if (height(root.right) - height(root.left) > 1) {
//右子树的右子树太高，进行左旋
if (height(root.right.right) >= height(root.right.left)) {
root = leftRotate(root);
} else {
//右子树的左子树太高，进行右-左旋转(右平衡)
root = rightBalance(root);
}
}
}
//更新插入节点高度值
root.high = Math.max(height(root.left), height(root.right)) + 1;
return root;
}
- 删除
/**
* 从root节点开始，找值为val的节点进行删除，删除完成后，返回新的子树的节点
* @param root
* @param val
* @return
*/
private Entry<T> remove(Entry<T> root, T val) {
if (root == null) {
return null;
}
//当前节点的值比待删节点的值大，则继续在其左子树中寻找
if (root.data.compareTo(val) > 0) {
root.left = remove(root.left, val);
//检测节点是否失衡
//右子树太高
if (height(root.right) - height(root.left) > 1) {
//右子树的右子树太高，进行左旋
if (height(root.right.right) >= height(root.right.left)) {
root = leftRotate(root);
} else {
//右子树的左子树太高，进行右-左旋转(右平衡)
root = rightBalance(root);
}
}
} else if (root.data.compareTo(val) < 0) { //当前节点的值比待删节点的值小，则继续在其右子树中寻找
root.right = remove(root.right, val);
//左子树太高
if (height(root.left) - height(root.right) > 1) {
//左子树的左子树太高,进行右旋
if (height(root.left.left) >= height(root.left.right)) {
root = rightRotate(root);
} else {
//左子树的右子树太高，进行左-右旋转操作(左平衡)
root = leftBalance(root);
}
}
} else {
//已找到待删除节点root，首先考虑有两个孩子的情况
if (root.left != null && root.right != null) {
/**
* 为减少旋转次数，选择左子树高删除前驱，右子树高删除后继
*/
//左子树高于右子树 删前驱
if (height(root.left) > height(root.right)) {
Entry<T> pre = root.left;
while (pre.right != null) {
//使pre指向待删节点的前驱节点
pre = pre.right;
}
//用前驱节点的值覆盖待删除节点的值
root.data = pre.data;
//继续递归寻找待删除节点的前驱节点
root.left = remove(root.left, pre.data);
} else { //右子树高于左子树 删后继
Entry<T> post = root.right;
while (post.left != null) {
//使post指向待删节点的后继节点
post = post.left;
}
//用后继节点的值覆盖待删除节点的值
root.data = post.data;
//继续递归寻找待删除节点的后继节点
root.right = remove(root.right, post.data);
}
} else {
if (root.left != null) {
return root.left;
} else if (root.right != null) {
return root.right;
} else {
return null;
}
}
}
//更新删除节点的高度值
root.high = Math.max(height(root.left), height(root.right)) + 1;
return root;
}
- 查询
private boolean query(Entry<T> root, T val) {
if (root == null) {
return false;
}
if (root.data.compareTo(val) > 0) {
return query(root.left, val);
} else if (root.data.compareTo(val) < 0) {
return query(root.right, val);
} else {
return true;
}
}