//

// AVLTree.m

// BaseAlgorithm

//

// Created by 陈超 on 2020/5/2.

// Copyright © 2020年 kayak. All rights reserved.

//

#import "AVLTree.h"

typedef struct Node{

int key;

struct Node *left;

struct Node *right;

struct Node *parent;

int height;

int distanceToRoot;

}Node;

typedef struct LinkNode{

Node*node;

int nodeDepth;

struct LinkNode*next;

}LinkNode;

@implementation AVLTree

static Node *root;

static int leftminDistance = 0;//主意，根节点左边的节点到根节点的距离为负数

static int rightMaxDistance = 0;

static int currentLevel = 0;

static int maxLevel = 0;

-(void)test{

int arr[] = {99,14,2,3,6,7,21,89,97,32,33,8};

int len = sizeof(arr)/sizeof(*arr);

root = NULL;

for (int i=0;i<len;i++) {

Node *node = (Node*)calloc(1, sizeof(Node));

node->key = arr[i];

node->height = 1;

node->distanceToRoot = 0;

addNode(node);

}

printNodeInLevel(root);

printf("\n-----------------------------\n");

removeByKey(3);

removeByKey(7);

printNodeInLevel(root);

}

void travelPreOrder(Node*node){

currentLevel++;

if(currentLevel>maxLevel){

maxLevel = currentLevel;

}

if(node->left){

node->left->distanceToRoot = node->distanceToRoot - 1;

if(leftminDistance>node->left->distanceToRoot){

leftminDistance = node->left->distanceToRoot;

}

travelPreOrder(node->left);

}

if(node->right){

node->right->distanceToRoot = node->distanceToRoot + 1;

if(rightMaxDistance<node->right->distanceToRoot){

rightMaxDistance = node->right->distanceToRoot;

}

travelPreOrder(node->right);

}

currentLevel --;

}

int removeByKey(int key){

Node *node = root;

while(1){

if(node->key>key){

if(node->left){

node = node->left;

}else {

return -1;

}

}else if(node->key<key){

if(node->right){

node = node->right;

}else {

return -1;

}

}else {

removeNode(node);

return 0;

}

}

}

void addNode(Node *node){

if(!root){

root = node;

return;

}

Node *parent = root;

while(true){//找到合适的位置插入节点

if(node->key<parent->key){

if(!parent->left){

parent->left = node;

node->parent = parent;

break;

}else {

parent = parent->left;

}

}else if(node->key>parent->key){

if(!parent->right){

parent->right = node;

node->parent = parent;

break;

}else {

parent = parent->right;

}

}

}

afterAdd(node);

}

void afterAdd(Node*node){

//更新高度

Node *p = node->parent;

while(p){

int balanced = isBalanced(p);

if(balanced){//失去平衡

p->height = getHeight(p);

}else {

adJustBalance(p);

break;

}

p = p->parent;

}

}

Node * findSuccessor(Node *node){//寻找后继节点

if(node->right){//有右字树

Node *left = node->right->left;

while(left&&left->left){

left = left->left;

}

return left;

}else {//没有右子树

Node *parent = node->parent;

while(parent&&parent->left!=node){

parent = node->parent;

}

return parent;

}

}

void removeNode(Node*node){

if(node->left&&node->right){//是度为2的节点

//用它的后继替代它

Node *successor = findSuccessor(node);

//让后继和其 parent 切断联系

if(successor->parent->left==successor){

successor->parent->left = NULL;

}else {

successor->parent->right = NULL;

}

successor->parent = NULL;

if(node->parent){

if(node->parent->left == node){

node->parent->left = successor;

}else {

node->parent->right = successor;

}

successor->parent = node->parent;

}

successor->left = node->left;

node->left->parent = successor;

successor->right = node->right;

node->right->parent = successor;

}else if(node->left||node->right){//是度为1的节点,让唯一的子节点成为自己 parent的子节点

Node *child = node->left;

if(!child){

child = node->right;

}

if(node->parent){

if(node->parent->left==node){

node->parent->left = child;

}else {

node->parent->right = child;

}

child->parent = node->parent;

}

}else {//是叶子根节点

if(node==root){//也是根节点

root = nil;

}else {//是叶子节点

if(node->parent->left==node){

node->parent->left = NULL;

}else {

node->parent->right = NULL;

}

}

}

//切断被删除的节点与原来的树的所有联系

Node *parent = node->parent;

node->parent = node->left = node->right = NULL;

afterRemove(parent);

}

void afterRemove(Node *node){

Node *p = node;

while(p){

if(isBalanced(p)){

p->height = getHeight(p);

}else {

adJustBalance(p);

}

p = p->parent;

}

}

void updateHeight(Node *node){

int leftHeight = 0;

if(node->left){

updateHeight(node->left);

leftHeight = node->left->height;

}

int rightHeight = 0;

if(node->right){

updateHeight(node->right);

rightHeight = node->right->height;

}

if(node->key==3){

int key = node->key;

}

if(node->left==NULL&&node->right==NULL)

{

node->height= 1;

}else {

node->height = MAX(leftHeight+1, rightHeight+1);

}

}

int getHeight(Node *node){

if(node==NULL){

return 0;

}

int leftHeight = 0,rightHeight = 0;

if(node->left){

leftHeight = node->left->height;

}

if(node->right){

if(node->right->height>rightHeight){

rightHeight = node->right->height;

}

}

return MAX(leftHeight, rightHeight)+1;

}

