천천히 하지만 더 멀리

이진 탐색 트리 ( Binary Search Tree ) 본문

CS/자료 구조

이진 탐색 트리 ( Binary Search Tree )

PJamesY 2022. 2. 19. 19:56

이진 트리를 탐색에 조금더 활용하기 위해서 이진 탐색 트리를 정의 한다.

 

이진 탐색 트리(BST) 는 이진트리이면서 다음 두 조건을 만족해야 한다.

1. 각 노드의 왼쪽 서브트리의 키값은 노드의 키값보다 작거나 같아야 하고

2. 각 노드의 오른쪽 서브트리의 키값은 노드의 키값보다 커야 한다.

위 두 조건을 모든 이진트리 노드가 만족하면 이진 탐색 트리라고 한다.

 

이진 탐색 트리를 클래스로 구현해보면 다음과 같다.

class BST:
    def __init__(self):
        self.root = None
        self.size = 0

    def __len__(self):
        return self.size

    def __iter__(self):
        return self.root.__iter__() # 노드 클래스에 있는 __iter__ 메서드를 호출 ( ex preOrder )

 

1. find_loc  ( 검색 )

find_loc 메서드는 찾으려는 노드의 key 를 함수의 인수로 넣고 만약 해당 key 를 가진 노드가 있으면 노드를 반환하고 해당 key 를 가지고 있지 않다면 노드를 삽입할 곳의 부모 노드를 반환한다. 코드를 구현해보자

class BST:
    def __init__(self):
        self.root = None
        self.size = 0

    def __len__(self):
        return self.size

    def __iter__(self):
        return self.root.__iter__() # 노드 클래스에 있는 __iter__ 메서드를 호출 ( ex preOrder )
	
    # key값을 가진 노드가 있다면 해당 노드를 return, 없으면 노드가 삽입될 부모노드를 return
    def find_loc(self, key): 
        if self.size == 0: # 빈트리면 key 값은 처음 들어가는 경우이다.
            return None
        p = None
        v = self.root

        while v != None: # v 가 None 이 된다는 것은 key 값을 못찾았다는 것이다
            if v.key == key: return v # Node 의 키가 찾고자 하는 key 와 같다면 같은 key 를 가지고 있는 노드 반환
            elif v.key < key: # 현재 노드의 key 가 찾고자 하는 key 보다 작으면 
                p = v # p는 v의 부모가 된다
                v = v.right # 오른쪽 하위 노드로 이동
            else: # 현재 노드의 key 가 찾고자 하는 key 보다 크면
                p = v $ p 는 v의 부모가 된다.
                v = v.left # 왼쪽 하위 노드로 이동

        # key 값이 트리에 없다면 부모노드 반환
        return p

 

2. insert ( 삽입 )

이진탐색 트리에 노드를 삽입하는 경우

1. find_loc 메서드를 통해 들어갈 위치의 부모노드를 검색한다.  p = find_loc(key) 

2. 만약에 삽입하려는 key 값의 노드가 이미 존재하면 삽입하지 않고 삽입하려는 key 가 없다면 노드를 생성한다. v = Node(key) 

3. 노드를 find_loc 을 통해 찾은 부모에 삽입을 하는데 부모 노드 key 값 보다 크면 오른쪽 하위 노드로 삽입하고, 부모 노드 key 값 보다 작으면 왼쪽 하위노드에 삽입한다. 

4. size 를 1개 키운다

class BST:
    def __init__(self):
        self.root = None
        self.size = 0

    def __len__(self):
        return self.size

    def __iter__(self):
        return self.root.__iter__() # 노드 클래스에 있는 __iter__ 메서드를 호출 ( ex preOrder )
	
    # key값을 가진 노드가 있다면 해당 노드를 return, 없으면 노드가 삽입될 부모노드를 return
    def find_loc(self, key): 
        if self.size == 0: # 빈트리면 key 값은 처음 들어가는 경우이다.
            return None
        p = None
        v = self.root

        while v != None: # v 가 None 이 된다는 것은 key 값을 못찾았다는 것이다
            if v.key == key: return v # Node 의 키가 찾고자 하는 key 와 같다면 같은 key 를 가지고 있는 노드 반환
            elif v.key < key: # 현재 노드의 key 가 찾고자 하는 key 보다 작으면 
                p = v # p는 v의 부모가 된다
                v = v.right # 오른쪽 하위 노드로 이동
            else: # 현재 노드의 key 가 찾고자 하는 key 보다 크면
                p = v $ p 는 v의 부모가 된다.
                v = v.left # 왼쪽 하위 노드로 이동

        # key 값이 트리에 없다면 부모노드 반환
        return p

    # 반환값이 None 이 아니면 정상적으로 삽입
    def insert(self, key):
        p = self.find_loc(key) # 새로 삽입될 노드 위치의 부모노드가 반환된다 O(h)
        if p == None or p.key != key:
            v = Node(key)
            if p == None: # 애초에 트리 자체가 빈 트리
                self.root = v # 루트로 삽입된다.
            else: # 부모노드의 자식노드로 들어갈수 있다.
                v.parent = p
                if p.key >= key: # key 값이 부모 key 값 보다 작으면 
                    p.left = v # 부모의 왼쪽 하위노드로 링크
                else: # key 값이 부모 key 값 보다 크면 
                    p.right = v # 부모의 오른쪽 하위노드로 링크

            self.size += 1
            return v
        else:
            print("key is already included")
            return p # p = None

