[Data Structure]이진 탐색 트리(Binary Search Tree, BST)

이진 탐색 트리(BST)란? 각 원소들이 중복되지 않는 key를 갖고 있고, 각 노드들에 대해 key(왼쪽 서브트리) < key(루트 노드) < key(오른쪽 서브트리)를 만족하는 이진 트리를 의미합니다.

BST는 선형 자료구조에서 연산들이 O(n)의 시간복잡도로 수행되는 것이 매우 느리다고 판단되어 고안된 자료구조입니다. 이진 탐색 트리의 구현 BST는 기본적으로 이진 트리의 확장이므로 그 구조는 이진 트리와 동일합니다. typedef struct _BSTNode { Key key; struct _BSTNode *left_child; struct _BSTNode *right_child; } BSTNode; 이진 탐색 트리는 기본적으로 다음과 같은 연산들을 갖고 있습니다.

대부분 이진 트리가 갖고 있는 연산들의 변형입니다. BSTNode* createNode(Key key); // 새 노드를 생성한다. void destroyNode(BSTNode* node); // 노드를 삭제한다....

요청 처리 중입니다...

[Data Structure]이진 탐색 트리(Binary Search Tree, BST)

등록된 다른 글