[자료구조] 이진탐색트리

1. 이진탐색트리란?

이진탐색트리: BST, Binary Search Tree로 이진트리 기반의 효율적인 탐색 작업을 위한 자료구조이다.

이진탐색트리의 정의

• 모든 노드는 유일한 키를 갖는다.
• 왼쪽 서브트리의 키들은 루트의 키보다 작다.
• 오른쪽 서브트리의 키들은 루트의 키보다 작다.
• 왼쪽과 오른쪽 서브트리도 이진탐색트리이다.
• key(왼쪽서브트리) ≤ key(루트노드) ≤ key(오른쪽서브트리)

2. 이진탐색트리의 연산

2.1 탐색 연산

탐색 방법

• 주어진 탐색키와 현재의 루트 노드의 키 값을 비교한다.
• 비교한 결과가 같으면 탐색 끝.
• key(탐색키) < key(루트 노드의 키)이면, 루트 노드의 왼쪽 자식을 기준으로 다시 탐색 시작.
• key(탐색키) > key(루트 노드의 키)이면, 루트 노드의 오른쪽 자식을 기준으로 다시 탐색 시작.

2.2 삽입 연산

삽입 방법

• 먼저 탐색을 수행.
• 이진 탐색 트리에서는 같은 키 값을 갖는 노드가 없어야 한다.
• 탐색이 실패로 끝날 경우 그 위치에 새로운 노드 삽입.
• 탐색이 성공하면 이미 같은 키 값을 갖는 노드가 있는것이므로 삽입 불가능.

삽입 알고리즘

insert (root, n)

if KEY(n) = KEY(root) 				// root와 키가 같으면
	then return; 					// return
else if KEY(n) < KEY(root) then 	// root보다 키가 작으면
	if LEFT(root) = NULL 			// root의 왼쪽 자식이
		then LEFT(root) ← n; 		// 없으면 n이 왼쪽 자식
		else insert(LEFT(root),n); 	// 있으면 순환 호출
else 								// root보다 키가 크면
	if RIGHT(root) = NULL
		then RIGHT(root) ← n;
		else insert(RIGHT(root),n);

2.3 삭제 연산

삭제 방법 case1: 단말 노드 삭제

• 먼저 탐색을 수행.
• 단말노드의 부모노드를 찾아서 연결을 끊으면 됨.
  

삭제 방법 case2: 자식이 하나인 노드 삭제

• 노드 삭제.
• 삭제된 노드의 자식을 부모 노드에 붙여줌.
  

삭제 방법 case3: 두 개의 자식을 가진 노드 삭제

• 삭제되는 노드와 가장 값이 비슷한 노드를 삭제 노드 위치로 가져옴.
• 삭제되는 노드와 가장 값이 비슷하 노드: 왼쪽 서브트리에서 제일 큰 값 or 오른쪽 서브트리에서 제일 작은 값

3. [예제]

LeetCode 98. Validate Binary Search Tree

class Solution {
public:
    bool isValid(TreeNode* root, TreeNode* low, TreeNode* high) {
        if(!root)   return true;

        if(low && root->val <= low->val)    return false;
        if(high && root->val >= high->val)  return false;
        
        return isValid(root->right, root, high) && isValid(root->left, low, root);
    }
    
    bool isValidBST(TreeNode* root) {
        return isValid(root, nullptr, nullptr);
    }
};

LeetCode 99. Recover Binary Search Tree

class Solution {
public:
    vector<int> val;
    int first, second;
    
    void InorderTraversal(TreeNode* root){
        if(root==NULL){
            return;
        }    
        
        InorderTraversal(root->left);
        val.push_back(root->val);
        InorderTraversal(root->right);
    }
    
    void changeValTree(TreeNode *root){
        if(root==NULL){
            return;
        }
        
        changeValTree(root->left);
        
        if((root->val)==first){
            (root->val) = second;
        }else if((root->val)==second){
            (root->val) = first;
        }
        
        changeValTree(root->right);
    }
    
    void recoverTree(TreeNode* root) {
        InorderTraversal(root);
        
        int prev = val[0];
        first = NULL, second = NULL;
        for(int i=1; i<val.size(); i++){
            if(prev>val[i] && first==NULL){
                first = prev;
            }
            
            if(prev>val[i] && first!=NULL){
                second = val[i];
            }
            
            prev = val[i];
        }
                
        changeValTree(root);
    }
};

LeetCode 700. Search in a Binary Search Tree

class Solution {
public:
	TreeNode* serchBST(TreeNode* root, int val) {
		if(root == NULL) {
			return NULL;
		}
        if(root->val == val) {
        	return root;
        }
		else if(root->val < val) {
			if(root->right == NULL) return NULL;
			return serchBST(root->right, val);
		}
		else {
			if(root->left == NULL) return NULL;
			return serchBST(root->left, val);
		}
	}
};

LeetCode 701. Insert into a Binary Search Tree

public TreeNode insertIntoBST(TreeNode root, int val) {

    if(root==null) return new TreeNode(val);
    if(root.val > val){
        root.left = insertIntoBST(root.left,val);
    }else{
        root.right = insertIntoBST(root.right,val);
    }
    return root;
}