[데이터구조론/과제] Binary Search Tree (결과화면 캡쳐, 로직설명, 디스커션 포함)

소개

데이터구조 과제 중 Binary Search Tree에 대한 과제 결과물입니다.

BST는 트리 중 노드를 2개만 가질 수 있는 구조를 의미하는데요.
트리에 데이터를 넣고, 검색/삭제, 형제/부모찾기, 트리의 높이 구하기 등 각 동작마다 결과창을 캡쳐하였고, 각 결과창마다 디스커션을 달았습니다.

많은 도움이 되었으면 좋겠습니다.

목차

1. 삽입동작 ( i )
2. 트리 순회( p ) (Inorder 방식으로 함)
3. 데이터 검색 ( s )
4. 데이터 삭제 ( d )
5. 형제의 부모찾기 ( b )
6. 이진탐색트리의 높이 구하기 ( k )
7. 검토 및 소감

본문내용

삭제함수는 여러 가지 경우의 수들이 많은데, 이것들을 모두 체크해서 예외사항들을 모두 대비하였다. 먼저 삭제함수인 Del 함수에서 Search함수를 부르기 때문에 삭제할 노드는 p가, 그 부모는 parent 포인터변수가 각각 가리키게 된다. 크게 ROOT노드를 지울때와 그렇지 않을때로 나누었고, 각각은 3가지 경우로 또 나뉜다.

첫 번째는 지우려는 노드가 LEAF노드일 때이다. 이 때는 해당 노드를 삭제하고, 그 노드를 가리키는 부모의 링크를 NULL로 해주면 된다. 자식 노드가 하나인 노드를 삭제할 때는 해당 노드를 free시키고, 삭제된 노드의 자식을 삭제된 노드의 부모와 링크 시켜준다.

마지막으로 자식 노드가 두 개인 노드를 삭제할 때는, 왼쪽 서브트리의 가장 큰 값 또는 오른쪽 서브트리의 가장 작은 값을 올려주면 된다. 이 코드에서는 왼쪽 서브트리의 가장 큰 값을 삭제할 노드의 위치에 복사시킨 후 링크들을 재설정해 주었다.

참고자료

· 없음