알고리즘 - Binary Search Tree / Tree (이진 탐색 트리, 트리, 이진 트리, Python 코드)

트리 (Tree)

트리 (Tree)란 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조이다.

트리는 트리 내에 다른 하위 트리가 있고 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료구조이다. 

 

이진 탐색 트리의 예시

 

 

트리 (Tree)에서 사용하는 용어

- 노드 (Node)

트리를 구성하고 있는 기본 요소

 

 

-  간선 (Edge)

노드와 노드 간의 연결선

 

 

-  루트노드 (Root Node)

트리 구조에서 부모가 없는 최상위 노드

 

 

- 부모노드 (Parent Node)

자식 노드를 가진 노드

 

 

-  자식노드 (Child Node)

부모 노드의 하위 노드

 

 

-  형제노드 (Sibling Node)

같은 부모를 가지는 노드

 

 

- 외부 노드(external node, outer node), 단말 노드 (terminal node), 리프 노드(leaf node)

자식 노드가 없는 노드

 

 

 - 내부 노드 (internal node, inner node), 비 단말 노드 (non-terminal node), 가지 노드 (branch node)

자식 노드 하나 이상 가진 노드

 

 

- 높이 (height)

어떤 노드에서 리프 노드까지 가장 긴 경로의 간선(Edge) 수

 

 

- 깊이 (depth)

루트에서 어떤 노드까지의 간선(Edge) 수

 

 

 

트리의 특징

1. 하나의 루트 노드와 0개 이상의 하위 트리로 구성되어 있다.

2. 데이터를 순차적으로 저장하지 않기 때문에 비선형 자료구조이다. 

3. 트리 내에 또 다른 트리가 있는 재귀적 자료구조이다. 

4. 단순 순환을 갖지 않고, 연결된 무방향 그래프 구조이다. 

5. 노드 간에 부모 자식 관계를 갖고 있는 계층형 자료구조이며 모든 자식 노드는 하나의 부모 노드만 갖는다.

6. 노드가 n개인 트리는 항상 n-1개의 간선(edge)을 가진다. 

 

 

트리의 종류

- 편향 트리

모든 노드들이 자식을 하나만 가진 트리 

 

- 이진 트리

각 노드의 차수(자식 노드)가 2 이하인 트리

 

- 이진 탐색 트리

순서화된 이진 트리

노드의 왼쪽 자식은 부모의 값보다 작은 값을 가져야 하며 노드의 오른쪽 자식은 부모의 값보다 큰 값을 가져야 한다.

 

- 균형 트리

높이 균형을 유지하는 트리

 

 

Python으로 구현한 코드

class Node:
    def __init__(self,value):#이진트리이므로 left와 right만 있어도 됨
        self.value = value
        self.left = None
        self.right = None
 
class NodeMgmt:
    def __init__(self,head): #root노드가 head
        self.head=head
        
    # 삽입 함수
    def insert(self,value):
        self.current_node = self.head #현재 노드는 head로 잡음
        while True: #recursive
            if value < self.current_node.value: 
                if self.current_node.left != None: 
                    self.current_node = self.current_node.left
                else: 
                    self.current_node.left = Node(value)
                    break

            else:
                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 #현재 노드는 head로 잡음
        
        while self.current_node: 
            if self.current_node.value == value: 
                return True
                break
            elif value < self.current_node.value:
                self.current_node = self.current_node.left
            else:
                self.current_node = self.current_node.right
        return False    
    
    # 삭제 함수
    def delete(self, value):
        searched = False
        self.current_node = self.head
        self.parent = self.head
        
        # 삭제하고자 하는 value를 가지고 있는 노드를 탐색하여 current_node로 설정
        
        while self.current_node:
            if self.current_node.value == value:
                searched = True
                break 
            
            elif value < 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
    

        if self.current_node.left == None and self.current_node.right==None:
            if value<self.parent.value:
                self.parent.left = None
            else:
                self.parent.right = None
            del self.current_node
        # 왼쪽 자식 노드만 있을 때
        if self.current_node.left != None and self.current_node.right==None:
            if vale<self.parent.value: 
                self.parent.left = self.current_node.left
            else: 
                self.parent.right = self.current_node.left
        #오른쪽 자식 노드만 있을 때
        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
            
        #child가 두 개 있을 때
        if self.current_node.left != None and self.current_node.right != None:
            if value<self.parent.value: #3-1
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left != None:
                    self.change_node.parent = self.change_node
                    self.change_node = self.change_node.left
                
                if self.change_node.right != None: #3-1-2
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                
                self.parent.left = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.change_node.left
            
            else:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left != None:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.left
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.right = self.change_node
                self.change_node.left = self.current_node.left
                self.change_node.right = self.current_node.right