[Python] - Tree

Tree 구조와 용어 정리

Tree(트리) : Node(정점)와 Edge(간선)를 이용하여 사이클을 이루지 않도록 구성한 자료구조

• Node : Tree에서 데이터를 저장하는 기본 요소
• Root Node : Tree의 최상위 Node
• Parent Node(부모 노드) : 해당 노드의 다음 Level에 연결된 Node
• Chile Node(자식 노드) : 해당 노드의 상위 Level에 연결된 Node
• Leaf Node(말단 노드) : Child Node가 존재하지 않는 노드
• Level : Node의 깊이를 나타내는 용어로, Root Node가 Level이 0이다.
• Sibling(Brother Node) : 동일한 Parent Node를 가진 Node
• Depth : Tree에서 Node가 가질 수 있는 최대 Level
• Degree(차수) :  Level + 1

 

Binary Tree & Binary Search Tree

Binary Tree(이진 트리) :  Node의 Edge가 최대 2개인 Tree

Binary Search Tree(이진 탐색 트리) : Binary Tree에서 추가적인 조건이 붙는다. 해당 Node의 왼쪽으로 연결된 Node는 해당 Node보다 작은 값이어야 하고, 해당 Node의 오른쪽으로 연결된 Node는 해당 Node보다 큰 값이어야 한다.

 

BTS의 시간 복잡도와 단점

- O(h) (h = Depth )

- n개의 Node를 가지고 있다면 h = log2n에 가까워지므로, 시간 복잡도는 O(logn)

- BTS의 시간복잡도는 O(logn)으로 빠르지만 최악의 경우 linked list와 동일한 O(n)의 시간복잡도를 보여준다.

 

class Node:
    def __init__(self, value):
        self.value = value
        self.left, self.right = None, None


class BinaryTree:
    def __init__(self, r):
        self.root = r

BinaryTree()를 사용하여 Tree를 처음 생성하게 되면 자동으로 Node가 생성되게 구현한다. 이 Node의 Left, Right는 None이다.

class Node:
    def __init__(self, value):
        self.value = value
        self.left, self.right = None, None

    def depth(self):
        leftDepth = self.left.depth() if self.left else 0
        rightDepth = self.right.depth() if self.right else 0
        Depth = leftDepth + 1 if leftDepth > rightDepth else rightDepth + 1
        return Depth

class BinaryTree:
    def __init__(self, r):
        self.root = r
        
    def depth(self):
        if self.root: self.root.depth()
        else: return 0

Binary Tree의 Node의 Depth를 구하는 연산이 필요하다. Root Node가 아니라면 각각의 Node들은 어떤 Node의 Chile Node인 점을 이용하여 재귀를 이용하여 Depth를 구한다.

class BinaryTree:
    def __init__(self, r):
        self.root = r

    def depth(self):
        if self.root: self.root.depth()
        else: return 0

    def insert(self, value):
        self.currentNode = self.root
        while True:
            if value < self.currentNode.value:
                if self.currentNode.left != None:
                    self.currentNode = self.currentNode.left
                else:
                    self.currentNode.left = value
                    break
            else:
                if self.currentNode.right != None:
                    self.currentNode = self.currentNode.right
                else:
                    self.currentNode.right = value
                    break

    def search(self, value):
        self.currentNode = self.root
        while self.currentNode:
            if self.currentNode.value == value:
                return True
            elif value < self.currentNode.value:
                self.currentNode = self.currentNode.left
            elif value > self.currentNode.value:
                self.currentNode = self.currentNode.right
        
        return False