3. Delete ( 삭제 )

3 - 1 DeleteByMerging

삭제하려는 노드를 X 라고 하고 X 의 왼쪽노드를 a, X의 오른쪽 노드를 b 라고 한다면 a 노드와 a 의 모든 자식노드를 X 노드 자리로 옮기고 a 자식노드 중에 맨 오른쪽 자식 노드의 오른쪽 자식노드로 노드 b 를 링크 시킨다. 이해를 위해 그림으로 살펴보자.

delet by merging

위 그림에서 m 은 a 노드의 자식 노드중에 가장 오른쪽에 있는 노드이다

그런데 만약에 a 노드가 존재 하지 않으면 즉 삭제하고자 하는 노드 X 의 왼쪽 자식 노드가 존재하지 않으면 어떻게 될까??

답은 단순하다 X의 오른쪽 노드 b 가 있다면 노드 X 를 지우고 노드 b 를 노드 X 자리에 위치 시키면 된다.

왼쪽 노드가 없을때

class BST:
    def __init__(self):
        self.root = None
        self.size = 0

    def __len__(self):
        return self.size

    def __iter__(self):
        return self.root.__iter__() # 노드 클래스에 있는 __iter__ 메서드를 호출 ( ex preOrder )
	
    # key값을 가진 노드가 있다면 해당 노드를 return, 없으면 노드가 삽입될 부모노드를 return
    def find_loc(self, key): 
        if self.size == 0: # 빈트리면 key 값은 처음 들어가는 경우이다.
            return None
        p = None
        v = self.root

        while v != None: # v 가 None 이 된다는 것은 key 값을 못찾았다는 것이다
            if v.key == key: return v # Node 의 키가 찾고자 하는 key 와 같다면 같은 key 를 가지고 있는 노드 반환
            elif v.key < key: # 현재 노드의 key 가 찾고자 하는 key 보다 작으면 
                p = v # p는 v의 부모가 된다
                v = v.right # 오른쪽 하위 노드로 이동
            else: # 현재 노드의 key 가 찾고자 하는 key 보다 크면
                p = v $ p 는 v의 부모가 된다.
                v = v.left # 왼쪽 하위 노드로 이동

        # key 값이 트리에 없다면 부모노드 반환
        return p

    # 반환값이 None 이 아니면 정상적으로 삽입
    def insert(self, key):
        p = self.find_loc(key) # 새로 삽입될 노드 위치의 부모노드가 반환된다 O(h)
        if p == None or p.key != key:
            v = Node(key)
            if p == None: # 애초에 트리 자체가 빈 트리
                self.root = v # 루트로 삽입된다.
            else: # 부모노드의 자식노드로 들어갈수 있다.
                v.parent = p
                if p.key >= key: # key 값이 부모 key 값 보다 작으면 
                    p.left = v # 부모의 왼쪽 하위노드로 링크
                else: # key 값이 부모 key 값 보다 크면 
                    p.right = v # 부모의 오른쪽 하위노드로 링크

            self.size += 1
            return v
        else:
            print("key is already included")
            return p # p = None


    def deleteByMerging(self, x):
        a = x.left, b = x.right
        pt = x.parent
        c # 노드 X 자리를 대체할 노드
        m # 노드 X의 왼쪽 자식노드의 자식노드중에 가장 오른쪽 노드

        if a != None:
            c = a
            m = a
            while m.right: # 계속 오른쪽으로 내려간다
                m = m.right

            if b != None:
                b.parent = m
                
            m.right = b
        else: # a == None
            c = b

        if pt != None: # 노드 x 의 부모노드가 있을때
            if c: c.parent = pt
            if pt.key < c.key:
                pt.right = c
            else:
                pt.left = c
        else: # pt == None 지워야할 노드가 root 노드
            self.root = c
            if c: c.parent = None

        self.size -= 1

 

3 - 2 DeleteByCopying

지우고자 하는 노드 X 의 왼쪽 자식노드 a의 자식노드중에 가장 오른쪽 아래 있는 노드 M 을 지운 노드 X 자리로 이동시키고 노드 M 의 왼쪽 자식 노드는 노드 a, 노드 M의 오른쪽 자식노드는 노드 b 로 해준다. 그림을 통해 이해해보자

