[자료구조] Tree 구조(1)

 

안녕하세요? 주니하랑 입니다.

오늘은 자료구조와 알고리즘의 자료구조에서 Tree 구조에 대해 공부 해 보도록 하는 것이에요.

대학교 강의 시간에 참 이해가 안 갔던 것들 중 하나였는데, 다시 한번 공부 해 보도록 하겠습니다.

소스 코드에 대해서 확인 하고 싶으신 분들께서는 주니하랑의 Git hub에 관심을 주세요!

 

 

---

 

📌 Tree 구조

---

 

Tree는 Node와 Branch를 이용하여 Cycle이 이뤄지지 않도록 구성한 Data 구조인 것이에요.

Git을 사용해 보셨다면 Branch 많이 들어보셨지요?

그렇다면 어디에 많이 사용될까요? Tree 구조 중 Binary Tree(이진 트리) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용된답니다!

 

    📍 용어 정리

• Node : Tree에서 실질적으로 Data를 저장하고 있는 곳. 또는 Data를 저장하는 기본 요소 (Data와 다른 Node에 대한 Branch 정보 포함)
• Root Node: Tree 최상단에 위치한 Node
• Level : Tree 최상단 Node를 Level 0이라고 가정 했을 때, 하위 Branch로 연결된 Node의 Depth(깊이)
• Parent Node : 어떤 Node의 다음 하위 Level에 연결된 Node
• Child Node : 어떤 Node의 이전 상위 Level에 연결된 Node
• Leaf Node (Terminal Node) : Child Node가 하나도 없는 Node
• Sibling (Brother Node) : 동일한 Parent Node(부모 Node)를 가진 Node들을 지칭
• Depth : Tree에서 Node가 가질 수 있는 최대 Level(깊이)

 

 

 

위의 그림에서 Node와 Node를 연결 해 주는 선을 Branch라고 하는 것이에요. 다만, 하나 알아야 할 것은 Branch는 부모와 자식 간에만 연결이 가능하고, Siblings 간에는 연결하지 않는답니다. 만약 Node 5, 3, 6이 서로 Branch로 연결 되었다면 Cycle이 형성이 되었을텐데, 3과 6은 Siblings로 서로 Branch로 연결하지 못하다보니 Cycle이 형성될 수 없는 것이에요.

 

 

 

 

 

 

📌 Binary Tree And Binary Search Tree (이진 트리와 이진 탐색 트리)

---

 

이진 트리는 Node의 최대 Branch가 2인 것을 나타내는 것이에요.

Binary Search Tree, BST (이진 탐색 트리)는 다음과 같은 조건이 붙는 것을 이야기 해요!

• 왼쪽 Node는 상단 Node보다 작은 값을 갖으며, 오른쪽 Node는 상단 Node보다 큰 값을 갖는다.

 

출처 : https://blog.penjee.com/5-gifs-to-understand-binary-search-tree/#binary-search-tree-insertion-node

 

 

 

 

 

    📍 Binary Tree And Sorted Array Search(이진 트리와 정렬된 배열간의 탐색 비교)

 

 

출처 : https://blog.penjee.com/wp-content/uploads/2015/11/binary-search-tree-sorted-array-animation.gif

 

위에 가정은 27이라는 Data를 찾는 것이에요. 먼저 이진 탐색 트리에서는 21보다 27이 크기 때문에 오른쪽에서 값을 찾으려고 합니다.

왜냐하면? 이진 탐색 트리는 상단 Node의 값보다 작으면 왼쪽에 크면 오른쪽에 그 Data를 위치 시키는 성질이 있기 때문인 것이에요.

이를 통해 28에 자리로 하게 되고, 27은 28보다 작기 때문에 25의 자리로 갈 것이에요. 27은 25보다 크기 때문에 오른쪽으로 이동하게 될 것이고, 비로소 27을 찾게 되는 것이에요.

이진 탐색 트리로 27이라는 Data를 찾는데, 총 3번의 탐색이 이뤄졌어요!

 

그렇다면 배열은 어떨까요? 내림차순으로 정렬된 배열에서 27을 찾기 위해 위의 gif에서 보는 것과 같이 총 10번의 탐색이 이뤄졌습니다.

둘을 비교하면 탐색 속도 차이가 많이 나겠지요?

 

 

 

 

 

 

📌 Binary Search Tree Node Delete (이진 탐색 트리 노드 삭제)

---

 

이것은 매우 복잡한 것이에요. 때문에 우리는 3가지 경우를 나누어서 알아볼 것이에요!

 

    📍 Leaf Node : Child Node가 없는 Node를 삭제할 때

이 때는 삭제할 Node의 Parent Node(부모 노드)가 삭제할 Node를 Branch로 가르키지 않도록 해야 하는 것이에요.

 

19라는 Node를 삭제하려면 어떻게 해야 할까?

 

19라는 Data가 들어있는 Node를 삭제하려고 할 때는 별 다른 것 없이 15라는 Node가 현재는 19를 Branch로 가르키고 있는데, 이것을 None(Python 등), Null(Java 등)으로 변경하여 Child Node가 없다고 설정을 해 주면 되는 것이에요.

 

 

 

    📍 Child Node가 하나인 Node 삭제

