자료구조 - 트리

1. 트리 구조

• 트리 : Node와 Branch를 이용해서, 사이클(노드 구조가 원을 이루는 것)이 없는 데이터 구조
• 실제로 어디에 많이 사용되나?
  • 트리 중 이진 트리(Binary Tree) 형태 구조로 탐색(검색) 알고리즘 구현 위해 많이 사용 됨.

2. 용어

• Node : 트리에서 데이터를 저장하는 기본 요소 (Branch 정보 포함)
• Branch : 노드가 어느 노드랑 연결이 되어있는지에 대한 정보를 가진 요소
• Root Node : 트리 가장 상단의 노드
• Parent Node : 어떤 노드의 상위 레벨에 연결된 노드
• Child Node : 어떤 노드의 다음 레벨에 연결된 노드
• Sibling (Bother Node) : 동일한 Parent Node를 가진 노드(형제노드)
• Depth : 트리에서 Node가 가질 수 있는 최대 Level

3. 이진 트리와 이진 탐색 트리(Binary Search Tree)

• 이진 트리 : Branch가 최대 2개인 트리
• 이진 탐색 트리(Binary Search Tree, BST)
  • 값을 비교해서 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지는 트리

4. 자료구조 이진 탐색 트리 장점과 주요 용도

• 주요 용도 : 데이터 검색(탐색)
• 장점 : 탐색 속도를 개선 할 수 있다
• 단점 : 복잡함

5. 이진트리와 정렬된 배열간 탐색 비교

• 27이란 데이터를 찾는 것으로 가정
• 배열에서는 하나하나 다 비교해야 함 (최악의 경우 배열의 크기만큼 걸릴 수 있음)
• 데이터 탐색에 있어서는 이진탐색 트리가 효율적임

5. 이진 탐색 트리 삭제

• 복잡하므로 경우를 나누어서 이해하는 것이 좋다

1. 트리의 맨 끝에 있는 리프 노드(터미널 노드) 삭제 = 삭제할 Node의 Branch가 없을 때
   • 삭제할 Node의 Parent Node의 Branch를 None으로 만들어 줘야 함
2. Child Node가 하나인 Node 삭제
   • 삭제할 Node의 Parent Node의 Branch가 자신의 Child Node를 가리키게 함
3. Child Node가 두 개인 Node 삭제
   1. 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 함 

      • 자식의 자식 노드까지 다 확인해서 가장 작은 값을 찾아 Parent Node의 왼쪽 Branch가 가리키도록 함

      • 결국 오른쪽 자식 노드 중 가장 왼쪽에 있는 값을 올리게 됨

      • 만약 왼쪽 노드에게 오른쪽 자식 노드가 있다면 => 해당 노드의 Parent Node의 왼쪽 Branch로 자식 노드를 가리키게 하고나서 변경

   2. 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 함

      • 위와 마찬가지로 자식노드를 다 확인해서 가장 큰 값을 Parent Node의 오른쪽 Branch가 가리키도록 함

      • 결국 왼쪽 자식 노드 중 가장 오른쪽에 있는 값을 올리게 된다

      • 만약 오른쪽 노드에 왼쪽 자식 노드가 있다면 => 해당 노드의 Parent Node의 오른쪽 Branch로 자식 노드를 가리키게 하고나서 변경

   3. 트리의 규칙을 깨지 않기 위해 위와 같이 가장 작은 값, 큰 값을 찾는 것이다

5.5.2. 삭제할 Node의 Child Node가 한 개인 경우 

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

class NodeMgmt:
    def __init__(self, head):
        self.head = head ## init에 넣은 값이 루트인 헤드노드가 됨

    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < self.current_node.value: ## value가 head 보다 작을 때 왼쪽으로
                if self.current_node.left != None: #이미 Left값이 있다면 그 노드로 가서 다시 비교 시작
                    self.current_node = self.current_node.left  
                else :#Left값이 없으면 Left에 값을 넣음
                    self.current_node.left = Node(value)
                    break
            else : # head보다 크거나 같다면
                if self.current_node.right != None:
                    self.current_node = self.current_node.right
                else :
                    self.current_node.right = Node(value)
                    break
    def search(self, value):
        self.current_node = self.head
        while self.current_node: #self.current_Node가 있을때 계속 실행
            if self.current_node.value == value:
                return True
            elif value < self.current_node.value: #왼쪽에 있다면
                self.current_node = self.current_node.left
            else:
                self.current_node = self.current_node.right
    #위 while문에서 벗어났을 때 (해당 노드가 이진 탐색 트리에 없을 때)
        return False

5.5.3. 삭제할 Node가 Child Node를 두 개인 경우 (삭제할 Node가 Parent Node의 왼쪽에 있을 때)

• 기본 사용가능 전략
  1. 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 함
  2. 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 함
• 기본 사용가능 전략 중, 1번 전략 코드 구현
  1. 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값 가진 Node의 Child Node가 없을 때
  2. 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값 가진 Node의 오른쪽에 Child Node가 있을 때
     • 가장 작은 값 가진 Node의 Child Node가 왼쪽에 있을 경우는 없다. 왜냐면 왼쪽 Node가 있다는 것은 해당 Node보다 더 작은 값 가진 Node가 있다는 뜻이어서

6. 이진 탐색 트리의 시간 복잡도와 단점

1. 시간 복잡도(탐색시)
   • depth(트리 높이)를 h라고 표시한다면 O(h) - 데이터가 1개 있다면 h=1, 데이터가 3개면 h=2, 7개면 대략 h=3...
   • n개의 노드를 가진다면 h = log2n에 가까우므로 시간 복잡도는 O(logn)
     • 빅오 표기법에서 logn의 밑은 10이 아닌 2임
     • 한 번 실행시마다 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉 50%의 실행시간을 단축 시킬 수 있다는 것을 의미함
2. 이진 탐색 트리 단점
   • 평균 시간 복잡도는 O(logn)이지만, 이는 트리가 균형 잡혀 있을때 시간복잡도
   • 한 개씩만 연결되어 있는 경우(최악의 경우)는 링크드 리스트 등과 동일한 성능을 보여줌(O(n))
     • 이 경우에는 강제로 트리를 재조정 시키는 알고리즘이 필요함

 

 

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