[Swift] 자료구조 - 이진 탐색 트리 ( Binary Search Tree )

안녕하세요~

 

오늘은 지난 포스팅(해시 테이블)에 이어서 이진 탐색 트리에 대해서 알아보려고 합니다 : )

 

[ 해시 테이블 포스팅 ]

[Swift] 자료구조 - 해시 테이블(Hash Table)

 

 

---

 

 

일단, 트리부터 알아보겠습니다.

 

1. 트리란

트리

 

노드와 간선을 이용해 사이클을 이루지 않도록 만든 데이터 구조를 말합니다. 

 

연결 리스트의 경우

선형으로 Prev와 Next를 통해 앞, 뒤의 주소를 가지고 있었지만

 

트리의 경우

왼쪽과 오른쪽에 자식(child)이라고 하는 노드를 가지고 있는

비선형 구조의 자료구조입니다.

 

또, 사이클을 이루지 않고 있는데 ( J ↔️ K )가 불가능하기 때문에

( F ↔️ J ↔️ K ) 이런 식으로 순회가 불가능하다는 뜻입니다.

 

용어설명

1.  루트 노드(Root Node) : 트리의 근간이 되는 노드입니다. 즉, 최상위에 있는 노드를 말합니다.

2. 부모 노드(Parent Node) :특정한 노드의 상위 노드를 부모 노드라고 부릅니다. 위에서 B의 경우 E와 F의 부모 노드가 되는 것이죠.

3. 자식 노드(Child Node) : 특정한 노드의 하위 노드들을 말합니다. 물론 자신이 가리키고 있는 노드입니다.

4. 레벨 ( Level ) : 노드의 깊이, 루트 노드의 레벨은 0이고 이를 기준으로 레벨이 1씩 증가합니다.

5. 리프 노드 ( Leaf Node ) : 자식 노드가 하나도 없는 노드를 말합니다. 이미지에서는 E, J, K, L, H, I가 해당됩니다.

6. 트리의 깊이 ( Depth ) : 최대 레벨의 값으로 위에서는 3이 되겠네요.

 

2. 이진트리란?

자식 노드의 개수가 몇 개든 상관없이 가질 수 있으며 이때 자식노드를 최대 두 개만 가지고 있는 트리를 이진트리라고 부릅니다. 위의 이미지에 있는 트리도 이진트리가 되겠네요.

 

3. 이진 탐색 트리란?

탐색을 국어사전에 검색해 보면 "사물이나 현상을 밝히기 위해 찾음"이라고 나와있는데

말 그대로 원하는 것을 찾는 행위를 말합니다.

 

원하는 것을 찾기 위해서는 여러 방법이 있지만 가장 쉬운 것 중 하나가 비교해 보는 것입니다.

내가 찾고자 하는 값이 10이라면

다른 값들과 비교해 큰지 작은지 확인해 나가면 결국 찾게 되는 것이죠.

 

이진 탐색 트리에서는 특정한 조건을 갖추고 있습니다.

1. 모든 노드가 자신의 왼쪽 자식 노드에서는 자신보다 작은 값이 와야 하고 자신의 오른쪽 자식 노드에는 자신보다 큰 값이 와야 합니다.
2. 노드의 값은 유일해야 한다. 중복이 불가능.
3. 노드의 값은 항상 존재해야 한다.

위의 3가지 규칙을 준수하고 있다면 이진 탐색 트리라고 합니다.

 

이해에 도움이 될 수 있게 애니메이션을 하나 가지고 와봤습니다.

 

 

이진 탐색 트리

 

 

4. 이진 탐색 트리 구현

첫 번째, 노드(Node) 클래스

// 제네릭을 Comparable로 설정한 것은
// 위에서 말한 것처럼 두 값을 비교할 수 있어야 
// 위치를 정할 수 있기 때문!
class Node<T: Comparable> {
    var data: T
    // 자식 노드가 있을 수도 없을 수도 있으니 옵셔널!
    var left: Node? 
    var right: Node?
    
    init(data: T) {
    	self.data = data
    }
}

두 번째, 이진 탐색 트리(BST) 클래스

class BinarySearchTree<T: Comparable> {
	// 시작 노드이자 최상위 노드!
	var root: Node<T>?
}

세 번째, 데이터 추가, 검색, 삭제

가장 먼저 추가에 대해서 알아보겠습니다.

데이터를 넣으려면 알아야 하는 것이 뭘까요? 바로 위치입니다.

따라서 탐색을 진행하고 원하는 위치를 발견했다면 데이터를 추가하면 됩니다.

func insert(data: T) {
    // 만약 루트 노드가 없다면?
    // 바로 들어온 노드가 루트 노드가 되야겠죠? 👀
	guard let root = self.root else {
	    return self.root = Node.init(data: data)
    }
	
    var onNode = root // 루트 노드를 받아오기, 바로 시작할 위치이기 때문입니다.
    // 탐색 및 추가
    while true {
	    // 들어온 데이터가 현재 노드보다 작은 경우
    	if onNode.data > data {
        	// 작으면 왼쪽
        	guard let nextNode = onNode.left else {
                // 왼쪽 노드가 비어있다면 노드를 그 자리에 추가해주기
            	return onNode.left = Node.init(data: data)
            }
            // 비어있지 않다면 현재 탐색의 중심인 노드를 nextNode로 바꾸고 다시 while문
            onNode = nexNode
        } else {
        	// 위랑 반대
        	guard let nextNode = onNode.right esle {
            	return onNode.right = Node.init(data: data)
            }
            onNode = nextNode
        }
    }
}

다음으로 탐색을 알아보죠.

