📖Binary Search Tree

다음과 같은 조건이 붙은 이진 트리

1. 왼쪽 자식 노드에는 자신보다 작은 값
2. 오른쪽 자식 노드에는 자신보다 큰 값
3. 모든 노드는 유일한 값을 가짐

• 이진탐색의 효율적인 탐색을 유지하면서도, 빈번한 삽입/삭제를 가능하게 고안됨

📖순회 방법

• 부모 노드와 왼쪽 노드, 오른쪽 노드를 어떤 순서로 방문하느냐에 따라 나눠짐
• 순회하는 방법은 재귀적 ( ∵ 각 노드는 서브 트리)

1. 전위 순회(Preorder Traversal)

현재 노드-왼쪽 노드-오른쪽 노드 순으로 순회하는 방법

순회 결과 : A → B → D → G → E → C → F

2. 중위 순회(Inorder Traversal)

왼쪽 노드-현재 노드-오른쪽 노드 순으로 순회하는 방법

순회 결과 : G → D → B → E → A → F → C

• 이진탐색트리 내에 있는 모든 값들을 정렬된 순서대로 탐색 가능

3. 후위 순회(Postorder Traversal)

왼쪽 노드-오른쪽 노드-현재 노드 순으로 순회하는 방법

순회 결과 : G → D → E → B → F → C → A

4. 레벨 순서 순회(Level Order Traversal)

레벨 0(루트 노드)부터 레벨 차례로 방문하며, 같은 레벨에서는 왼쪽에서 오른쪽으로 가며 순회하는 방법

순회 결과 : A → B → C → D → E → F → G

• 큐로 구현

📖구현

📎Node Class

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

📎Binary Search Tree Class

class BinarySearchTree:
    def __init__(self, root):
        self.root = root

Insert

    def insert(self, data):
        self.cur = self.root
        
        while True:
            # 추가할 노드가 현재 위치의 노드보다 작을 때(왼쪽 서브 트리)
            if data < self.cur.data:
                # 왼쪽 자식 노드가 있을 때 → 현재 위치 왼쪽 자식 노드로 바꾸고 계속 탐색
                if self.cur.left != None:
                    self.cur = self.cur.left
                # 왼쪽 자식 노드가 없을 때 → 해당 위치에 추가할 값을 연결 후 탐색 끝
                else:
                    self.cur.left = Node(data)
                    break
                
            # 추가할 노드가 현재 위치의 노드보다 클 때(오른쪽 서브 트리)
            else:
                # 오른쪽 자식 노드가 있을 때 → 현재 위치 오른쪽 자식 노드로 바꾸고 계속 탐색
                if self.cur.right != None:
                    self.cur = self.cur.right
                else:
                    self.cur.right = Node(data)
                    break

Search

    def search(self, data):
        self.cur = self.root
        
        while self.cur:
            # 찾고자 하는 노드 찾은 경우
            if data == self.cur.data:
                return True
            # 찾고자 하는 노드가 현재 위치의 노드보다 작을 때 → 현재 위치 왼쪽 자식 노드로 바꾸고 계속 탐색
            elif data < self.cur.data:
                self.cur = self.cur.left
            # 찾고자 하는 노드이 현재 위치의 노드보다 클 때 → 현재 위치 오른쪽 자식 노드로 바꾸고 계속 탐색
            else:
                self.cur = self.cur.right
            
        # 찾고자 하는 노드 못 찾은 경우
        return False

Remove

    def remove(self, data):
        searched = False
        self.cur = self.root
        self.parent = self.root
        
        # 삭제하고자 하는 노드가 트리 안에 존재하는지 체크
        while self.cur:
            if data == self.cur.data:
                searched = True
                break
            elif data < self.cur.data:
                self.parent = self.cur
                self.cur = self.cur.left
            else:
                self.parent = self.cur
                self.cur = self.cur.right
            
        # 삭제하고자 하는 노드 없음
        if not searched:
            return False

1. 자식 노드가 없는 경우

부모 노드가 삭제할 노드를 가리키지 않도록 함

        # 삭제할 노드의 자식 노드가 없는 경우
        if self.cur.left == self.cur.right == None:
            if data < self.parent.data:
                self.parent.left = None
            else:
                self.parent.right = None

2. 자식 노드가 1개인 경우

부모 노드가 삭제할 노드의 자식 노드를 가리키도록 함

        # 삭제할 노드의 자식 노드가 1개인 경우
        # 그 경우 중 삭제할 노드의 자식 노드가 왼쪽 자식 노드인 경우
        elif self.cur.left != None and self.cur.right == None:
            if data < self.parent.data:
                self.parent.left = self.cur.left
            else:
                self.parent.right = self.cur.left
        # 그 경우 중 삭제할 노드의 자식 노드가 오른쪽 자식 노드인 경우
        elif self.cur.left == None and self.cur.right != None:
            if data < self.parent.data:
                self.parent.left = self.cur.right
            else:
                self.parent.right = self.cur.right

3. 자식 노드가 2개인 경우

Preorder Traversal

    def preorder_traversal(self, node):
        if not node:
            return
        print(node.data, end =' ')
        self.preorder_traversal(node.left)
        self.preorder_traversal(node.right)

Inorder Traversal

    def inorder_traversal(self, node):
        if not node:
            return
        self.inorder_traversal(node.left)
        print(node.data, end =' ')
        self.inorder_traversal(node.right)

postorder Traversal

    def postorder_traversal(self, node):
        if not node:
            return
        self.postorder_traversal(node.left)
        self.postorder_traversal(node.right)
        print(node.data, end =' ')

Levelorder Traversal

    def levelorder_traversal(self, root):
        q = [(root, 0)]
        l = 0
        
        while q:
            node, level = q.pop(0)
            print(node.data, end = ' ')
 
            # 레벨 별 줄바꿈 출력
            if level != l:
                l += 1
                print()
                
            if node.left:
                q.append((node.left, level + 1))
            if node.right:
                q.append((node.right, level + 1))

📖시간복잡도

h는 트리의 높이

연산	시간복잡도
삽입	O(h)
삭제	O(h)
탐색	O(h)

• 연산 모두 트리의 높이에 의해 시간복잡도가 결정 → 트리가 한 쪽으로 치우쳐진 경우 시간복잡도가 너무 커짐