Binary Search Tree [BST] '이진트리' with Python

트리(Tree)

 

• 루트 노드(root node) : 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node) : 자식이 없는 노드, '말단 노드' 또는 '잎 노드'라고도 부른다.
• 내부(internal) 노드 : 단말 노드가 아닌 노드
• 간선(edge) : 노드를 연결하는 선 (link, branch 라고도 부름)
• 형제(sibling) : 같은 부모를 가지는 노드
• 노드의 크기(size) : 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야한는 간선의 수
• 노드의 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree) : 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
• 트리의 차수(degree of tree) : 트리의 최대 차수
• 트리의 높이(height) : 루트 노드에서 가장 깊숙히 있는 노드의 깊이

📌 기본 Node 구조

노드는 세 개의 멤버를 가지고 있고, 10이라는 변수는 val에 값으로 들어간다. ( self.val = 10 )

초기에 생성할 때는 self.left = None  / self.right = None 으로 설정된다.

 

 ################
 ##Node 기본 셋팅##
 ################
 
 # .val 으로는 값이 들어간다.
 # 처음 생성할 때는 item을 가지고 head를 만들고, 왼쪽 오른쪽은 None으로 설정한다.
 def __init__(self, item):
     self.val = item
     self.left = None
     self.right = None

 

 

 

📌 Node에 추가하기

이진트리 21을 넣는다고 가정하면,

27보다는 작기 때문에 왼쪽 / 20보다는 크기 때문에 오른쪽 / 22보다는 작기 때문에 왼쪽에 21을 생성하면 된다.

 def add(self, item):
        # 제일 위에있는 노드의 값이 None일때(head.val에 값이 없을 때), 완전히 새로운 노드를 만들때
        if self.head.val is None:
            # item 매개변수를 head 값으로 설정
            self.head.val = item
        # 제일 위에 있는 노드의 값이 None이 아닐때(head.val에 값이 있을 때), 이미 존재한 노드 밑에 노드를 추가할 때
        else:
            # _add_node()를 실행하고 매개변수로 self.head 와 item을 보낸다.
            self.__add_node(self.head, item)
 
 #  self.head 가 cur로 전달된다.
 def __add_node(self, cur, item):
        # cur(self.head)의 값이 item 값보다 크거나 같을 때
        if cur.val >= item:
            # cur의 왼쪽 줄기에 값이 None이 아니라면, 다시 _add_node() 함수 반복. 이번에는 cur.left 가 cur로 들어간다.
            if cur.left is not None:
                self.__add_node(cur.left, item)
            # cur의 왼쪽 줄기에 값이 None이라면, 해당 부분의 노드를 추가한다.
            else:
                # cur 왼쪽의 값은 item 값을 헤드로 넣은 새로운 Node를 만든다.
                cur.left = Node(item)
        # cur(self.head)의 값이 item 보다 작을 때 (item이 더 크기 때문에 self.head의 오른쪽으로 이동)
        else:
            # cur의 오른쪽 값이 None이 아니라면, cur.right 값을 가지고 다시 _add_node 함수를 반복.
            if cur.right is not None:
                self.__add_node(cur.right, item)
            # cur의 오른쪽 값이 None이라면, cur.right의 값에 item으로 만든 새로운 노드를 만든다.
            else:
                cur.right = Node(item)

 

 

 

📌 Node 검색하기

head(27)에서 시작 -> 19는 27보다 작기 때문에 왼쪽 -> 14보다는 크기 때문에 오른쪽 -> 19발견! (True 반환)

head(27)에서 시작 -> 20은 27보다 작기 때문에 왼쪽 -> 14보다는 크기 때문에 오른쪽 -> 19보다는 크기 때문에 오른쪽 -> 하지만, 20은 없음 (False 반환)

