Augmentation

📖 Data structures augmentation

• 데이터 구조가 효율적으로 구현될 수 있도록 기존 데이터 구조에 추가 정보 추가하는 것
• 이진 탐색 트리 노드에 서브 트리 노드 개수 정보 추가
  : root에서 내려와 해당 value보다 작거나 같으면 1을 더하고 왼쪽에 있는 서브 트리 개수를 더해준다.

📖 Rank

• 이진 탐색 트리에서 노드의 Rank는 왼쪽 서브트리의 노드 수가 중요하다.
• -코드

int getRank(Node* root, int x)
{
    if (root->data == x)
        return root->leftSize;
 
    if (x < root->data) {
        if (!root->left)
            return -1;
        else
            return getRank(root->left, x);
    }
 
    else {
        if (!root->right)
            return -1;
        else {
            int rightSize = getRank(root->right, x);
              if(rightSize == -1 ) return -1;
            return root->leftSize + 1 + rightSize;
        }
    }
}

📖 AVL tree

• 정의
  : 높이 균형을 맞추는 이진 탐색 트리
  : 왼쪽과 오른쪽 하위 트리의 높이 차이는 모든 노드에 대해 1을 넘어가면 안된다.
• Rotation 방식
  1) Right
  

BinaryNode *rotateLL(BinaryNode* parent){
	BinaryNode* child = parent->getLeft();
    parent->setLeft(child->getRight());
    child->setRight(parent);
    return child;
}

2) Left

BinaryNode *rotateRR(BinaryNode* parent){
	BinaryNode* child = parent->getRight();
    parent->setRight(child->getLeft());
    child->setLeft(parent);
    return child;
}

3) Left-Right

BinaryNode *rotateLR(BinaryNode* parent){
	BinaryNode* child = parent->getLeft();
    parent->setLeft(rotateRR(child));
    return rotateLL(parent);
}

4) Right-Left

BinaryNode *rotateLL(BinaryNode* parent){
	BinaryNode* child = parent->getRight();
    parent->setRight(roteLL(child));
    return rotateRR(parent);
}

• Insertion
  -단계
  1) 이진 탐색 트리 삽입 로직을 사용하여 새 요소를 트리에 삽입한다.
  2) 요소를 삽입한 후에는 각 노드의 Balance Factor를 확인한다.
  3) 모든 노드의 Balance Factor가 0, 1 또는 -1과 같이 발견되면 알고리즘은 다음 연산을 위해 계속 진행된다.
  4) 위의 세 가지 값 이외의 노드의 균형 value가 올 때 트리는 불균형하다고 한다. 그다음 적절한 Rotation 방식을 수행하여 균형을 맞춘 후 다음 작업을 위해 알고리즘이 진행된다.
• -코드

BinaryNode* insertAVL(BinaryNode* parent, int data){
		if(data < parent->getData() ){
        	if(parent->getLeft() !=NULL)
            	parent->setLeft(insertAVL(parent->getLeft(),data));
            else
            	parent->setLeft(new BinaryNode(data));
           	return reBalance(parent);
        }
        else if (data > parent->getData()){
        	if(parent->getRight() != NULL)
            	parent->setRight(insertAVL(parent->getRight(),data));
            else
            	parent->setRight(new BinaryNode(data));
            return reBalance(parent);
        }
        else{
        	return NULL;
       	}
     }
};

• Deletion
  -단계
  1) 일반 이진 탐색 트리 삭제를 수행한다.
  2) 현재 노드는 삭제된 노드의 상위 노드 중 하나여야 하므로 현재 노드의 높이를 업데이트한다.
  3) 현재 노드의 Balance Factor를 가져온다.
  4) 균형 계수가 1보다 크면 현재 노드가 불균형 상태이고 LL이나 LR 상태인 것이다. 이를 확인하기 위해 왼쪽 하위 트리의 Balance Factor를 가져온다. 왼쪽 하위 트리의 Balance Factor가 0보다 크거나 같으면 LL이고, 그렇지 않으면 LR이다.
  5) 균형 계수가 -1보다 작으면 현재 노드가 불균형 상태이고 RR이나 RL 상태인 것이다. 이를 확인하기 위해 오른쪽 하위 트리의 Balance Factor를 가져온다. 오른쪽 하위 트리의 균형 계수가 0보다 작거나 같으면 RR이고, 그렇지 않으면 RL이다.
• -코드

BinaryNode* deleteNode(BinaryNode* root, int key) {
    if (root == NULL)
        return root;
 
    if ( key < root->key )
        root->left = deleteNode(root->left, key);
 
    else if( key > root->key )
        root->right = deleteNode(root->right, key);
 
    else {
        if((root->left == NULL) || (root->right == NULL)) {
            BinaryNode *temp = root->left ? root->left : root->right;
 
            if (temp == NULL) {
                temp = root;
                root = NULL;
            }
            else
            	*root = *temp;
            	free(temp);
        }
        else {
            BinaryNode* temp = minValueNode(root->right);
            root->key = temp->key;
            root->right = deleteNode(root->right,temp->key);
        }
    }
    if (root == NULL)
    	return root;
        
    root->height = 1 + max(height(root->left), height(root->right));

    int balance = getBalance(root);

    if (balance > 1 && getBalance(root->left) >= 0)
        return rightRotate(root);
 
    if (balance > 1 && getBalance(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    if (balance < -1 && getBalance(root->right) <= 0)
        return leftRotate(root);

    if (balance < -1 && getBalance(root->right) > 0)
    {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
 
    return root;
}

 

💻 문제풀이

Leetcode 110번 - Balanced Binary Tree
주어진 이진트리가 높이 균형 이진트리인지 판단한다.
이 문제에서 높이 균형 이진 트리는 다음과 같이 정의된다.
: 모든 노드의 왼쪽과 오른쪽 하위 트리의 높이 차이가 1이하인 이진트리

• 풀이

-접근 방식
1) 깊이 우선 탐색 순회를 이용하여 왼쪽과 오른쪽의 서브트리 높이를 구한다.
2) 왼쪽과 오른쪽 서브트리의 높이 차이가 1이 넘어 가지 않고 높이 균형이 맞는 경우 : return true
3) 2)가 아닌 경우 : return false

-코드

class Solution {
public:

	// 트리의 높이 균형 여부 확인
    bool isBalanced(TreeNode* root) {
    	// 왼쪽 서브트리와 오른쪽 서브트리의 높이 변수 각각 선언
        int ls, rs;
        
        // 트리가 empty인 경우 true 
        if(!root)
            return true;
            
        // 왼쪽과 오른쪽 서브 트리의 높이 구하기    
        ls = calheight(root->left);
        rs = calheight(root->right);
        
        // 접근방식의 2)와 3) 경우 확인
        if(abs(ls-rs)<=1&& isBalanced(root->left)&& isBalanced(root->right))
            return true;
        return false;
    }
    
    // 트리의 높이 계산
    int calheight(TreeNode* node){
    	// 트리가 empty인 경우 false
        if(!node)
            return false;
        // 트리가 empty가 아닌 경우 트리 높이 구하기 
        return 1 + max(calheight(node->left),calheight(node->right));
    }
};