哪位daN帮我看看我的平衡二叉搜索树的添加和删除啊
写的好乱啊 指导一二
package Tree;
public class t2<E> {
AVLNode<E> root;
private class AVLNode<E> {
int key;
E value;
AVLNode<E> left;
AVLNode<E> right;
int height;
public AVLNode(int key) {
this.key = key;
}
public AVLNode(int key, E value) {
this.key = key;
this.value = value;
this.height = 1;
}
}
// 获取节点高度
private int getHeight(AVLNode<E> node) {
return node == null ? 0 : node.height;
}
// 更新节点高度
private void updateHeight(AVLNode<E> node) {
node.height = Integer.max(getHeight(node.left), getHeight(node.right)) + 1;
}
private AVLNode<E> rightRotate(AVLNode<E> node) {
AVLNode<E> leftChile = node.left;
node.left = leftChile.right;
leftChile.right = node;
updateHeight(leftChile.right); // (leftChile.right也就是node节点)此时node作为子节点,需要先更新子节点的高度
updateHeight(leftChile);
return leftChile;
}
private AVLNode<E> leftRightRotate(AVLNode<E> node) {
// 首先对左子树进行左旋,转换为左左的情况
node.left = leftRotate(node.left);
// 然后对进行右旋
return rightRotate(node);
}
private AVLNode<E> leftRotate(AVLNode<E> node) {
AVLNode<E> rightChile = node.right; // node为6 rightChile 为 8
node.right = rightChile.left; // 将7给6的右子节点
rightChile.left = node; // 8 的左子节点为6
updateHeight(node);
updateHeight(rightChile);
return rightChile;
}
private AVLNode<E> rightLeftRotate(AVLNode<E> node) {
node.right = rightRotate(node.right);
// 然后本节点左旋
return leftRotate(node);
}
private int balanceFactor(AVLNode<E> node) {
return getHeight(node.left) - getHeight(node.right);
}
private AVLNode<E> balance(AVLNode<E> node) {
if (node == null) return null;
// 计算处高度差
int bf = balanceFactor(node);
if (bf < -1) { // 右边过高
int bfChile = balanceFactor(node.right);
if (bfChile > 0) { // 子节点,左边高,右左 ,先右旋,再左旋
return rightLeftRotate(node);
} else { // 右边高,右右(包含两边相等的情况),左旋
return leftRotate(node);
}
} else if (bf > 1) { // 左边更高
int bfChile = balanceFactor(node.left);
if (bfChile > 0) { // 左边高,左左
return rightRotate(node);
} else { // 右边高,左右,先左旋,再右旋
return leftRightRotate(node);
}
} else { // 不需要旋转
return node;
}
}
public void put(int key, E value) {
if (root == null) {
root = new AVLNode<>(key, value);
return;
}
AVLNode<E> p = root;
AVLNode<E> addNode = null;
AVLNode<E> parent = root;
while (p != null){
if(key > p.key){
parent = addNode;
addNode = p;
p = p.right;
}else if (key<p.key){
parent = addNode;
addNode = p;
p = p.left;
}else { // 有重复元素更改元素的值
p.value = value;
return;
}
}
AVLNode node = new AVLNode<>(key,value);
if (node.key > addNode.key) addNode.right=node;
else if (node.key < addNode.key) addNode.left=node;
updateHeight(addNode);
AVLNode<E> balance = balance(parent);
if (parent != null){
if (parent == root){
root = balance;
updateHeight(root);
}else {
AVLNode<E> parentParent = findParent(parent.key);
if (parentParent.key>balance.key)parentParent.left=balance;
else parentParent.right=balance;
}
}
}
public E remove(int key) {
AVLNode<E> remParent = null;
AVLNode<E> p = root;
while (p != null && p.key != key){
if (key < p.key){
remParent = p;
p = p.left;
}else{
remParent = p;
p =p.right;
}
}
if (p == null) return null;
// 执行删除节点
if (p .left==null){
shift(remParent,p,p.right);
}else if (p.right==null){
shift(remParent,p,p.left);
}else {// 如果左右节点都有,寻找后继节点
AVLNode<E> successor = getSuccessor(p);
// 如果后继节点和当前节点相邻,替换即可
if (successor == p.right){
p.key = successor.key;
p.value = successor.value;
p.right=successor.right;
}else {
// 如果不相邻寻找父节点
AVLNode<E> successorParent = findParent(successor.key);
p.key = successor.key;
p.value = successor.value;
successorParent.left = successor.right;
}
}
if (remParent == null) remParent=root;
if (remParent==null)return null;
// 删除后更新父节点
updateHeight(remParent);
if (remParent == root){
root = balance(remParent);
}else{
AVLNode<E> parentParent = findParent(remParent.key);
AVLNode<E> balance = balance(remParent);
if (parentParent.key>balance.key)parentParent.left = balance;
else parentParent.right = balance;
updateHeight(parentParent);
}
return root.value;
}
public AVLNode<E> findParent(int key){
AVLNode<E> parent = null;
AVLNode<E> p = root;
while (p.key != key){
parent = p;
if (key > p.key){
p = p.right;
}
else {
p = p.left;
}
}
return parent;
}
private AVLNode<E> getSuccessor(AVLNode<E> node){
AVLNode<E> successor = node.right;
while (successor.left != null){
successor = successor.left;
}
return successor;
}
private void shift(AVLNode<E> parent,AVLNode<E> deleted,AVLNode<E> child){
if (parent == null){
root = child;
return;
}
if (parent.left == deleted) parent.left = child;
else parent.right=child;
}
}