이 때는 삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 가르키게 만들어 주면 되는 것이에요.

 

15라는 Node를 삭제하려면 어떻게 해야 할까?

 

15라는 Data가 있는 Node를 삭제만 하게 되면 19라는 Node는 연결이 되지 않게 되는 것이에요.

그렇기 때문에 15에 Paren Node와 15의 원래 연결 되어 있었던 Child Node를 Branch로 연결 해 주면 되겠지요?

 

 

 

    📍 Child Node가 두 개인 Node 삭제

이 때는 이 두가지를 꼭 기억해야 하는 것이에요.

1. 삭제할 Node의 오른쪽 자식 Node 중 가장 작은 값(해당 Node의 계속 왼쪽으로 내려감)을 삭제할 Node의 자리에 위치시킨다.
   (즉, 삭제할 Node의 Parent Node가 가르키도록 한다.)
2. 삭제할 Node의 왼쪽 자식 Node 중 가장 큰 값(해당 Node의 계속 오른쪽으로 내려감)을 삭제할 Node의 자리에 위치시킨다.
   (즉, 삭제할 Node의 Parent Node가 가르키도록 한다.

 

5라는 Node를 삭제하려면 어떻게 해야 할까?

 

위의 그림에서 5라는 Data가 들어있는 Node를 삭제하려면 해당 자식 중 오른쪽을 선택해서 그 값에 제일 작은 값이 담긴 Node를 현재 5 위치에 두면 되는 것이에요. 위에 그림은 6밖에 없으닌까 6을 위치시키면 되겠네요!

이렇게 삭제를 한다고 했을 때, 그 내용을 적어보면 어떨까요?

• 삭제할 Node의 오른쪽 자식 선택
• 오른쪽 자식의 가장 왼쪽에 있는 Node 선택
• 해당 Node를 삭제할 Node의 Parent Node의 왼쪽 Branch가 가르키게 한다.
• 해당 Node의 왼쪽 Branch가 삭제할 Node의 왼쪽 Child Node를 가르키게 한다.
• 해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node를 가르키게 한다.
• 만약 해당 Node가 오른쪽 Child Node를 가지고 있었을 경우, 해당 Node의 본래 Parent Node의 왼쪽 Branch가 오른쪽 Child를 가르키게 한다.

 

 

 

 

 

📌 Binary Search Tree Delete Code

---

 

삭제할 Node가 없는 경우에도 연산이 처리되야 한다.

이를 위해 삭제할 Node가 없는 경우 False를 반환하고, 함수를 종료한다.

 

    def delete(self, value):
        searched = False  # Tree를 순회하면서 해당 값이 있는지 찾을 때 사용하는 변수 선언
        self.current_node = self.head  # 삭제할 Node를 지칭
        self.parent = self.head  # 삭제할 Node의 부모를 지

        while self.current_node:  # 삭제할 Node가 값이 있다면 반복
            if self.current_node.value == value:  # 삭제할 Node의 Data가 입력값과 같다면?
                searched = True  # 해당 값이 있기에 True로 변경
                break  # while 문을 끝낸다.

            elif value < self.current_node.value:  # 찾을 값이 비교 대상보다 작다면?
                self.parent = self.current_node
                self.current_node = self.current_node.left

            else:
                self.parent = self.current_node
                self.current_node = self.current_node.right

        if searched == False:
            return False

        # == 이후부터 삭제 Case에 맞추어 Code 작성 == #

 

    📍 Case 1 : 삭제할 Node가 Leaf Node인 경우

 

 

       # Leaf Node인 경우 삭제 Case
        # self.current_node가 삭제할 Node이고, self.parent Node는 삭제할 Node의 Parent Node
        if self.current_node.left == None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = None

            else:
                self.current_node.right = Node
                del self.current_node

 

 

 

  📍 Case 2 : 삭제할 Node가 Child Node를 한 개 가지고 있을 경우

 

 

 

 

            # 삭제할 Node가 Parent 기준 왼쪽에 있을 때
            if self.current_node.left != None and self.current_node.right == None:	# 삭제할 Node의 왼쪽 자식 Node가 None이 아니고, 오른쪽 자식 Node는 None 이라면?
                if value < self.parent.value:	# 삭제할 값이 부모 Node의 값보다 작다면?
                    self.parent.left = self.current_node.left	# 부모 Node의 왼쪽 자식 Node에 삭제할 Node의 왼쪽 자식 Node를 넣음으로 가르키게 한다.

                else:							# 삭제할 값이 부모 Node의 값보다 크다면?
                    self.parent.right = self.current_node.left	# 부모 Node의 오른쪽 자식 Node에 삭제할 Node의 왼쪽 자식 Node를 넣음으로 가르키게 한다.
                    
                    
           # 삭제할 Node가 Parent 기준 오른쪽에 있을 때
            elif self.current_node.left == None and self.current_node.right != None:
                if value < self.parent.value:
                    self.parent.left = self.current_node.right

                else:
                    self.parent.right = self.current_node.right

 

 

---

 

 

주니하랑의 글이 마음에 드셨나요? 구독과 공감! 그리고, 댓글은 주니하랑에게 많은 힘이 됩니다