이진 탐색트리

이진 탐색 트리 

1. 이진트리의 조건을 유지하면서 
2. 자기 부모나 루트보다 작거나 같은 값들은 왼쪽으로 큰 값들은 오른쪽으로 보내버리는 이진트리를 의미한다. 

3. 이에 대응하는 서브트리들도 이 조건들을 모두 만족해야한다. 

 

그림으로 만들어보면 아래와 같이 볼 수 있을 것이다. 

작으면 왼쪽 크면 오른쪽

특정한 값을 검색하고 찾는데 더 효율적일 것이다. 

 

입력, 탐색, 삭제 모두  높이에 비래해서 시간복잡도가 걸린다. O(n)이다. 

 

입력은 특정한 값이 들어오면 루트나 부모와 비교하여 왼쪽 혹은 오른쪽으로 이동하게 만들어준다. 계속 자기의 자리를 찾아가다 자리를 완전히 찾게되면 node를 반환해준다. 트리는 누가봐도 재귀를 사용하시요 같은 구조이다. 그래서 값을 비교하여 재귀를 통해 값을 넣어줄 수 있다. 

Node* addNode(Node *root, int value){
	if(root==NULL)
		return makingNode(value);
	else{
		if(root->value < value)
			root->right = addNode(root->right ,value); 
		else 
			root->left = addNode(root->left ,value);
	}
	return root;
}

삭제 

삭제는 전체적으로 세가지 경우가 발생할 수 있다. 

 

1. 자식노드가 없는 노드를 삭제 
    이것은 단순하게 삭제해주면 된다. 

2. 자식노드가 한개일 때
    남은 한개의 자식을 다시 이어주면 된다. 

3. 자식노드가 2개일 때

      이때는 특이한데 Successor를 구한다고 한다. Successor는 지우는 데이터의 바로 오른쪽 자식 노드에서 부터 제일 왼쪽의 노드를 넣어주면 된다. 밑에 예를 들어서 50의 오른쪽노드 70의 제일 왼쪽 노드 60을 50대신 넣어주면 된다. 

Node* deleteNode(Node* root, int value){
	if(root == NULL) return root;

	if(root->value < value)
		root->right = deleteNode(root->right, value);
	else if (root->value > value)
		root->left = deleteNode(root->left, value);
	else {
		if(root->left == NULL){
			Node *temp = root->right;
			free(root);
			return temp;
		}else if (root->right == NULL){
			Node *temp = root->left;
			free(root);
			return temp;
		}
		Node* temp = getSuccessor(root->right);
		root->value = temp->value;
		deleteNode(root->right, temp->value);

	}

	return root;
}


Node* getSuccessor(Node *node){
	Node *current = node;

	while(current->left!=NULL)
		current = current->left;

	return current;
}

지우는 노드의 오른쪽 노드의 제일 왼쪽의 노드를 반환해주는 함수 getSuccessor도 있다. 

 

검색

검색트리니 당연히 검색의 기능이 있어여한다. 이것도 대부분의 아이디어와 동일하다 못찾거나 같은 것을 찾으면 노드를 반환해주고 현재 노드와 key값을 비교하여 오른쪽 왼쪽으로 이동하는 방법이다. 이방법 또한 O(n)의 시간복잡도가 걸린다. 

 

Node* search(Node* root, int key){
	if(root == NULL || root->value == key)
		return root;
	if(root->value < key)
		retrun search(root->right ,key);
	
		return search(root->left, key);
}