一种二叉排序树，其中每个节点的左子树和右子树的高度差至多等于1
基本思想：在构建二叉排序树的过程中，每当插入一个节点时，先检查是否因插入而破坏了平衡性，若是，找出最小不平衡树。在保持二叉排序树特性的前提下，调整最小不平衡树中各节点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。
需要平衡处理的四种情况：
1.对当前节点的左孩子的左子树改变---- 右旋转
2.对当前节点的左孩子的右子树改变-----左右旋转
3.对当前节点的右孩子的左子树改变-----右左旋转
4.对当前节点的右孩子的右子树改变-----左旋转
private static class BalanceBinaryNode {
//关键字
private String key;
//值
private int val;
//高度
private int height;
//左子树
private BalanceBinaryNode left;
//右子树
private BalanceBinaryNode right;
public BalanceBinaryNode(String key, int val) {
this.key = key;
this.val = val;
}
public BalanceBinaryNode(String key, int val, int height) {
this.key = key;
this.val = val;
this.height = height;
}
}
//根节点
public BalanceBinaryNode root;
/**
* 添加
*
* @param val
*/
public void add(String key, int val) {
if (root == null) {
root = new BalanceBinaryNode(key, val, 1);
return;
}
root = add(root, key, val);
}
/**
* 添加
*
* @param val
*/
public BalanceBinaryNode add(BalanceBinaryNode node, String key, int val) {
if (node == null) {
//根节点初始化，高度为1
return new BalanceBinaryNode(key, val, 1);
}
//比根节点小，在左侧
if (node.val > val) {
//找到待插入的左节点，如果没有就新建结点
node.left = add(node.left, key, val);
//判断是否出现不平衡，相差达到2时，为不平衡。由于插入的数据，由于数据插入是一直插入到左子树的，所以必然是左边高
if (height(node.left) - height(node.right) == 2) {
//结点比左孩子小，则在左孩子的左子树，就是进行右旋
if (node.left.val > val) {
node = rightRotate(node);
} else {
//如果插入的是左孩子的右子树，则由平衡因子，左孩子变成了负数，结点是整数，需要先左旋再右旋转
//注意的是，左旋是左旋的该结点的孩子节点，右旋是右旋的该结点
node = leftRightRotate(node);
}
}
//比节点大，在右侧
} else if (node.val < val) {
node.right = add(node.right, key, val);
//插入节点的右侧，则肯定右子树的原因变成不平衡
if (height(node.right) - height(node.left) == 2) {
//比右孩子数值大，在右侧，进行左旋转
if (node.right.val < val) {
node = leftRotate(node);
} else {
//比右孩子数值小，在右孩子的做孩子节点上，右孩子左孩子节点平衡因子为正，右孩子节点为负数，先右旋在左旋
node = rightLeftRotate(node);
}
}
} else {
//碰到相等的数据，就覆盖掉
node.key = key;
}
node.height = updateHeight(node);
return node;
}
public void remove(int val) {
root = remove(root, val);
}
public BalanceBinaryNode remove(BalanceBinaryNode node, int val) {
if (node == null) {
return null;
}
//删除的结点在左侧
if (node.val > val) {
node.left = remove(node.left, val);
//因为删除的是左子树的结点，出现不平衡，只会是右边高左边低
if (height(node.right) - height(node.left) == 2) {
node = leftRotate(node);
}
} else if (node.val < val) {
//因为删除的是结点的右子树上的结点，出现不平衡只会是左高右低
node.right = remove(node.right, val);
if (height(node.left) - height(node.right) == 2) {
node = rightRotate(node);
}
} else {
//处理一个结点为空时，将另一个子节点赋值给父节点的左右节点
if (node.right == null) {
return node.left;
}
if (node.left == null) {
return node.right;
}
//都不是空。找到右子树的最小节点，和该结点替换
BalanceBinaryNode minNode = findMin(node.right);
minNode.right = removeMin(node.right);
minNode.left = node.left;
node = minNode;
if(height(node.left) - height(node.right) == 2){
node = rightRotate(node);
}
}
node.height = updateHeight(node);
return node;
}
public BalanceBinaryNode findMin(BalanceBinaryNode node) {
if (node == null) {
return null;
}
while (node.left != null) {
node = node.left;
}
return node;
}
public BalanceBinaryNode removeMin(BalanceBinaryNode node) {
if (node == null) {
return null;
}
if (node.left == null) {
return node.right;
}
node.left = removeMin(node.left);
if (height(node.right) - height(node.left) == 2) {
node = leftRotate(node);
}
return node;
}
/**
* 右旋操作
*
* @param node
*/
public BalanceBinaryNode rightRotate(BalanceBinaryNode node) {
BalanceBinaryNode x = node.left;
node.left = x.right;
x.right = node;
node.height = updateHeight(node);
x.height = updateHeight(x);
return x;
}
/**
* 左旋
*
* @param node
*/
public BalanceBinaryNode leftRotate(BalanceBinaryNode node) {
BalanceBinaryNode x = node.right;
node.right = x.left;
x.left = node;
node.height = updateHeight(node);
x.height = updateHeight(x);
return x;
}
/**
* 左右旋转
*
* @param node
*/
public BalanceBinaryNode leftRightRotate(BalanceBinaryNode node) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
/**
* 右左旋转
*
* @param node
* @return
*/
public BalanceBinaryNode rightLeftRotate(BalanceBinaryNode node) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
/**
* 修改高度，如果该结点没有左右孩子结点，高度为1
*
* @param node
* @return
*/
private int updateHeight(BalanceBinaryNode node) {
return Math.max(height(node.left), height(node.right)) + 1;
}
/**
* 获取高度，默认为0
*
* @param node
* @return
*/
private int height(BalanceBinaryNode node) {
return node == null ? 0 : node.height;
}
网友评论