Binary Search Tree를 위한 Insert method와 Search method를 구현한다. Node를 삽입할 때의 규칙은 위에서 설명한 것과 같다. 해당 Node의 왼쪽으로 연결된 Node는 해당 Node보다 작은 값이어야 하고, 해당 Node의 오른쪽으로 연결된 Node는 해당 Node보다 큰 값이어야 한다. Search Method도 위와 같은 규칙을 이용하여 구현한다.

    def delete(self, value):
        checkSearch = False # 삭제할 Node가 있는지 확인하기 위한 boolean 변수 선언
        self.currentNode, self.parent = self.root, self.root
        while self.currentNode: #삭제할 Node = self.currentNode, 삭제할 Node의 Parent Node = self.parent로 만드는 while문
            if self.currentNode.value == value:
                checkSearch = True
                break
            elif value < self.currentNode.value:
                self.parent = self.currentNode
                self.currentNode = self.currentNode.left
            elif value > self.currentNode.value:
                self.parent = self.currentNode
                self.currentNode = self.currentNode.right

        if checkSearch == False: #삭제할 노드가 없으면 False를 return
            return False
        #삭제할 Node가 Leaf Node인 경우
        if self.currentNode.left == None and self.currentNode.right == None:
            if value < self.parent.value:
                self.parent.left = None
            if value > self.parent.value:
                self.parent.right = None
        #삭제할 None가 Child Node를 1개 가지고 있을 경우
        elif self.currentNode.left != None and self.currentNode.right == None: #child Node가 currentNode의 왼쪽에 위치할 때
            if value < self.parent.value:
                self.parent.left = self.currentNode.left
            elif value > self.parent.value:
                self.parent.right = self.currentNode.left
        elif self.currentNode.left == None and self.currentNode.right != None: #child Node가 currentNode의 오른쪽 위치할 때
            if value < self.parent.value:
                self.parent.left = self.currentNode.right
            elif value > self.parent.value:
                self.parent.right = self.currentNode.right

        # 삭제할 Node가 Child Node를 2개 가지고 있을 경우
        elif self.currentNode.left != None and self.currentNode.right != None:
            if value < self.parent.value : #삭제할 Node가 삭제할 Node의 Parent보다 값이 작을 때
                self.changeNode = self.currentNode.right
                self.changeNodeParent = self.currentNode.right
                while self.changeNode.left != None:
                    self.changeNodeParent = self.changeNode
                    self.changeNode = self.changeNode.left
                if self.changeNode.right != None:
                    self.changeNodeParent.left = self.changeNode.right
                else:
                    self.changeNodeParent.left = None
                self.parent.left = self.changeNode
                self.changeNode.right = self.currentNode.right
                self.changeNode.left = self.currentNode.left

            elif value > self.parent.value : #삭제할 Node가 삭제할 Node의 parent보다 값이 클 때
                self.changeNode = self.currentNode.right
                self.changeNodeParent = self.currentNode.right
                while self.changeNode.left != None:
                    self.changeNodeParent = self.changeNode
                    self.changeNode = self.changeNode.left
                if self.changeNode.right != None:
                    self.changeNodeParent.left = self.changeNode.right
                else:
                    self.changeNodeParent.left = None
                self.parent.right = self.changeNode
                self.changeNode.right = self.currentNode.right
                self.changeNode.left = self.currentNode.left
        return True

BTS에서 가장 어려운 연산인 delete Method다.  Node를 삭제할 때 경우의 수는 크게 3가지 이다.  left Node를 삭제하는 경우, 삭제하는 Node의 Child Node가 1개인 경우, 삭제하는 Node의 Child Node가 2개인 경우이다.

1) left node 삭제

- 삭제하는 Node의 parrent Node가 삭제할 Node를 가르키지 않도록 Node값으로 변경시킨다.

2) Child Node가 1개인 Node를 삭제

- 삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 가르키도록한다.

- Child Node가 1개이므로 값을 바꿔주면 되므로 간단하다.

3) Child Node가 2개인 Node를 삭제하는 경우

3-1) 삭제하는 Node가 Parent Node.left일 때

- 삭제할 Node의 오른쪽 자식 중에 가장 작은 값을 parent.eft로 만든다. (또는 삭제할 Node의 왼쪽 자식 중에 가장 큰 값을 parent.left로 만들어도 된다.) 이 때도 2가지의 경우로 나뉜다.

3-1-1) 샥제할 Node의 오른쪽 자식 중에 가장 작은 값을 가진 Node의 Child Node가 없을 때

3-1-2) 삭제할 Node의 오른쪽 자식 중에 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때 (왼쪽에는 없음)

 

3-2) 삭제하는 Node가 Parent Node.right일 때

- 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 parent.right로 만든다. (또는 삭제할 Node의 왼쪽 자식 중에 가장 큰 값을 parent.right로 만들어도 된다.) 이 때도 2가지의 경우로 나뉜다.

3-2-1) 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때

3-2-2) 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때 (왼쪽에는 없음)

 

이렇게 크게는 3개의 경우의 수를 생각하며 delete method를 구현하면 된다.

 

 

++ 추가적으로 구현은 안 했지만 BT에는 순회(Traverse) 연산이 있다. 

1) 전위 순회(Prefix)

- 자기 자신을 출력한 후 left를 끝까지 순회하고 마지막으로 right를 순회한다.

2) 중위 순회(InFix)

- 먼저 left를 끝까지 순회하고, 자기 자신을 출력한 후, rigth를 순회한다.

3) 후위 순회(PostFix)

- left를 순회하고, right를 순회한 후 자기 자신을 출력한다.