원글 페이지 : 바로가기
오늘은 저번에 공부 했던 힙과 마찬가지로 트리 구조 중 하나인 이진 탐색 트리에 대해 공부해 보겠다. 현재 차근차근 해보자는 생각에 기초적인 부분을 공부하고 있다. 좀 더 구체적인 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 해보겠다. 틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다. 📌 개념 이진 탐색 트리(Binary Search Tree)는 그래프의 트리 구조로 각 노드에 데이터가 저장된다. 이진 탐색 트리 예 이진 탐색 트리의 예시 이다. 각 노드에 쓰인 숫자가 데이터 이다. 이진 탐색 트리에는 두가지 특징이 있다. 첫번쩨, 각 노드의 값은 왼쪽 가지에 있는 노드들의 값보다 크다는 특징이 있다. 특징 첫번쨰 예시를 보면 노드 9는 왼쪽 가지에 있는 값보다 크다. 두번째, 각 노드의 값은 오른쪽 가지에 있는 노드들의 값보다 작다는 특징이 있다. 특징 두번째 예시에 보면 노드 15는 오른쪽 가지에 있는 노드들 보다 값이 작다. 최솟값/최댓값 찾기 이진 탐색 트리의 특징을 통해 다음 조건이 성립된다. 최솟값 찾기 이진 탐색 트리의 최솟값은 제일 위에 있는 노드(root)에서 가장 왼쪽에 있는 노드이다. 여기서는 최솟값 3인것을 확인 할 수 있다. 최대값 찾기 반대로 최대값은 제일 위에 있는 노드(root)에서 가장 오른쪽에 있는 노드다. 28이 가장 큰 값인 것 확인 할 수 있다. 데이터 추가 데이터 추가 1을 추가해 보겠다. 데이터 추가 이진 탐색 트리의 최상위 노드(root)에서 부터 추가할 위치를 찾기 시작한다. 추가하려는 값 1과 현재 노드의 값을 비교해서 작으면 왼쪽으로, 크면 오른쪽으로 진행한다. 1 < 15 이기 때문에 왼쪽으로 이동한다 데이터 추가 1 < 9 이기 때문에 왼쪽으로 진행한다. 데이터 추가 1 > 3이기 때문에 왼쪽으로 진행한다. 더 이상 비교할 노드가 없기 때문에 해당 위치에 새로운 데이터를 추가 한다. 데이터 추가 이렇게 1을 추가 했다. 데이터 추가 다음으로 4를 추가해 보겠다. 1을 추가할 때와 마찬가지로 root 노드에서 비교해 가면서 진행한다. 데이터 추가 4 < 15 이기 때문에 왼쪽으로 진행한다. 데이터 추가 4 < 9 이기 때문에 역시 왼쪽으로 진행한다. 데이터 추가 이번엔 4 > 3이기 때문에 오른쪽으로 진행한다. 데이터 추가 마지막으로 4 < 8 이기 때문에 왼쪽으로 진행하는데, 노드가 없기 때문에 새로운 노드를 추가한다. 데이터 추가 이렇게 4도 추가를 완료했다. 데이터 삭제 이번엔 데이터 삭제를 해보겠다. 데이터 삭제 28을 삭제해 보겠다. 데이터 삭제 삭제 케이스 첫번째인 자식 노드가 없는 경우이다. 해당 경우는 그냥 자신 노드만 삭제하면 된다. 데이터 삭제 두번째 경우는 자식 노드가 하나 있을 경우 이다. 이 경우를 알아보기 위해 8을 삭제해 보겠다. 데이터 삭제 이때는 먼저 해당 노드를 삭제한 뒤 데이터 삭제 자식 노드를 부모 노드 위치로 옮기면 된다. 데이터 삭제 마지막 경우인 자식 노드가 두개 다 있는 경우이다. 이 경우는 9를 지우면서 알아보겠다. 데이터 삭제 해당 경우는 먼저 해당 노드를 삭제한 하고 삭제한 노드의 왼쪽이나 오른쪽에서 최댓값을 가진 노드를 찾은 뒤, 여기선 왼쪽 노드에서 찾아 4가 최댓값이다. 데이터 삭제 삭제한 노드의 위치로 옮겨주면 된다. 그러면 이진 탐색 트리의 두 가지 조건을 만족하면서 노드를 삭제할 수 있다. 이동하게 된 노드(여기선 4)에 자식 노드가 있는 경우에는 같은 작업을 재귀적으로 반복해야 한다. ※ 재귀 알고리즘은 추후에 알고리즘 공부하면서 다뤄 보겠다. 데이터 탐색 이번에는 이진 탐색 트리에서 값을 찾는 과정에 대해 알아보겠다. 데이터 탐색 12라는 값을 찾아보겠다. 데이터 탐색 항상 root 노드부터 찾기 시작한다. 추가할 때와 마찬가지로 찾고자하는 데이터와 현재 노드를 비교하여 작으면 왼쪽, 크면 오른쪽으로 진행한다. 12 < 15이므로 왼쪽으로 진행한다. 데이터 탐색 12 > 4이기 때문에 오른쪽으로 진행한다. 데이터 탐색 찾고자하는 데이터 12를 발견했다. 이렇게 이진 트리 탐색은 효율적으로 원하는 것을 탐색해 삽입, 삭제, 탐색을 가능하게 한다. 하지만 데이터가 너무 많아 높이가 커지거나 데이터가 불균형하게 한쪽에 몰려있는 형식이라면 검색 효율아 불균형할 수 있다. ⏱️ 시간복잡도 이진 탐색 트리는 데이터를 찾거나 추가할 때, 현재 위치의 데이터와 크기를 비교하여 왼쪽 혹은 오른쪽으로 진행하면서 노드의 위치를 찾는다. 비교 연산은 트리의 높이만큼 수행하게 된다. 따라서 노드 n개가 균형 있게 배치되어 있다면 최대 log₂n번 비교하므로, 계산 시간은 O(log n)이 된다. 하지만 트리가 한쪽으로 치우쳐져 세로로 늘어선 모양이 되면 높이가 높아지므로, 계산 시간은 O(n)이 된다. 📌 추가 내용 이진 탐색 트리를 확장한 데이터 구조도 있다. 예를 들어 트리가 한쪽으로 치우치면 형태를 수정하여 항상 균형을 유지하는 것도 있다. 이렇게 검색 효율을 높인 것을 균형 이진 탐색 트리라고 한다. 균형 탐색 이진 트리 또한, 앞서 설명한 이진 탐색 트리의 경우 각 노드의 자식 노드가 최대 두개 였는데, 이를 m개로 확장하고 자식 노드 수에 자유도를 부여하여 트리의 균형을 맞춘 B 트리라는 것도 있다. B-트리 참고 자료 그림으로 이해하는 알고리즘 : 이시다 모리테루, 미야자키 슈이츠 이미지 출처 균형 이진 탐색 트리 https://velog.io/@dnrwhddk1/%EA%B7%A0%ED%98%95-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC%EC%97%90-%EB%8C%80%ED%95%B4-%EC%9E%90%EC%84%B8%ED%9E%88-%EC%95%8C%EC%95%84%EB%B3%B4%EA%B8%B0-%EB%B9%84%EC%84%A0%ED%98%95-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0 B 트리 https://velog.io/@chanyoung1998/B%ED%8A%B8%EB%A6%AC