[탐색] 이진탐색트리 (BST)

struct node {
	int key;
	struct node* l;
	struct node* r;
};


struct node* TreeInit() {
	node* t, * head;
	head = new node;
	head->l = NULL;
	head->r = NULL;
	head->key = 0;

	return head;
}

struct node* TreeSearch(struct node* head, int xkey) {
	struct node* t;
	if (head->key == xkey) return (head);
	t = head->r;
	while (t != NULL) {
		if (xkey == t->key) return(t);
		if(t!=NULL) if (xkey < t->key) t = t->l;
		if(t!= NULL) if (xkey > t->key) t = t->r;
	}
	return(NULL);
}

void TreeInsert(struct node* head, int xkey) {
	struct node* p, * t;
	p = head; t = p->r;
	while (t != NULL) {
		p = t;
		if (xkey == t->key)return;
		else if (xkey < t->key) t = t->l;
		else t = t->r;
	}
	t = new node;//새로운 노드 생성
	t->key = xkey; t->l = NULL; t->r = NULL; // 자식없음
	if (xkey < p->key) p->l = t; //부모와 비교하여 크면 좌 작으면 우에 배치
	else p->r = t;
}

struct node* minValueNode(struct node* node) {
	struct node* current = node;

	while (current->l != NULL) {
		current = current->l;
	}

	return current;
}
struct node* deleteNode(struct node* root, int key) {
	if (root == NULL) return root;

	if (key < root->key) root->l = deleteNode(root->l, key);
	else if (key > root->key) root->r = deleteNode(root->r, key);
	else {
		if (root->l == NULL) { // 자식이 없을때
			struct node* temp = root->r;
			free(root);
			return temp;
		}
		else if (root->r == NULL) // 자식이 하나
		{
			struct node* temp = root->l;
			free(root);
			return temp;
		}
		//자식이 둘
		struct node* temp = minValueNode(root->r);
		root->key = temp->key;
		root->r = deleteNode(root->r, temp->key);
	}
	return root;
}

시간 복잡도

 

삽입 : O(logN)

제거 : O(logN)

탐색 : O(logN)

 

단, 편향트리일 경우 O(N) 가능