안녕하세요! 소들입니다 :)
오늘은 자료구조이기도 하고.. 알고리즘이기도 한.. (아리송)
트리에 대해 공부해볼 거예요!!! 그 중에 이진 탐색 트리에 대해 다뤄보려고 합니다!!
음.. 지금껏 공부해왔던 것 중에서.. (뭐 별로 한 것도 없지만)
그래도 트리는 난이도가 꽤 있는 편에 속해요!!
어려울 수도 있지만 차근차근 공부해봅시다 :))
그럼 고고씽
모든 포스팅은 편의 말투로 합니다~!!
1. 트리가 무엇일까?
자, 먼저 트리(Tree)라는 것은
🎄
쨔쟌..ㅎ
다들 코로나때매 못 본 트리보셈~~
헛소리 집어 치우고 다시 트리란,
Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
늘 그렇지만 정의만 보면 도대체 이게 뭔소리일까;;;
자, 근데 여기서 우리는 Node라는 단어를 앎..! 언제 알아봤냐면, 연결 리스트할 때 알아봤거든
여기서 한 가지 유추가 가능함..! 트리는 아직 뭔지 모르겠지만 연결 리스트로 구현할 수 있겠구나..!
(물론 노드라고 해도 배열로 구현하는 Heap이 있긴 함!)
먼저, 노드가 무엇인지 연결리스트에서 배운 것을 생각해보셈
노드란 내 데이터 + 다음 데이터의 주소값을 갖고 있는 형태였음
(단방향일 경우 next만, 양방향일 경우 prev, next 둘 다 가졌음)
트리도 마찬가지임!
트리 또한 내 데이터 + 다음 데이터의 주소값을 갖는 형태이지만,
여기서 중요한 건 트리는 데이터들 간 연결 고리의 모양이 좀 다름
이런 식으로 노드들이 계층을 가지고 구성이 됨!!!!
따라서 연결 리스트의 prev, next 같은 선형구조(순차적으로 나열된 구조)가 아닌,
최상위 노드(20)를 기준으로 노드들이 왼쪽, 오른쪽에 "자식"으로 배치되는 비선형 구조임
그래서 이름이 트리인 것임!! 마치 나무같지 않음?? 노드들이 나뭇가지(branch)를 통해 뻗어 나가듯!
이때 내 자식 노드들(왼쪽, 오른쪽)을 가리키는 선이 바로 branch(혹은 Edge)임!
그렇다면 트리에선 다음 주소값이, 내 자식 노드들의 주소값을 가리키겠구나! 라고 생각할 수 있겠지 :)
근데 이 branch는 아래로만 뻗어서,
다음과 같이 트리의 branch가 삼각형이 될 일은 없음
이렇게 제멋대로 뻗어서 순환될 일이 없으니 안심하란 것임
그렇기 때문에 트리의 정의에서 노드들이 사이클을 이루지 않도록 구성한다
라는 말이 나온 것
1-1. 트리에서 사용하는 용어
트리를 공부하기 전에, 헷갈리기 쉬운 용어부터 정립하고 가겠움!
◦ Node : 트리에서 데이터를 구성하고 있는 각 요소 (데이터 및 Branch 정보도 포함)
◦Root Node : 트리의 최상위에 있는 노드
◦Level : 노드의 깊이
◦Parent Node : 어떤 노드의 다음 레벨에 연결된 노드
◦ Child Node : 어떤 노드의 이전 레벨에 연결된 노드
◦ Leaf Node (Terminal Node) : Child Node가 하나도 없는 노드
◦Depth : 트리에서 Node가 가질 수 있는 최대 Level
어려운 것 없을 거라 생각함 :)
Parent Node와 Child Node가 정의로 보면 헷갈릴 수 있는데..!
그냥 나를 가리키는 내 윗 레벨 Node는 내 Parent Node이고,
내가 가리키는 다음 레벨 노드는 내 Child Node임!
여기까지 공부하고 다시 트리의 정의를 보면, 무슨 말인지 이해가 갈 것임!
이제 트리가 무엇인지 알았다!!!! 👀
2. 이진 트리 vs 이진 탐색 트리
가끔 공부할 때 열받는 거... 이름이 조금씩 달라서 헷갈릴 때......
하지만 이진 트리와 이진 탐색트리는 처음엔 헷갈릴 수 있지만,
전혀 혼동할만한 개념이 아님
2-1. 이진 트리란?
위에서 공부한 트리의 내용은 이진트리를 기반으로 설명했는데,
사실 트리를 구성하는 노드의 branch 갯수는 다음과 같이
여러 개가 될 수 있음
자식 노드가 아예 없을 수도 있고, 2개둘 수 있고, 3개도 둘 수 있음!!!!
근데!!!!!! 이진 트리란
branch가 최대 2개인 노드로만 구성되는 트리
를 말함!!!
따라서 다음과 같이 branch의 갯수가 0~2개로 생긴 노드들이
모여서 만든 트리는 모두 이진 트리임!!!
만약 branch가 3개 있는 노드가 하나라도 있을 경우, 그 트리는 이진 트리가 아님
2-2. 이진 탐색 트리
그렇다면 이진 탐색트리는 무엇이냐?
이진트리에 조건이 붙은 것임
모든 노드가
자신의 왼쪽 Child Node엔 자신보다 작은 값이,
자신의 오른쪽 Child Node엔 자신보다 큰 값이 오는 규칙을 만족하는 "이진 트리"
를 말함!!! 근데 여기에
노드의 데이터 값은 유일하다 (중복되지 않음)
노드의 데이터 값은 항상 존재한다(nil이면 안됨)
라는 조건도 덧붙어야 됨 ㅎㅎㅎㅎ
이렇게 그림으로 보면 쉽지 않음 ? :)
이진 탐색 트리를 Binary Search Tree 라고 부르는데,
보통 줄임말로 BST 라고 부름!!! 마치 BTS 같군....
.
.
자, 정리를 해봅시다..!!!
이진 트리란 branch가 최대 2개인 노드로만 구성된 트리를 말하고,
이진 트리에서 특정 조건을 만족하는 트리를 이진 탐색 트리라고 한다!!
그럼 Swift로 구현을 해봅시다 :)
3. 이진 탐색 트리 구현
앞서 말했듯 이진 탐색 트리는 연결 리스트로 구현할 것임!!!!
(배열로도 불가능한 것은 아니지만 BST에선 매우 비효율적)
3-1. Node 클래스를 생성하자
먼저, 이진 탐색 트리는 자신의 왼쪽, 오른쪽에 branch를 두니,
Node 클래스를 다음과 같이 구성하면 될 것 같음!
|
class Node<T: Comparable> {
var data: T
var left: Node?
var right: Node?
init(data: T) {
self.data = data
}
}
|
이진 탐색 트리 자체가 데이터를 비교해가면서 탐색을 하기 때문에,
비교가 가능한 데이터만 저장할 수 있게 Comparable 프로토콜을 채택한 제네릭으로 선언했음!
또한, 데이터는 항상 존재해야 하므로 Non-Optional Type임!
트리의 왼쪽, 오른쪽 Child Node는 존재할 수도, 안 할 수도 있으니 Optional Type임!
3-2. 이진 탐색 트리 클래스를 만들자
이제 이 Node를 이용해 이진 탐색 트리를 만들어주는
BinarySearchTree 라는 클래스를 만들어보겠음!
그리고 최상위 노드인 Root Node를 가리킬 root라는 프로퍼티도 하나 추가해주겠음!
|
class BinarySearchTree<T: Comparable> {
var root: Node<T>? }
|
이제 이 클래스에 insert, search, remove 함수를 추가해보겠음 :)
ⓛ insert(_:) : 데이터 삽입하기
위에서 이진 탐색 트리에 대해 제대로 이해를 했다면,
삽입을 한다는 것은 내가 삽입하려는 위치까지 탐색을 해야 한단 것을 알 수 있음
먼저, root가 있는지 확인해주고, root가 있으면 root 노드부터 탐색을 하는 것임
(현재 노드가 내 데이터보다 크면 왼쪽으로, 작으면 오른쪽으로 가면서 내 위치를 찾는 것)
|
func insert(_ data: T) {
guard let root = self.root else {
return self.root = Node.init(data: data)
}
var currentNode = root
while true {
if currentNode.data > data {
guard let nextNode = currentNode.left else {
return currentNode.left = Node.init(data: data)
}
currentNode = nextNode
} else {
guard let nextNode = currentNode.right else {
return currentNode.right = Node.init(data: data)
}
currentNode = nextNode
}
}
}
|
음.. 저는 이렇게 구현해봤는데..!
노드의 left, right가 모두 nil을 지닐 수 있는 옵셔널 타입이어야 해서;;
옵셔널 체이닝이나 옵셔널 강제 해제 연산을 최대한 피해보려고 하니 코드가 좀 복잡해보이는 것 같음
혹은 재귀함수를 이용하면 더 간단하게 구현할 수도 있는데
아직 재귀함수 포스팅 전이니(사용법은 알지만) 정석적인 방식으로 구현해봤음!
실제 이진탐색트리를 만들고 삽입을 한 후,
다이어그램을 만들어주는 함수로 출력해 보면!!
잘 들어가있음....!!
이 다이어그램 함수 만들어주는 코드는 마지막에 출처랑 같이 남겨 놓겠음!
② search(from:) : 데이터 검색하기
이번엔, 내가 찾는 데이터가 이진 탐색 트리 안에 존재하는지 아닌지를
판별해서 Bool 값으로 리턴해주는 함수를 만들어보겠음..!
이또한 insert와 비슷하게
현재 노드와 내가 찾고자하는 노드의 데이터를 비교해가며 탐색을 진행하는 것임!
|
func search(from data: T) -> Bool {
if root == nil { return false }
var currentNode = root
while let node = currentNode {
if node.data == data {
return true
}
if node.data > data {
currentNode = node.left
} else {
currentNode = node.right
}
}
return false
}
|
옵셔널 바인딩을 위해 while let을 사용 했구여...!
Swift로 구현하다 보니 옵셔널 신경쓰는게 빡세네여..;;
아까 insert 했던 요소들로 테스트 해보몀ㄴ
쨔쟌 잘 됨!!!!!!
.
.
.
일단 이진 탐색 트리에 대한 기본 구조와
insert & search에 대해서 다뤄봤음!!!
아직 하나 남은 remove는 내용이 어렵....기 때문에... 길어질거 같아서~
2탄에서 마저 쓰겠음~~~ +이진 탐색 트리의 시간복잡도 또한!!!
혹시 틀렸거나 피드백할 내용, 궁금증은 언제나 댓글 주세요!!!
전체 코드는 2편에서 삭제 다룬 후 넣어둘게요~~!
+ 이진 탐색 트리 다이어그램
(draw 함수는 개별로 추가함)
|
func drawDiagram() {
print(diagram(for: self.root))
}
private func diagram(for node: Node<T>?,
_ top: String = "",
_ root: String = "",
_ bottom: String = "") -> String {
guard let node = node else {
return root + "nil\n"
}
if node.left == nil && node.right == nil {
return root + "\(node.data)\n"
}
return diagram(for: node.right, top + " ", top + "┌──", top + "│ ")
+ root + "\(node.data)\n"
+ diagram(for: node.left, bottom + "│ ", bottom + "└──", bottom + " ")
}
|
다이어그램 코드 출처 :
devmjun.github.io/archive/BinarySearchTree
이진탐색트리 귀여운 짤 출처
blog.penjee.com/5-gifs-to-understand-binary-search-tree/#binary-search-tree-insertion-node)
'Algorithm > 자료구조' 카테고리의 다른 글
| Swift) 그래프(Graph) 이해하기 (6) | 2021.01.20 |
|---|---|
| Swift) 이진 탐색 트리(BST) 구현 해보기 (2/2) (4) | 2021.01.08 |
| Swift) 해시 테이블(Hash Table) 이해하기 (12) | 2021.01.05 |
| Swift) 양방향 연결 리스트(Doubly LinkedList) 구현 해보기 (5) | 2021.01.04 |
| Swift) 단방향 연결 리스트(LinkedList) 구현 해보기 (6) | 2020.12.29 |
