[트리의 종류들]

2021.05.08 - [Tech.log/자료구조] - [자료구조의 형태]

[자료구조의 형태]

자료구조란 ? 컴퓨터에서 사용할 자료를 더 효율 적으로 관리하기 위해서 자료의 특성과 사용 용도에 따라 분류하고 구조화 한것이다. 1. 단순 자료 구조 컴퓨터 프로그래밍에서 쓰이는 데이터

itfordoit.tistory.com

트리란

그래프의 일부이지만 사이클이 없는 계층적 구조이다. 트리에는 여러가지 종류가 있는데 살펴보자.

이진트리

각각의 노드가 최대 두 개의 자식 노드를 가지는트리 자료구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.

정 이진 트리(Full Binary Tree)

모든 레벨에서 노드들이 꽉 채워진 자식노드 2개를 가지고 있는 이진트리다.

완전 이진트리(Complete Binary Tree)

"이진 트리"중 노드가 왼쪽부터 차례대로 채워져 있는 트리를 말한다.

이진 탐색 트리(Binary Search Tree)

이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조

이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐습니다.

이진 탐색은 탐색의 소요되는 시간 복잡도는 O(logn)이지만, 자료의 입력과 삭제가 어렵다.
연결 리스트의 경우 자료 삽입,삭제의 시간복잡도는 O(1)이지만, 탐색이 O(n)이다.

이 둘을 합친 것이 이진 탐색 트리이다.

이진탐색트리의 특징

각 노드의 왼쪽 서브 트리에는 해당 노드 보다 작은 값으로 이루어져 있다.
각 노드의 오른쪽 서브 트리에는 해당 노드보다 큰 값으로 이루어져있다.
중복된 노드가 없다.

이진탐색트리의 탐색

이진탐색트리를 순회할 때는 중위순회(inorder) 방식을 사용한다.(왼=>현재노드=>오른쪽 )

이진탐색트리의 연산

탐색

만일 10을 탐색한다고 했을때,
1. 7와 10 비교 =>오른쪽
2.8과 10비교 =>오른쪽
3.종료

따라서 탐색 시에 소요되는 최대 복잡성은 트리의 높이인 h O(h)가 된다.

파이썬 코드

  def find(self, val):
        if (self.findNode(self.root, val) is False):
            return False
        else:
            return True

    def findNode(self, currentNode, val):
        if (currentNode is None):
            return False
        elif (val == currentNode.val):
            return currentNode
        elif (val < currentNode.val):
            return self.findNode(currentNode.leftChild, val)
        else:
            return self.findNode(currentNode.rightChild, val)

삽입

4를 추가한다.

1. 7와 4비교 =>왼

2.3과 4비교 =>오른쪽

3.4와5비교 =>왼쪽

4. 추가

따라서 삽입 시에 소요되는 최대 복잡성은 트리의 높이(h)인 O(h)가 된다.

def insert(self, val):
        if (self.root is None):
            self.setRoot(val)
        else:
            self.insertNode(self.root, val)

    def insertNode(self, currentNode, val):
        if (val <= currentNode.val):
            if (currentNode.leftChild):
                self.insertNode(currentNode.leftChild, val)
            else:
                currentNode.leftChild = Node(val)
        elif (val > currentNode.val):
            if (currentNode.rightChild):
                self.insertNode(currentNode.rightChild, val)
            else:
                currentNode.rightChild = Node(val)

삭제

삭제는 여러가지 상황이 있다. 하나 씩 따져보자.

자식노드가 없는 경우

4를 제거하려는 경우
그냥 없애면 된다

자식 노드가 하나 있는 경우

20을 지우고 싶은 경우
해당 노드를 지우고 자식 노드와 연결하면 된다.

자식 노드가 두개 있는 경우

16을 지우고 싶은 경우

16의 왼쪽 서브트리에 속한 모든 값은 16보다 작고, 오른쪽 서브트리에 속한 모든 값은 16보다 큰 것을 확인할 수 있습니다.
특히 13을 predecessor(삭제 대상 노드의 왼쪽 서브트리 가운데 최대값), 20을 successor(삭제 대상 노드의 오른쪽 서브트리 가운데 최소값)라고 한다.

따라서 아래와 같이 삭제할 노드인 16 위치에 20을 복사해 놓고, 기존 20 위치에 있던 노드를 삭제하게 되면 정렬된 순서를 유지(=이진탐색트리 속성을 만족)할수있다.

삭제 대상 노드의 오른쪽 서브트리를 찾는다.

successor(1에서 찾은 서브트리의 최소값) 노드를 찾는다.

2에서 찾은 successor의 값을 삭제 대상 노드에 복사한다.

successor 노드를 삭제한다.

트리의 높이가 $h$ 이고 삭제대상 노드의 레벨이 $d$ 라고 가정했을때 , 1번 과정에서는 $d$ 번의 비교 연산이 필요합니다. 2번 successor 노드를 찾기 위해서는 삭제 대상 노드의 서브트리 높이( $h - d$ )에 해당하는 비교 연산을 수행. 3번 4번은 복사하고 삭제하는 과정으로 상수시간이 걸려 무시할 만 합니다. 종합적으로 따지면 $O (d + h - d)$ , 즉 $O (h)$ 가 됩니다.삭제 시에 소요되는 최대 복잡성은 트리의 높이(h)인 O(h)가 된다.

    //이진트리의 중위 순회 파이썬 코드
    def traverse(self):
        return self.traverseNode(self.root)

    def traverseNode(self, currentNode):
        result = []
        if (currentNode.leftChild is not None):
            result.extend(self.traverseNode(currentNode.leftChild))
        if (currentNode is not None):
            result.extend([currentNode.val])
        if (currentNode.rightChild is not None):
            result.extend(self.traverseNode(currentNode.rightChild))
        return result

한계점