- 활동일시
- 일시 : 2022.10.10(월) 17:00 ~ 19:00 (2시간)
- 오늘의 계획
- 이진트리 구현
- IsFullBinaryTree()
- IsCompleteBinaryTree()
- IsBinarySearchTree()
- 오늘의 활동
Binary Search Tree (BST) 란?
- 정렬된 이진트리
- 노드의 왼쪽 하위 트리에는 루트노드의 키보다 작은 키의 노드만 존재
- 노드의 오른쪽 하위 트리에는 루트노드의 키보다 큰 키의 노드만 존재
- 왼쪽 및 오른쪽 하위트리 역시 각각 BST여야함.
- 중복된 키 허용 X 
- IsBinarySearchTree() : 현재 Tree의 모든 node들이 0 or 2개의 자식을 가지고 있는지 확인
-> 0 or 2면 True, 그렇지 않으면 False return
-
IsCompleteBinaryTree() : 마지막 level의 node들을 제외한 모든 node들은 꽉차있고, 마지막 level의 node는 왼쪽에서부터 채워져있음을 확인.
-> node들이 꽉 차있고, 마지막 level이 왼쪽에서부터 채워져있으면 True, 그렇지 않으면 False return.
-
IsBinarySearchTree() : 하나의 node를 기준으로 left value < node < right value 임을 확인.
(각각의 left subtree, right subtree 모두 FullBinarySearchTree이어야 함.)
-> 각각의 subtree들이 BinarySearchTree이면 True, 그렇지 않으면 False return
- IsFullBinaryTree, IsCompleteBinaryTree, IsBinarySearchTree를 확인하는 코드를 C++을 통해 작성해본다.
1) IsFullBinaryTree
IsFullBinaryTree의 경우 자식의 개수만 확인하면 된다. 그렇기 때문에 재귀로 왼쪽, 오른쪽을 돌면서 왼쪽과 오른쪽 자식이 두개 모두 Null이거나 두개 모두 어떠한 값이 있으면 True이다. Tree를 돌면서 어떠한 node라도 한쪽만 값이 있다면 False return 해준다.
2) IsCompleteBinaryTree
IsCompleteBinaryTree 확인 역시 재귀로 구현을 해 보았다. 마지막 level을 제외하고는 IsFullBinaryTree와 일치한다. 마지막 level을 위해 왼쪽에만 값이 있을때도 한번 더 재귀를 통해 검사해준다.
3) IsBinarySearchTree
IsBinarySearchTree의 경우 왼쪽과 root node의 값의 비교를 통해 BinarySearchTree인지 확인을 해야한다. 그렇기 때문에 재귀로 내려오면서 if문을 사용해 값 비교를 한다. 왼쪽이 root의 값보다 크거나, 오른쪽이 root의 값보다 작다면 False를 return, 그렇지 않은 경우는 재귀를 통해 계속 탐색을 진행한다.
- 활동 소감
이렇게 3개의 BinaryTree의 특징을 구현해보았다.
재귀를 잘 사용하지 못해 많이 어려웠지만, 같은 일을 계속 반복해나가고, 마지막 탈출 조건만 잘 설정해놓으면 되는 문제이다. 재귀함수를 사용한다면 함수를 보고 한번에 탈출조건을 확인할 수 있도록 가장 위에 적는 것이 좋은 것 같다.
