Concept
현재 노드의 값보다 작으면 왼쪽 자식 노드에, 크면 오른쪽 자식 노드에 값을 저장하는 이진 트리
연결리스트는 삽입/삭제 시간이 O(1)이지만 탐색 시간이 O(n)으로 느리고 이진탐색은 탐색 시간이 O(log n)이지만 삽입/삭제가 불가능하므로 이 둘을 보완한 자료구조가 BST이다.
Time Complexity
Worst Case
균형 잡히지 않고 한줄로 늘어진 트리의 경우가 문제가 됨
Access : O(n)
Search : O(n)
Insertion : O(n)
Deletion : O(n)
Average Case
Access : O(log n)
Search : O(log n)
Insertion : O(log n)
Deletion : O(log n)
Space Complexity
Worst Case
O(n)
Example
#include <stdio.h>
#include <stdlib.h>
typedef struct _node {
struct _node *left;
struct _node *right;
int value;
} Node;
typedef struct _bst {
Node *root;
} BST;
BST *createBST() {
BST *bst = (BST *) malloc(sizeof(BST));
bst->root = NULL;
return bst;
}
void _put(Node *node, Node *new) {
if(node->value > new->value) {
if(node->left) _put(node->left, new);
else node->left = new;
}
else {
if(node->right) _put(node->right, new);
else node->right = new;
}
}
void put(BST *bst, int value) {
Node *new = (Node *)malloc(sizeof(Node));
new->left = NULL;
new->right = NULL;
new->value = value;
if(bst->root) _put(bst->root, new);
else bst->root = new;
}
int _get(Node *node, int value) {
if (node->value == value) {
return value;
}
else if (node->value > value) {
if(node->left) return _get(node->left, value);
else return -1;
}
else {
if(node->right) return _get(node->right, value);
else return -1;
}
}
int get(BST *bst, int value) {
return _get(bst->root, value);
}
void _trav(Node *node) {
if(node->left) _trav(node->left);
printf("%d ", node->value);
if(node->right) _trav(node->right);
}
void print(BST *bst) {
_trav(bst->root);
}
int main() {
BST *bst = createBST();
put(bst, 1);
put(bst, 2);
put(bst, 3);
put(bst, 4);
put(bst, 5);
put(bst, 10);
print(bst);
int result = get(bst, 6);
printf("\n%d\n", result);
return 0;
}