Written by nodejs-style
on 2021-08-02

[C++] 이진 검색 트리(BST,binary search tree) 구현하기, code - 컴...

728x90

이진 검색 트리(BST, Binary Search Tree)는 널리 사용되는 형태의 이진트리이다. BST는 다음과 같은 속성이 있다.

부모 노드의 값 ≥ 왼쪽 자식 노드의 값

부모 노드의 값 ≤ 오른쪽 자식 노드의 값

이러한 관계식은 부모 노드보다 작거나 같은 모든 원소는 항상 왼쪽에 있고, 부모 노드보다 크거나 같은 원소는 항상 오른쪽에 있게 된다. 따라서 원소 검색을 위해 루트 노트부터 차례대로 값을 비교하는 경우, 각 단계마다 검색 범위가 절반으로 줄어든다.

BST가 마지막 레벨을 제외한 모든 노트에 두 개의 자식 노드가 있을 경우, 이 트리의 높이는 log2(N)이 된다. 여기서 N은 원소의 개수를 말한다. BST의 검색 및 삽입 동작은 O(log N)의 시간 복잡도를 갖는다.

#include using namespace std; struct node { int data; node* left; node* right; }; struct BST { node* root = nullptr; node* find(int value) { return find_impl(root,value); } public: void insert(int value) { if(!root) root=new node{value,nullptr,nullptr}; else insert_impl(root,value); } void inorder() { inorder_impl(root); } void deleteValue(int value) { root = delete_impl(root,value); } node* succesor(node* start) { auto current = start->right; while(current && current->left) current = current->left; return current; } private: node* find_impl(node* cur, int value) { if(!cur) { cout<< endl; return nullptr; } if(cur->data == value) { cout << value << "을 찾았습니다." left,value); return find_impl(cur->right,value); } node* insert_impl(node* cur,int value) { if(valuedata) { if(!cur->left) cur->left = new node{value,nullptr,nullptr}; else insert_impl(cur->left,value); } else { if(!cur->right) cur->right =new node{value,nullptr,nullptr}; else insert_impl(cur->right,value); } } void inorder_impl(node* cur) { if(!cur) return; inorder_impl(cur->left); cout << cur->data << " "; inorder_impl(cur->right); } node* delete_impl(node* start, int value) { if(!start) return nullptr; if(value < start->data) start->left = delete_impl(start->left,value); else if(value > start->data) start->right = delete_impl(start->right,value); else { if(!start->left) { auto tmp = start->right; delete start; return tmp; } if(!start->right) { auto tmp = start->left; delete start; return tmp; } auto succNode = succesor(start); start->data = succNode->data; start->right = delete_impl(start->right , succNode->data); } return start; } }; int main(void) { BST tree; tree.insert(12); tree.insert(5); tree.insert(4); tree.insert(7); tree.insert(34); tree.insert(54); tree.insert(1); tree.insert(4); tree.insert(4); tree.insert(3); cout << "중위 순회: "; tree.inorder(); cout << endl; tree.deleteValue(12); cout << "12를 삭제한 후 중위 순회 : "; tree.inorder(); cout<< endl; if(tree.find(12)) cout << "12 발견." <

728x90

from http://comdolidol-i.tistory.com/186 by ccl(A) rewrite - 2021-08-02 09:26:57

Top