개발일지

구현　위의 검색 / 삽입 / 삭제의 특성을 가지는 BST를 구현하는 시간을 가지도록 하자. #include using namespace std;struct Node{ int _data; Node* _left, * _right;};　트리에 사용될 노드 구조체 Node를 선언한다. class BST{ Node* _root;public: BST() : _root(nullptr) {}　이진 탐색 트리 클래스 BST를 선언하고, 기본 생성자를 통해 루트 노드를 nullptr로 초기화해 준다. class BST{ ... Node* Find_Implementation(Node* node, int value) { if (!node) // node가 존재하지 않는 경우 return NULL; if (node->_..

이진 검색 트리 (BST)개요　이진 검색 트리(Binary Search Tree - BST)는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 이진트리의 일종으로서, 특정한 규칙을 통해 검색을 하는 자료구조다. 각 노드는 하나의 값을 가지며, 다음과 같은 특징이 있다.왼쪽 노드의 값 ≤ 부모 노드의 값 ≤ 오른쪽 노드의 값중복된 값을 갖는 노드가 존재하지 않음이진 탐색 트리의 모든 서브 트리도 이진 탐색 트리따라서 BST는 부모 노드보다 작거나 같은 모든 원소는 항상 왼쪽에 있고, 부모 노드보다 크거나 같은 원소는 항상 오른쪽에 있다. 이를 그림으로 나타내면 다음과 같다. 　  　이러한 BST는 이름에 걸맞게 탐색 속도가 빠르다. BST는 높이에 따라 시간 복잡도가 결정되며, 이를 O(높이)로 표현할..