코드를 통해 구현해보자

class BST:
    def __init__(self):
        self.root = None
        self.size = 0

    def __len__(self):
        return self.size

    def __iter__(self):
        return self.root.__iter__() # 노드 클래스에 있는 __iter__ 메서드를 호출 ( ex preOrder )
	
    # key값을 가진 노드가 있다면 해당 노드를 return, 없으면 노드가 삽입될 부모노드를 return
    def find_loc(self, key): 
        if self.size == 0: # 빈트리면 key 값은 처음 들어가는 경우이다.
            return None
        p = None
        v = self.root

        while v != None: # v 가 None 이 된다는 것은 key 값을 못찾았다는 것이다
            if v.key == key: return v # Node 의 키가 찾고자 하는 key 와 같다면 같은 key 를 가지고 있는 노드 반환
            elif v.key < key: # 현재 노드의 key 가 찾고자 하는 key 보다 작으면 
                p = v # p는 v의 부모가 된다
                v = v.right # 오른쪽 하위 노드로 이동
            else: # 현재 노드의 key 가 찾고자 하는 key 보다 크면
                p = v $ p 는 v의 부모가 된다.
                v = v.left # 왼쪽 하위 노드로 이동

        # key 값이 트리에 없다면 부모노드 반환
        return p

    # 반환값이 None 이 아니면 정상적으로 삽입
    def insert(self, key):
        p = self.find_loc(key) # 새로 삽입될 노드 위치의 부모노드가 반환된다 O(h)
        if p == None or p.key != key:
            v = Node(key)
            if p == None: # 애초에 트리 자체가 빈 트리
                self.root = v # 루트로 삽입된다.
            else: # 부모노드의 자식노드로 들어갈수 있다.
                v.parent = p
                if p.key >= key: # key 값이 부모 key 값 보다 작으면 
                    p.left = v # 부모의 왼쪽 하위노드로 링크
                else: # key 값이 부모 key 값 보다 크면 
                    p.right = v # 부모의 오른쪽 하위노드로 링크

            self.size += 1
            return v
        else:
            print("key is already included")
            return p # p = None


    def deleteByMerging(self, x):
        a = x.left, b = x.right
        pt = x.parent
        c # 노드 X 자리를 대체할 노드
        m # 노드 X의 왼쪽 자식노드의 자식노드중에 가장 오른쪽 노드

        if a != None:
            c = a
            m = a
            while m.right: # 계속 오른쪽으로 내려간다
                m = m.right

            if b != None:
                b.parent = m
                
            m.right = b
        else: # a == None
            c = b

        if pt != None: # 노드 x 의 부모노드가 있을때
            if c: c.parent = pt
            if pt.key < c.key:
                pt.right = c
            else:
                pt.left = c
        else: # pt == None 지워야할 노드가 root 노드
            self.root = c
            if c: c.parent = None

        self.size -= 1

    
    def deleteByCopying(self, x):
        a = x.left, b = x.right
        pt = x.parent
        c
        m

        if a != None: # a 가 있다면
            # m(a 의 가장 오른쪽 자식 노드) 을 찾는다
            m = a
            while m.right:
                m = m.right
            c = m # 기존의 x 자리(c)에 노드 m 을 넣는다 

            if m.left: # 노드 m의 왼쪽 자식 노드가 있다면
                a.right = m.left # 노드 m의 왼쪽 노드를 노드 a의 오른쪽으로 넣는다
            m.left = a # 노드 m의 왼쪽에는 노드 a
            m.right = b # 노드 m의 오른쪽에는 노드 b
        else:
            c = b
    
        if pt != None:
            if c: 
                c.parent = pt
            if pt.key < c.key:
                pt.right = c
            else:
                pt.left = c
        else:
            self.root = c
            if c:
                c.parent = None
    
    	self.size -= 1

 

수행시간

find_loc, insert, delete 의 수행시간은 모두 트리의 높이 (h) 에 영향을 받습니다. O(h)

 

 

Reference

https://www.youtube.com/watch?v=VVhmgQIJCu8&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=27

강의를 보며 정리하였습니다

 

'CS > 자료 구조' 카테고리의 다른 글

균형이진 트리 회전 ( rotation )  (0) 2022.03.05
이진트리 순회 ( Preorder, Inorder, Postorder )  (0) 2022.02.05
Heap tree ( Insert, find_max, delete_max )  (0) 2022.01.23
이진트리 [ 힙 ]  (0) 2022.01.08
이진트리 ( binary tree ) 표현법  (0) 2021.12.25
'CS/자료 구조' Related Articles more
Comments