############
##Node 검색##
#############
    def search(self, item):
        # head의 값이 None일 때(노드가 없을 때)
        if self.head.val is None:
            # false를 반환
            return False
        # head 값이 있을 때
        else:
            # __search_node() 함수에 head 값과 찾을 노드인 item을 보낸다.
            return  self.__search_node(self.head, item)
 
    def __search_node(self, cur, item):
        # 현재 값과 item 값이 같다면
        if cur.val == item:
            # item 찾기 성공!
            return True
        # 현재 값과 item 값이 다르다면
        else:
            # cur의 값이 item보다 크거나 같다면
            if cur.val >= item:
                # cur 왼쪽 값이 None이 아니라면
                if cur.left is not None:
                    # 해당 cur에서 다시 왼쪽으로 가서 item과 다시 비교한다. (재귀함수)
                    return self.__search_node(cur.left, item)
                # cur 왼쪽 값이 None이라면
                else:
                    # 해당 왼쪽 노드를 다 돌아본 것이기에 false를 반환.
                    return False
            # cur의 값이 item 보다 작다면
            else:
                # cur 오른쪽 값이 None이 아니라면
                if cur.right is not None:
                    # 해당 cur에서 다시 오른쪽으로 가서 item과 다시 비교한다. (재귀함수)
                    return self.__search_node(cur.right, item)
                # cur 오른쪽 값이 None이라면
                else:
                    # 해당 오른쪽 노드를 다 돌아본 것이기에 false를 반환.
                    return False

 

 

 

📌 Node에서 값 제거하기 ①

 

1. 지우고자 하는 노드가 자식 노드가 하나도 없을 때

-> 10을 지우고 싶다.

27보다 작으니까 왼쪽 => 14보다 작으니까 왼쪽 => 10을 삭제

 

📌 Node 에서 값 제거하기 ②

 

2. 삭제하려는 노드가 자식이 하나 있을 때

-> 31을 지우고 싶다.

27보다는 크니까 오른쪽 => 35보다는 작아서 왼쪽 => 부모를 죽이고 자식을 할아버지에게 직접 붙여주면 됨. (31을 지우고 자식 노드인 30을 35에 붙여준다.)

 

📌 Node 에서 값 제거하기 ③

 

3. 삭제하려는 노드가 양쪽에 모두 자식이 있을 때

-> 35를 지운다.

 

자식 노드가 너무 많음.

오른쪽 서브 트리에서 가장 왼쪽에 있는 노드를 옮기면 된다. (40)

35를 없애고 40을 35의 위치로 보낸다.

 

