[Data Structure] 색인과 이진 검색 트리(구현, 순회)

기본 자료 구조 이진 트리에 대한 공부 기록이다.

색인

색인은 데이터를 찾을 때 사용되는 지름길 같은 개념이다.

색인은 키와 페이지로 이루어져 있다.

키를 이용해 페이지를 얻어 쉽게 데이터를 찾을 수 있다.

 

색인을 위한 자료구조로는

저번 기록에서 다뤘던 Hash Table

[Data Structure] Hash Table

그리고 이번 기록에서 다룰 이진 검색 트리 등이 있다.

 

이진 검색 트리

트리는 위와 같은 구조로 이루어져 있다.

 

이진 검색 트리의 특징은 아래와 같다.

1. 노드는 모두 서로 다른 키를 갖는다.
2. 각 노드는 최대 2개의 자식을 갖는다(right, left)
3. 임의의 노드의 키는
   1. 자신의 left subtree에 있는 모든 노드의 키보다 크고,
   2. 자신의 right subtree에 있는 모든 노드의  키보다 작다.

서브 트리

그림에서 보는 것처럼

오른쪽의 자식이 right subtree, 왼쪽이 left subtree이다.

배열로 구현한 이진트리

배열로 나타냈을 경우엔 위와 같다.

---

객체 구조

이진 검색 트리를 구현하기 위해서는 두 개의 객체가 필요하다.

노드

노드는 하나의 키(key) 값과 두 개의 자식(left, right)을 가져야 한다.

class TreeNode:
    def __init__(self,newItem,left,right):
        self.item=newItem
        self.left=left
        self.right=right

이진 검색 트리 객체

루트 노드를 정하고, 각 메서드를 구현할 객체가 필요하다.

 

알고리즘

이진 검색 트리 객체에는 어떤 메서드가 필요할까?

검색

search(x) : 원소 x를 검색한다.

    def __searchItem(self,tNode,x):
        if tNode==None:
            return None
        elif x==tNode.item:
            return tNode
        elif x<tNode.item:
            return self.__searchItem(tNode.left,x)
        else:
            return self.__searchItem(tNode.right,x)
            
    def search(self, x):
        return self.__searchItem(self.__root, x)

만난 노드의 값과 같으면 반환,

찾으려는 값이 작으면 해당 노드의 오른쪽 노드에서 다시 재귀,

크면 해당 노드의 왼쪽에서 재귀하는 방식의 알고리즘이다.

 

삽입

insert(x) : 원소 x값을 삽입한다.

    def insert(self,newItem):
        self.__root=self.__insertItem(self.__root,newItem)
        
    def __insertItem(self,tNode:TreeNode,newItem)->TreeNode:
        if(tNode==None):
            tNode=TreeNode(newItem,None,None)
        elif(newItem<tNode.item):
            tNode.left=self.__insertItem(tNode.left,newItem)
        else:
            tNode.right=self.__insertItem(tNode.right,newItem)
        return tNode

검색 알고리즘과 비슷하게 해당 값에 맞는 위치를 찾아서 삽입한다.

 

삭제

delete(x) : 원소 x값을 삭제한다.

    def delete(self,x):
        self.__root=self.__deleteItem(self.__root,x)
        
    def __deleteItem(self,tNode:TreeNode,x)->TreeNode:
        if(tNode==None):
            return None
        elif x==tNode.item:
            tNode=self.__deleteItem(tNode)
        elif x<tNode.item:
            tNode.left=self.__deleteItem(tNode.left,x)
        else:
            tNode.right=self.__deleteItem(tNode.right,x)
        return tNode

검색 메서드를 사용해서 삭제하는 방향으로 리팩터링 해봐야겠다.

 

순회

이진트리에서 모든 노드를 방문하는 알고리즘이다.
순회에는 세 가지 방법이 있다.

모든 순회 방법은 왼쪽 자식 노드를 우선한다.

전위 순회(Preorder Traversal)

전위 순회는 루트를 맨 먼저 방문하는 순회 방법이다.

def printPreOrder(self,root):
    if root:
        print(root.item, end=' ')
        self.printPreOrder(root.left)
        self.printPreOrder(root.right)

루트를 제일 먼저 출력하는 것을 볼 수 있다.

중위 순회(Inorder Traversal)

중위 순회는 루트를 중간에 방문하는 순회 방법이다.

def printInOrder(self,root):
    if root:
        self.printInOrder(root.left)
        print(root.item,end=' ')
        self.printInOrder(root.right)

루트를 중간에 출력하는 것을 볼 수 있다.

후위 순회(Postorder Traversal)

후위 순회는 루트를 마지막에 방문하는 순회 방법이다.

def printPostOrder(self, root):
    if root:
        self.printPostOrder(root.left)
        self.printPostOrder(root.right)
        print(root.item, end=' ')

루트를 중간에 출력하는 것을 볼 수 있다.

방문 순서를 표시해보면 위 그림과 같다.

---

마치며

잘못된 정보에 대한 피드백은 환영입니다.

감사합니다.