void adJustBalance(Node *node){

int leftHeight = 0,rightHeight = 0;

if(node->left){

leftHeight = node->left->height;

}

if(node->right){

rightHeight = node->right->height;

}

if(leftHeight>rightHeight){//左边失衡

Node *left = node->left;

leftHeight = 0;rightHeight = 0;

if(left->left){

leftHeight = left->left->height;

}

if(left->right){

rightHeight = left->right->height;

}

if(leftHeight>rightHeight){//LL型

rotateRight(node);

}else {//LR型

rotateLeft(left);

rotateRight(node);

}

}else{//右边失衡

Node *right = node->right;

leftHeight = 0;rightHeight = 0;

if(right->left){

leftHeight = right->left->height;

}

if(right->right){

rightHeight = right->right->height;

}

if(leftHeight>rightHeight){//RL型

rotateRight(right);

rotateLeft(node);

}else {//RR型

rotateLeft(node);

}

}

}

/**

右旋的定义是把左边的部下提升为上级，顶替自己，自己给左边的部下当右部下

*/

void rotateRight(Node*node){

Node *parent = node->parent;

Node *left = node->left;

if(parent){

if(parent->left==node){

parent->left = left;

}

if(parent->right==node){

parent->right = left;

}

}else {

root = left;

}

left->parent = parent;

//左部下原来的右部下（如果有）作为自己的左部下

if(left->right){

left->right->parent = node;

}

node->left = left->right;

//自己作为原来来的左部下的右部下

left->right = node;

node->parent = left;

//更新高度

node->height = getHeight(node);

left->height = getHeight(left);

}

/**

左旋的定义是把右边的部下提升为上级，顶替自己，自己给右边的部下当左部下

*/

void rotateLeft(Node *node){

Node *parent = node->parent;

Node *right = node->right;

if(parent){

if(parent->left==node){

parent->left = right;

}

if(parent->right==node){

parent->right = right;

}

}else {

root = right;

}

right->parent = parent;

//右部下原来的左部下(如果有)作为自己的右部下

if(right->left){

right->left->parent = node;

}

node->right = right->left;

//自己作为原来来的右部下的左部下

right->left = node;

node->parent = right;

//更新高度

node->height = getHeight(node);

right->height = getHeight(right);

}

int isBalanced(Node *node){

int leftHeight = 0,rightHeight = 0;

if(node->left){

leftHeight = node->left->height;

}

if(node->right){

rightHeight = node->right->height;

}

return abs(leftHeight-rightHeight)<2;

}

void deleteNode(Node *node){

}

void printNodeInLevel(Node *parent){

travelPreOrder(root);

if(parent==NULL) return;

LinkNode linkNode = {parent,0,NULL};

LinkNode *head = &linkNode;

LinkNode *tail = head;

int nodeDepth = tail->nodeDepth;

int keyWidth = 2;//打印的key 占几个字节

int maxDistanceAbs = keyWidth*powl(2, maxLevel);

int lastBlackSpaceCount = 0;

while (1) {

int blackSpaceCountToPrint = 0;

if(head->node->parent&&head->node == head->node->parent->left){//是其父节点的左子节点

head->node->distanceToRoot = head->node->parent->distanceToRoot - maxDistanceAbs/powl(2,head->nodeDepth);

}else if(head->node->parent&&head->node == head->node->parent->right){////是其父节点的右子节点

head->node->distanceToRoot = head->node->parent->distanceToRoot + maxDistanceAbs/powl(2,head->nodeDepth);

}else {//是根节点

head->node->distanceToRoot = 0;

}

if(nodeDepth==0||nodeDepth!=head->nodeDepth){//新一层的开头

blackSpaceCountToPrint = head->node->distanceToRoot+maxDistanceAbs;

lastBlackSpaceCount = blackSpaceCountToPrint;

nodeDepth = head->nodeDepth;

printf("\n");

}else{//不是新一层的开头

int leftBlackSpaceCount = head->node->distanceToRoot+maxDistanceAbs;

blackSpaceCountToPrint = leftBlackSpaceCount - lastBlackSpaceCount;

lastBlackSpaceCount = leftBlackSpaceCount;

}

int _blankSpaceCountToPrint = blackSpaceCountToPrint;

while (_blankSpaceCountToPrint--) {

printf(" ");

}

int key = 0;

if(head->node->parent){

key = head->node->parent->key;

}

// printf("%02d{%d}{%d}{%d}",head->node->key,head->node->distanceToRoot,key,lastBlackSpaceCount);

printf("%02d",head->node->key);

if(parent->left){

LinkNode *newNode = (LinkNode*)calloc(1, sizeof(LinkNode));

newNode->node = parent->left;

newNode->nodeDepth = head->nodeDepth + 1;

tail->next = newNode;

tail = newNode;

}

if(parent->right){

LinkNode *newNode = (LinkNode*)calloc(1, sizeof(LinkNode));

newNode->node = parent->right;

newNode->nodeDepth = head->nodeDepth+1;

tail->next = newNode;

tail = newNode;

}

if(head->next){

head = head->next;

parent = head->node;

}else {

head = NULL;

break;

}

}

}

@end