#############
##Node 제거##
#############
    def remove(self, item):
        # self 의 헤드 값이 None이라면
        if self.head.val is None:
            print('there is no item : in BST', item)
        # self 의 헤드 값이 item이라면 -> 지워야함.
        if self.head.val == item:
            # 1) 자식이 없는 Node를 지울 때 (왼쪽, 오른쪽 모두 None)
            if self.head.left is None and self.head.right is None:
                # head를 지워버린다.
                self.head = None
            # 2) 왼쪽에 자식이 하나 있는 Node를 지울 때
            elif self.head.left is not None and self.head.right is None:
                # 왼쪽 값을 head로 올리면 된다.
                self.head = self.head.left
            # 3) 오른쪽에 자식이 하나 있는 Node를 지울 때
            elif self.head.left is None and self.head.right is not None:
                # 오른쪽 값을 head로 올린다.
                self.head = self.head.right
            # 4) 양 쪽 모두 자식이 있을 때
            else:
                # 양 쪽 모두 자식이 있을 때는 오른쪽 노드의 제일 왼쪽 자식 값을 head로 올리면된다.
                self.head.val = self.__most_left_val_from_right_node(self.head.right).val
                self.__removeitem(self.head, self.head.right, self.head.val)
        # self 의 헤드 값이 item 이 아니라면
        else:
            # self.head 의 값이 item 보다 크다면
            if self.head.val > item:
                # 왼쪽 노드로 내려간다. left 노드와 함께 item을 보낸다.
                self.__remove(self.head, self.head.left, item)
            # self.head의 값이 item 보다 작다면
            else:
                # 오른쪽 노드로 내려간다. right 노드와 함께 item 을 보낸다.
                self.__remove(self.head, self.head.right, item)

    # parent : 부모 node / cur : 현재 node / item : 찾을 값
    def __remove(self, parent, cur, item):
        # 현재 node가 끝
        if cur is None:
            print('There is no item:', item)
        # 현재 값이 item 값과 같다면
        if cur.val == item:
            # 1) cur이 자식이 없는 node일 경우
            if cur.left is None and cur.right is None:
                # 부모의 왼쪽 노드가 cur인 경우 (마지막 끝단에 cur이 있기 때문에
                if parent.left == cur:
                    # parent 의 왼쪽 노드(cur) 을 None으로 바꾼다. (제거)
                    parent.left = None
                # 부모의 오른쪽 노드가 cur인 경우
                else:
                    # parent 의 오른쪽 노드(cur)을 None으로 바꿔준다. (제거)
                    parent.right = None
            # 2) 왼쪽에 자식이 하나 있는 cur인 경우
            elif cur.left is not None and cur.right is None:
                # 부모의 왼쪽 노드가 cur인 경우
                if parent.left == cur:
                    # 부모의 왼쪽 노드를 현재 노드의 왼쪽(cur) 값으로 이어 붙인다.
                    parent.left = cur.left
                # 부모의 오른쪽 노드가 cur인 경우
                else:
                    # 부모의 오른쪽 노드를 현재 노드(cur)의 왼쪽 값으로 이어 붙인다.
                    parent.right = cur.left
            # 3) 오른쪽에 자식이 하나 있는 cur인 경우
            elif cur.left is None and cur.right is not None:
                # 부모의 왼쪽 노드가 cur 인 경우
                if parent.left == cur:
                    # 부모의 왼쪽 노드를 현재 노드(cur)의 오른쪽 값으로 이어 붙인다.
                    parent.left = cur.right
                # 부모의 오른쪽 노드가 cur인 경우
                else:
                    # 부모의 오른쪽 노드를 현재 노드(cur)의 오른쪽 값으로 이어 붙인다.
                    parent.right = cur.right
            # 4) cur의 양쪽 모두 자식이 있는 경우
            else:
                cur.val = self.__most_left_val_from_right_node(cur.right).val
                self.__removeitem(cur, cur.right, cur.val)

    # cur의 자식이 모두 있을 때, cur을 지워야하는 경우 => cur의 오른쪽 node의 왼쪽 제일 아래 값을 cur로 지정.
    def __most_left_val_from_right_node(self, cur):
        # cur의 왼쪽 노드가 None 일때, 해당 부근에 도착
        if cur.left is None:
            # cur을 반환한다.
            return cur
        # cur의 왼쪽 노드가 Nonde이 아니라면
        else:
            # 왼쪽 끝까지 가기위해서 재귀함수 실행 (인수로 cur.left 값을 계속 전달)
            return self.__most_left_val_from_right_node(cur.left)


    def __removeitem(self, parent, cur, item):
        if cur.val == item:
            # 부모의 왼쪽 노드가 cur인 경우
            if parent.left == cur:
                # 부모의 왼쪽 노드를 None으로 바꾼다. (제거)
                parent.left = None
            # 부모의 오른쪽 노드가 cur인 경우
            else:
                # 부모의 오른쪽 노드를 None으로 바꾼다. (제거)
                parent.right = None
        # cur.val 이 item과 다를 때
        else:
            # cur.val 이 item 보다 큰거나 같은 경우
            if cur.val >= item:
                # cur의 왼쪽 노드로 이동해서 다시 반복 (재귀함수)
                self.__removeitem(cur, cur.left, item)
            # cur.val 이 item 보다 작은 경우
            else:
                # cur의 오른쪽 노드로 이동해서 다시 반복 (재귀함수)
                self.__removeitem(cur, cur.right, item)

 

(Tip)

- cur 은 노드이고 cur.val은 노드의 값과 left, right 필드를 가지고 있다.

 

참고

www.youtube.com/watch?v=0CqDdXOr6Kk

github.com/minsuk-heo/problemsolving/blob/master/data_structure/BinaryTree.py