26. BST (Binary Search Tree, 이진탐색트리) 알고리즘

1. 개요

 BST 알고리즘은 쉬움.

 부모 노드를 기준으로 좌측엔 부모 노드보다 작은 데이터, 우측엔 부모 노드보다 큰 데이터 삽입. (반드시 만족해야 함)

 가장 오른쪽 노드의 데이터가 최대 크기.

 가장 왼쪽 노드의 데이터가 최소 크기. 

 이진 탐색 트리를 중위 순행하면 정렬 리스트를 생성할 수 있음. (작은->중간->큰 순으로 운행)

 BST는 삽입, 삭제, 데이터 검색, 최소 데이터 검색, 최대 데이터 검색 5가지 기본 연산 존재.

 모든 검색은 O(n)에 움직임.

 왜냐하면 BST의 좌,우측 트리 높이 차이는 0~n까지 있을 수 있기 때문에 O(n)이 된다.

 이를 균형 맞추기 위해 나타난 트리가 Balanced BST이다. 대표적으로 AVL Tree가 있다.

 AVL Tree는 좌,우측 트리 높이 차이가 1이하이다. 즉, 최대 높이가 BST보다 반으로 줄기에 검색 시간 O(logn).

 BST에 응용 가능한 수 많은 알고리즘들이 존재.

 기억해야 할 것

 삭제 알고리즘

 (1) Leaf 노드 (자식 노드가 없는 경우) 삭제할 때

 (2) Half 노드 (자식 노드가 하나만 있는 경우) 삭제할 때

 (3) Full 노드 (자식 노드가 두 개 있을 경우) 삭제할 때

 경우를 잘 생각하고 처리해야 한다. 이게 BST의 전부.

2. 문제

 데이터 10, 100, 500 범위 안에서 랜덤으로 데이터를 입력받고 이를 BST에 삽입했다 삭제하는 알고리즘 작성하시오.

3. 출력

3-1) 구조체 및 함수 선언

3-2) 메인

3-3) BST 삽입 알고리즘

3-4) BST 삭제 알고리즘

3-5) 검색, 최소, 최대 구하기 알고리즘

3-6) 데이터 크기 10,100,500에 따른 출력 (데이터는 범위 안에서 랜덤 삽입함)

4. 정리

 이번 BST는 정말 하루만에 뚝딱 올리고 싶었지만 예기치 않은 문제로 인해서 일주일이나 걸려버렸다.

 왜냐하면 원래 내가 알고있는 방식으로 풀었다면 바로 올릴 수 있었겠지만 그에 따른 코드양이 너무 많았다.

 그래서 기존에 배운 방식이 아닌 스승님이 제시해 준 이 방식으로 풀어보고 싶었다. 하지만 스승님은 역시나

 완성된 코드가 아닌 슈도 코드만 올려놓으셨고 이거 분석하고 코드량을 대폭 줄이기 위해 연구하느라 시간이

 오래 걸렸다. 그 와중에 리켜전에 대해 새로운 느낌을 잡았으니 만족한다. 이해가 되지 않던 것들을 하나씩

 부서나갈 때마다 성장하는게 느껴진다. 좋다.

 기억해야 할 것.

 내가 알던 낡은 방법은 삭제 노드를 찾으면 바로 그에 따른 처리를 한다.

 새로운 방법은 삭제 노드를 찾으면 데이터 갱신만 하고 다시 중복된 갱신 데이터를 삭제하도록 한다. (속도도 괜찮다.)