[Coding Interview University] 이진 탐색 트리 : 이론 및 구현

<본 블로그는 코딩인터뷰대학 님의 Git과 서적을 참고해서 공부하며 작성하였습니다 :-)>

 

🫧 이진탐색트리

: “모든 왼쪽 자식들 ≤ n < 모든 오른쪽 자식들” 속성은 모든 노드 n에 대해서 반드시 참이어야 함

: 모든 노드에 대해서 왼쪽 자식들의 값이 현재 노드 값보다 작거나 같도록 하고, 오른쪽 자식들 값은 현재 노드의 값보다 반드시 커야함

 

🫧 균형 vs 비균형

• 균형
  • 레드 블랙 트리
  • AVL 트리

 

🫧 완전이진트리

: 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리

: 마지막 단계는 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 함

 

🫧 전이진트리

: 모든 노드의 자식이 없거나 정확히 두 개 있는 경우

: 자식이 하나만 있는 노드가 존재해서는 안됨

 

🫧 포화이진트리

: 전 이진 트리이면서 완전 이진 트리인 경우

: 모든 말단 노드는 같은 높이에 있어야 하며, 마지막 단계에서 노드의 개수가 최대가 되어야 한다

: 노드의 개수가 정확히 2^K-1 (K는 트리의 높이) 개

 

🫧 이진 탐색 트리 탐색

1. 루트 노드의 키와 찾고자 하는 값을 비교한다. 찾고자 하는 값이라면 탐색을 종료한다
2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행한다
3. 찾고자 하는 값이 루트노드의 키보다 크다면 오른쪽 서브트리로 탐색을 진행한다

TreeNode* search(TreeNode* root, int key){
    if(root == NULL){    // 값을 찾지 못한 경우  
        return NULL;
    }
    
    if(key == root->key){    // 값을 찾음 
        return root;
    }
    else if(key < root->key){    // 왼쪽 서브트리 탐색 
        search(root->left, key);
    }
    else if(key > root->key){    // 오른쪽 서브트리 탐색 
        search(root->right, key);
    }
    
}

 

🫧 이진 탐색 트리 삽입

1. 삽입할 값을 루트 노드와 비교해 같다면 오류를 발생한다 ( 중복 값 허용 X )
2. 삽입할 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리를 탐색해서 비어있다면 추가하고, 비어있지 않다면 다시 값을 비교한다
3. 삽입할 값이 루트노드의 키보다 크다면 오른쪽 서브트리를 탐색해서 비어있다면 추가하고, 비어있지 않다면 다시 값을 비교한다

Node* Insert(Node* node, int data)
{
    if(node == NULL)
    {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data;
        newNode->Left = NULL;
        newNode->Right = NULL;
        
        return newNode;
    }
    else
    {
        if(node->data > data)
        {
            node->Left = Insert(node->Left, data);
        }
        else if(node->data < data)
        {
            node->Right = Insert(node->Right, data);
        }
        else
        {
        	//중복 된 데이터이므로 추가하지 않는다.
        }
        
        return node;
    }
}

 

🫧 이진 탐색 트리 삭제

1. 삭제하려는 노드가 단말 노드(leaf node) 일 경우
2. 삭제하려는 노드의 서브 트리가 하나인 경우(왼쪽 혹은 오른쪽 서브 트리)
3. 삭제하려는 노드의 서브 트리가 두 개인 경우

Node* FindMinNode(Node* node, Node** minNode)
{
    if(node->Left == NULL)
    {
        *minNode = node;
        node = node->Right;
        return node;
    }
    else
    {
        node->Left = FindMinNode(node->Left, minNode);
        return node;
    }
}

Node* Delete(Node* node, int data)
{
    if(node == NULL) return NULL;
    
    if(node->data == data)
    {
        Node* deleteNode = node;
        if(node->Left == NULL && node->Right == NULL)
        {
            node = NULL;
        }
        else if(node->Left != NULL && node->Right == NULL)
        {
            node = node->Left;
        }
        else if(node->Left == NULL && node->Right != NULL)
        {
            node = node->Right;
        }
        else
        {
            Node* minNode = NULL;
            node->Right = FindMinNode(node->Right, &minNode);
            minNode->Left = deleteNode->Left;
            minNode->Right = deleteNode->Right;
            node = minNode;
        }
        
        free(deleteNode);
        return node;
    }
    else
    {
        if(node->data > data)
        {
            node->Left = Delete(node->Left, data);
        }
        else
        {
            node->Right = Delete(node->Right, data);
        }
        return node;
    }
}