平衡二叉树相关算法

@interface Node : NSObject
@property (nonatomic,strong) Node *left;
@property (nonatomic,strong) Node *right;
@property (nonatomic,assign) NSInteger height; //当前节点的高度
@property (nonatomic,assign) NSInteger value;

+(instancetype)nodeWithValue:(NSInteger)value;
@end

//左左类型调整
+(Node *)SingleRotateLeft:(Node *)node
{
Node *p = node.left;
node.left = p.right;
p.right = node;

node.height = MAX(node.left.height, node.right.height) + 1;
p.height = MAX(p.left.height, p.right.height) + 1;
return p;

}

//右右类型调整
+(Node *)SingleRotateRight:(Node *)node
{
Node *p = node.right;
node.right = p.left;
p.left = node;

node.height = MAX(node.left.height, node.right.height) + 1;
p.height = MAX(p.left.height, p.right.height) + 1;
return p;

}

//左右类型调整
+(Node *)DoubleRotateLR:(Node *)node
{
node.left = [self SingleRotateRight:node.left];
return [self SingleRotateLeft:node];
}

//右左类型调整
+(Node *)DoubleRotateRL:(Node *)node
{
node.right = [self SingleRotateLeft:node.right];
return [self SingleRotateRight:node];
}

//判断两个节点是否平衡
+(BOOL)isBalanced:(Node *)left right:(Node *)right
{
NSInteger lH = left.height;
NSInteger rH = right.height;

return labs(lH-rH) < 2;

}

//平衡二叉树插入节点
+(Node *)insertValue:(NSInteger)value rootNode:(Node *)rootNode
{
if (!rootNode) {
rootNode = [Node nodeWithValue:value];
rootNode.height = 1;
return rootNode;
}
if (value>rootNode.value) {
rootNode.right = [self insertValue:value rootNode:rootNode.right];
if (![self isBalanced:rootNode.left right:rootNode.right]) {
if (value > rootNode.right.value) {
rootNode = [self SingleRotateRight:rootNode];
}
else
{
rootNode = [self DoubleRotateRL:rootNode];
}
}
}
else{
rootNode.left = [self insertValue:value rootNode:rootNode.left];
if (![self isBalanced:rootNode.left right:rootNode.right]) {
if (value < rootNode.left.value) {
rootNode = [self SingleRotateLeft:rootNode];
}
else
{
rootNode = [self DoubleRotateLR:rootNode];
}
}
}
rootNode.height = MAX(rootNode.left.height, rootNode.right.height)+1;
return rootNode;
}

//平衡二叉树插删除节点
// 递归进行删除，返回比较节点
private Node<T> remove(T data, Node<T> node) {
if (node == null) {// 不存在此节店，返回null.不需要调整树高
return null;
}
int compareResult = data.compareTo(node.data);
if (compareResult == 0) {// 存在此节点进入
/**
* 找到节点之后进行节点删除操作 判断node是否有子树，如果没有子树或者只有一个子树则直接进行删除
* 如果有两个子树，则需要判断node的平衡系数balance
* 如果balance为0或者1则把node和node的左子树的最大值进行交换 否则把node和右子树的最小值进行交换
* 交换数据之后删除该节点 删除之后判断delete节点的父节点是否平衡，如果不平衡进行节点旋转
* 旋转之后返回delete节点的父节点进行回溯
* */
if (node.left != null && node.right != null) { // 此节点存在左右子树
// 判断node节点的balance，然后进行数据交换删除节点
int balance = getHeight(node.left) - getHeight(node.right);
Node<T> temp = node;// 保存需要进行删除的node节点
if (balance == -1) {
// 与右子树的最小值进行交换
exChangeRightData(node, node.right);
} else {
// 与左子树的最大值进行交换
exChangeLeftData(node, node.left);
}
// 此时已经交换完成并且把节点删除完成，则需要重新计算该节点的树高
temp.height = Math.max(getHeight(temp.left), getHeight(temp.right)) + 1;
// 注意此处，返回的是temp,也就是保存的需要删除的节点，而不是替换的节点
return temp;
} else {
// 把node的子节点返回调用处等于删除了node节点
// 此处隐含了一个node.left ==null && node.right == null 的条件，这时返回null
return node.left != null ? node.left : node.right;
}
} else if (compareResult > 0) {// 没找到需要删除的节点继续递归进行寻找
node.right = remove(data, node.right);
// 删除之后进行树高更新
node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
// 如果不平衡则进行右旋调整。
if (getHeight(node.left) - getHeight(node.right) == 2) {// 进行旋转
Node<T> leftSon = node.left;
// 判断是否需要进行两次右旋还是一次右旋
// 判断条件就是比较leftSon节点的左右子节点树高
if (leftSon.left.height > leftSon.right.height) {
// 右旋一次
node = rotateSingleRight(node);
} else {
// 两次旋转，先左旋，后右旋
node = rotateDoubleRight(node);
}
}
return node;
} else if (compareResult < 0) {// 没找到需要删除的节点继续递归进行寻找
node.left = remove(data, node.left);
// 删除之后进行树高更新
node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
// 如果不平衡进行左旋操作
if (getHeight(node.left) - getHeight(node.right) == 2) {// 进行旋转
Node<T> rightSon = node.right;
// 判断是否需要进行两次右旋还是一次右旋
// 判断条件就是比较rightSon节点的左右子节点树高
if (rightSon.right.height > rightSon.left.height) {
node = rotateSingleLeft(node);
} else {
// 先右旋再左旋
node = rotateDoubleLeft(node);
}
}
return node;
}
return null;
}

// 递归寻找right节点的最大值
private Node<T> exChangeLeftData(Node<T> node, Node<T> right) {
    if (right.right != null) {
        right.right = exChangeLeftData(node, right.right);
    } else {
        // 数据进行替换
        node.data = right.data;
        // 此处已经把替换节点删除
        return right.left;
    }
    right.height = Math.max(getHeight(right.left), getHeight(right.right)) + 1;
    // 回溯判断left是否平衡,如果不平衡则进行左旋操作。
    int isbanlance = getHeight(right.left) - getHeight(right.right);
    if (isbanlance == 2) {// 进行旋转
        Node<T> leftSon = node.left;
        // 判断是否需要进行两次右旋还是一次右旋
        // 判断条件就是比较leftSon节点的左右子节点树高
        if (leftSon.left.height > leftSon.right.height) {
            // 右旋一次
            return node = rotateSingleRight(node);
        } else {
            // 两次旋转，先左旋，后右旋
            return node = rotateDoubleRight(node);
        }
    }
    return right;
}

// 递归寻找left节点的最小值
private Node<T> exChangeRightData(Node<T> node, Node<T> left) {
    if (left.left != null) {
        left.left = exChangeRightData(node, left.left);
    } else {
        node.data = left.data;
        // 此处已经把替换节点删除
        return left.right;
    }
    left.height = Math.max(getHeight(left.left), getHeight(left.right)) + 1;
    // 回溯判断left是否平衡,如果不平衡则进行左旋操作。
    int isbanlance = getHeight(left.left) - getHeight(left.right);
    if (isbanlance == -2) {// 进行旋转
        Node<T> rightSon = node.right;
        // 判断是否需要进行两次右旋还是一次右旋
        // 判断条件就是比较rightSon节点的左右子节点树高
        if (rightSon.right.height > rightSon.left.height) {
            return node = rotateSingleLeft(node);
        } else {
            // 先右旋再左旋
            return node = rotateDoubleLeft(node);
        }
    }
    return left;
}