// 해당 값의 레벨과 존재하는지 반환하는 함수를 만들어보겠습니다
func search(data: T) -> (Int?, Bool?) {
	// 만약에 루트가 nil이면 당연히 탐색할 것이 없습니다.
	if root = nil { return (nil,nil) }
    
    var onNode = root // 루트부터 시작
    var level = 0 // 루트의 레벨은 0
    while let node = onNode {
	    // 해당되는 데이터를 찾았다면 레벨과 true 반환
    	if node.data == data {
			return (level,true)
		}
        
        // 탐색했을 때와 마찬가지로 
        // 찾고자하는 데이터의 값이 더 작으면 왼쪽에 있다는 것이므로 왼쪽으로 계속 이동
        if node.data > data {
			onNode = node.left
		} else {
     		onNode = node.right   
        }
        // 왼쪽으로 내려가든 오른쪽으로 내려가든 level은 1씩 증가
        level += 1
    }
    return (nil,false)
}

마지막으로 삭제를 구현해 봅시다.

 

삭제 시에는 3가지 경우의 수가 존재합니다.

 

1. 자식 노드가 없는 노드를 제거

2. 자식 노드가 하나만 있는 노드를 제거

3. 자식 노드가 두 개인 노드를 제거

자식 노드가 없는 노드를 제거

// 삭제가 완료되었는지 확인하기 위해 Bool 타입으로 반환
func remove(data: T) -> Bool {
	// 루트를 찾을 수 없다면 false
    guard let root = self.root else { return false }
    // 루트노드부터 시작
    var parentNode = root
    var onNode: Node? = root
    
    // 삭제할 노드를 찾기
    while let node = onNode {
    	// 기존의 탐색처럼 두 값을 비교하면서 찾기!
        if node.data == data { break }
        if node.data > data {
            onNode = node.left
        } else {
            onNode = node.right
        }
        // 왼쪽 혹은 오른쪽으로 내려가 해당 노드를 부모 노드로 두고 다시 비교
        parentNode = node 
    }
    // 찾기 성공
    guard let deleteNode = onNode else {  
	    // 찾기 실패
        return false
    }
    // 자식 노드가 모두 없다면 ( 삭제하려는 노드의 ) 찾은 상태
    // 따라서 제거
    // 이때, 제거하려는 노드의 부모노드의 왼쪽인지 오른쪽인지 확인하고 연결을 끊어준다(nil)
    if deleteNode.left == nil && deleteNode.right == nil {
        if parentNode.data > data {
            parentNode.left = nil
        } else {
            parentNode.right = nil
        }
        return true
    }
}

자식 노드가 하나만 있는 노드를 제거

탐색하는 방법은 같지만 조건이 달라집니다.

// 제거하려는 노드의 왼쪽 자식 노드가 존재할 경우
if (deleteNode.left != nil) && (deleteNode.right == nil) { 
    if parentNode.data > data {
    	// 부모노드와 값을 비교하고 부모노드가 값이 크다면
        // 부모노드의 왼쪽에 제거하려는 노드의 왼쪽 노드를 연결 
        parentNode.left = deleteNode.left
    } else {
	    // 위와 반
        parentNode.right = deleteNode.left
    }
    return true
}
// 제거하려는 노드의 오른쪽 자식 노드가 존재할 경우
if (deleteNode.left == nil) && (deleteNode.right != nil) { 
    if parentNode.data > data {
    	// 부모노드와 값을 비교하고 부모노드가 값이 크다면
        // 부모노드의 왼쪽에 제거하려는 노드의 오른쪽 노드를 연결 
        parentNode.left = deleteNode.right
    } else {
        parentNode.right = deleteNode.right
    }
    return true
}

자식 노드가 두 개인 노드를 제거

하단에 소들님 블로그가 정말 잘 정리되어 있고 저도 참고해서 정리했으니 꼭 보시길 바랍니다.

 

방법

1. 오른쪽 자식 노드에서 가장 작은 값을 찾아 제거하려는 노드의 위치로 옮겨주는 방법

2. 왼쪽 자식 노드에서 가장 큰 값을 찾아 제거하려는 노드의 위치로 옮겨주는 방법

 

해당 코드는 첫 번째 방법을 기준으로 하고 있습니다.

// 제거하고자하는 노드의 오른쪽 자식 노드가 존재
guard let rightNode = deleteNode.right else { return false }
 
// 탐색을 위한 변수 세팅 
var currentNode = rightNode
var currentParentNode = rightNode

// 탐색을 통해 가장 작은 값을 찾는 루프 ( 계속 왼쪽으로 내려가기 )
while let nextNode = currentNode.left {
    currentParentNode = currentNode
    currentNode = nextNode
}

// 만약에 현재 노드(가장 작은 값을 가진)의 오른쪽 노드가 존재할 경우 기존의 부모노드와 연결
if let currenteChildNode = currentNode.right {
    currentParentNode.left = currentChildNode
// 없기 때문에 부모 노드의 왼쪽 ( 기존의 자신 )을 nil 해주기
} else {
    currentParentNode.left = nil
}

if parentNode.data > data {
    parentNode.left = currentNode
} else {
    parentNode.right = currentNode
}
 
currentNode.left = deleteNode.left
currentNode.right = deleteNode.right

return true

 

사용한 트리 이미지와 이진 탐색 트리 gif의  출처 그리고 참고한 블로그입니다 : - )

감사합니다 👏 👏 👏

 

자료구조 - 트리(Tree)란

5 Gifs to Understand Binary Search Trees

Swift) 이진 탐색 트리(BST) 구현 해보기 (1/2)