이진탐색트리

📖스케줄링 문제에 접근하는 이진 탐색 트리

• 정의 : 이진트리 기반의 탐색을 위한 자료구조
  • 이진트리 : 모든 노드가 2개의 subtree를 갖는 트리
    • 모든 노드의 차수는 2 이하 -> 최대 2개까지의 자식노드를 가질 수 있다
    • left subtree와 right subtree는 반드시 구별되어야 한다
  • 탐색 : 컴퓨터, 자료구조에서의 핵심적인 응용 분야
• 특징
  • nearly complete X
  • 왼쪽 노드 키 < 오른쪽 노드 키
  • 각각의 노드가 2개이하의 노드를 갖고 있어야한다
  • 모든 노드 x에 대해 if y가 x의 left subtree에 있다면 key(y) <= key(x),
    if y가 right subtree에 있다면 key(y) >= key(x)
  • balanced가 되기 위해서는 left(h)와 right(h)가 비슷해야한다
• 연산
  • insert(n): 이진 탐색 트리의 특성을 유지하면서 새로운 노드 n 을 이진 탐색 트리에 삽입한다
  • remove(n): 이진 탐색 트리의 특성을 유지하면서 노드 n 을 트리에서 삭제한다
  • search(key): 키 값이 key 인 노드를 찾아 반환한다

1) 탐색 연산 구현

• 일반함수로 구현 (순환적)

BinaryNode* searchRecur (BinaryNode* n, int key){

		if(n == NULL) return NULL;
		if(key == n->getData ()) return n;
		else if (key < n->getData ())
        		return searchRecur (n->getLeft(), key);
		else
        		return searchRecur (n->getRight(), key);

}

• 노드의 멤버함수로 구현 (순환적)

BinaryNode* BinaryNode ::search(int key){
		if( key == data ) return this;
		else if (key < data && left!=NULL) 
			return left ->search(key);
		else if (key > data && right!=NULL )
			return right ->search(key);
		else
			return NULL;
            
}

2) 삽입 연산 구현

• 일반함수/트리 멤버 함수로 구현 (순환적)

void insertRecur ( BinaryNode* r, BinaryNode* n ) {
		if( n ->getData() == r ->getData() ) 
			return;
		else if ( n->getData () < r->getData () ) {
				if( r->getLeft () == NULL ) r->setLeft(n);
				else insertRecur ( r->getLeft(), n );
}
		else{
			if( r->getRight () == NULL ) r->setRight(n);
			else insertRecur ( r->getRight(), n);
	}
}

3) 삭제 연산 구현

• 일반함수로 구현 (순환적)

void remove ( BinaryNode* parent , BinaryNode* node ) {
// case 1 : 삭제하려는 노드 -> 단말 노드
if( node->isLeaf () ) {
	if( parent == NULL ) root = NULL;
	else {
		if( parent->getLeft () == node )
			parent->setLeft(NULL);
		else
			parent->setRight(NULL);
	}
}
//case 2 : 삭제하려는 노드 -> 한쪽 자식만 갖는 경우
else if ( node->getLeft ()== NULL || node->getRight() == NULL ) {
	BinaryNode* child = node->getLeft () != NULL)
? node->getLeft () : node->getRight();
	if( node == root )
		root = child;
	else {
		if( parent->getLeft () == node )
			parent->setLeft (child);
		else
			parent->setRight (child);
	}
}
//case 3 : 삭제하려는 노드 ->  두 개의 자식 모두 있는 경우
else{
	BinaryNode* succp = node;
	BinaryNode* succ = node->getRight();
	while(succ->getLeft () != NULL ) {
		succp = succ;
		succ = succ->getLeft();
}
if( succp->getLeft () == succ )
	succp -> setLeft(succ->getRight());
else
	succp->setRight(succ->getRight());
node->setData(succ->getData());
node = succ;
	}
delete node;
}

 

📖Big-O

• Big-O 정의 : 시간복잡도함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 수 있도록 시간복잡도를 표시하는 방법
  (=시간복잡도 함수에서 실제로 영향력을 끼치는 부분)
  • 시간복잡도 : 알고리즘의 실행 시간 분석
• Big-O 특징
  • 시간복잡도 함수가 다항식으로 표시된 경우, 최고차항의 차수가 Big-O가 된다
  • 많이 사용되는 Big-O 표기법의 실행 시간 순
    

    

• 이진 탐색 트리와 Big-O
  • 최선의 경우
    • 시간복잡도 : O(log n)
  • 최악의 경우
    • 시간복잡도 : O(n)

💻문제풀이

LeetCode 98번 - Validate Binary Search Tree
이진 트리의 루트가 지정된 경우 유효한 이진 검색 트리(BST)인지 확인한다.

• 풀이

class Solution {
	int arr[1024];
	int n = 0;
public:
	void check(TreeNode* p){
        if(p==NULL) return;
        check(p->left);
        check(p->right);
   }
    bool isValidBST(TreeNode* root) {
        check(root);
        for(int i=0; i<n-1; i++) {
            if(arr[i] >= arr[i+1]) 
                return false;    
        }        
        return true;
    }
};

LeetCode 99번 - Recover Binary Search Tree
BST(Binary Search Tree)의 루트가 주어졌는데, 여기서 정확히 두 노드의 값이 실수로 스왑되었다. 트리의 구조를 변경하지 않고 복구해야 한다.

• 풀이

class Solution {
public:
    void recoverTree(TreeNode* root) {
        if(root == NULL) return;
        TreeNode* p = NULL;
        TreeNode* f = NULL;
        TreeNode* s = NULL;
        while(root!=NULL){
            if(root->left == NULL){
                if(p!=NULL && (p->val > root->val)){
                    if(f==NULL){
                        f=root;
                    }
                
                else{
                    s=root;
                }
            }
        
            p=root;
            root=root->right;
            }
             
                
            else{
                TreeNode* t = root->left;
                while(t->right!=NULL && t->right!=root){
                    t=t->right;
                }
                if(t->right==NULL){
                    t->right=root;
                    root=root->left;
                }
                else{
                    t->right=NULL;
                    if(p!=NULL && (p->val > root->val)){
                        if(f==NULL){
                            f=p;
                        }
                        s=root;
                    }
                    p=root;
                    root=root->right;
                }
            }
        }

            int t = f->val;
            f->val=s->val;
            s->val=t;
    
    }
};

LeetCode 700번 - Search in a Binary Search Tree
BST에서 노드의 값이 val인 노드를 찾아 해당 노드로 루팅된 하위 트리를 반환한다. 이러한 노드가 없으면 null을 반환한다

• 풀이

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

LeetCode 701번 - Insert into a Binary Search Tree
BST(이진 검색 트리)의 루트 노드와 트리에 삽입할 값이 제공된다. 삽입 후 BST의 루트 노드를 반환한다. 새로운 값이 원래 BST에 존재하지 않는다는 것이 보장된다.

• 풀이

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        TreeNode* n = new TreeNode(val);
        if(!root) return n;
        if(root->val < val){
            root->right = root->right ? insertIntoBST(root->right,val) : n;
        }
        else{
            root->left = root->left ? insertIntoBST(root->left,val) : n;
        }return root;
    }
};