[Data Structure] 이진 탐색 트리

35030 단어 알고리즘 자료구조 알고리즘

개념

이진 탐색 트리(Binary Search Tree)는 원소의 크기에 따라 노드의 위치를 정의한 것이고, 이진 트리 기반의 탐색을 위한 자료구조이다.

탐색할 때, 부모 노드의 값을 기준으로 작으면 왼쪽, 크면 오른쪽에 넣기 때문에 시간복잡도는 O(n)이다. 따라서, 이진 트리 구조에서 탐색할 때 효과적인 방법이다.

조건

모든 원소는 서로 다른 유일 키를 갖는다.
왼쪽 서브 트리에 있는 원소들의 키는 루트의 키보다 작다.
오른쪽 서브 트리에 있는 원소들의 키는 루트의 키보다 크다.
왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리이다.

트리의 노드

class Node:
    def __init__(self,data):
        self.data = data # 현재 노드의 값 
        self.left = None # 좌측 노드
        self.right = None # 우측 노드

삽입

트리의 특정 위치에 원소를 넣는 과정이다. 먼저 탐색을 수행하여 이진트리에 같은 원소가 있는지 확인하고 있다면 삽입하지 않는다. 만약 없다면, 탐색 실패가 발생한 위치에 원소를 삽입한다.

코드

# 삽입
def insert(self, data):
    # 트리의 루트 노드가 존재하는지 아닌지 판단
    if self.root is None:
        self.setRoot(data)  # 루트 노드가 없는 경우(제일 처음에 들어온 데이터가 루트 노드가 됨)
    else:
        self._insert_value(self.root, data)

def _insert_value(self, cur, data):
    # 부모 노드의 키보다 작으면 좌측, 크면 우측으로 보냄
    if data < cur.data:
        if cur.left:  # 이미 요소가 있다면 삽입 메서드 한번 더
            self._insert_value(cur.left, data)
        else:
            cur.left = Node(data)
    else:
        if cur.right:
            self._insert_value(cur.right, data)
        else:
            cur.right = Node(data)

탐색

루트 노드부터 기준으로 잡고 탐색 시작
비교
- 키 값과 기준 노드의 키 값 같을 경우
- 키 값이 기준 노드의 키 값 보다 작을 경우
  - 좌측 서브트리 탐색
- 키 값이 기준 노드의 키 값 보다 클 경우
  - 우측 서브트리 탐색

# 탐색
def find(self,data):
    if self._find_node(self.root,data):
        return True
    else:
        return False


def _find_node(self,cur,data):
    if cur is None:
        return False
    elif data == cur.data:
        return True
    elif data < cur.data:
        return self._find_node(cur.left,data)
    else:
        return self._find_node(cur.right,data)

삭제

삭제는 삽입과 삭제보다 고려해야 될 점이 많아 복잡하다. 왜냐하면 삭제 후에도 이진 탐색을 계속 유지해야하기 때문이다.

삭제할 노드를 기준으로

자식 노드가 없을 경우
해당 노드(삭제할 노드)를 삭제하고, 부모 노드에서도 정보(좌측,우측)를 지운다.
```
def remove(self)
```
자식 노드가 하나인 경우

해당 노드를 삭제하고, 자식 노드를 그 자리에 대신 넣으면 된다. 즉, 자식 노드를 할아버지 노드에 연결한다.
자식 노드가 둘인 경우

해당 노드를 삭제하고, 그 자리에 대신할 노드를 넣어야한다. 이 경우에는 직계 자식 노드뿐만 아니라 전체 자손 노드 중에서 후계자를 찾아야한다. 자리를 물려줘도 이진 탐색 트리가 유지되야 하는데, 자식 노드를 넣으면 이진 탐색 트리 구조가 깨질 수도 있기 때문이다.

후계자의 조건

왼쪽 서브트리에 있는 노드의 키 값 보다는 커야하고 오른쪽 서브트리에 있는 노드의 키 값 보다는 작아야한다.
- 왼쪽 서브트리에서 가장 큰 값
- 오른쪽 서브트리에서 가장 작은 값

# 삭제
def delete(self,data):
    self._delete_node(self.root,data) # 루트 노드부터 시작하므로 재귀를 시작해야하므로
def _delete_node(self,cur,data):
    if cur is None:
        return None
    elif data < cur.data:
        cur.left = self._delete_node(cur.left,data) # 왼쪽 자식 노드 정보 제거
        return cur
    elif data > cur.data:
        cur.right = self._delete_node(cur.right,data) # 오른쪽 자식 노드 정보 제거
        return cur
    else: # data == cur.data
        # Node to be removed has no children.
        if cur.left is None and cur.right is None:
            return None
        # Node to be removed has own children.
        elif cur.left is not None and cur.right is None:
            return cur.left
        elif cur.left is None and cur.right is not None:
            return cur.right
        # Node to be removed has two children.
        else:
            # 오른쪽 서브트리에서 가장 작은 값
            min_node = self._successor_node(cur.right)
            cur.data = min_node.data # cur.left 정보는 유지하기 위해 min_node.data만 가져옴
            self._delete_node(cur.right,min_node.data) # cur.right에는 이미 저장하고 있으므로 저장 안해도
            return cur
# 후계 노드 찾기
def _successor_node(self,cur):
    while cur.left is not None:
        cur = cur.left
    return cur

전체 코드

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


class BinarySearchTree(object):
    def __init__(self):
        self.root = None  # 트리의 루트 노드
        self.pre_order_lst = []  # 전위 순회 리스트
        self.post_order_lst = []  # 후위 순회 리스트

    # 루트 노드 설정
    def setRoot(self, data):
        self.root = Node(data)

    # 삽입
    def insert(self, data):
        # 트리의 루트 노드가 존재하는지 아닌지 판단
        if self.root is None:
            self.setRoot(data)  # 루트 노드가 없는 경우(제일 처음에 들어온 데이터가 루트 노드가 됨)
        else:
            self._insert_value(self.root, data)

    def _insert_value(self, cur, data):
        # 부모 노드의 키보다 작으면 좌측, 크면 우측으로 보냄
        if data < cur.data:
            if cur.left:  # 이미 요소가 있다면 삽입 메서드 한번 더
                self._insert_value(cur.left, data)
            else:
                cur.left = Node(data)
        else:
            if cur.right:
                self._insert_value(cur.right, data)
            else:
                cur.right = Node(data)


    # 탐색
    def find(self,data):
        if self._find_node(self.root,data):
            return True
        else:
            return False


    def _find_node(self,cur,data):
        if cur is None:
            return False
        elif data == cur.data:
            return True
        elif data < cur.data:
            return self._find_node(cur.left,data)
        else:
            return self._find_node(cur.right,data)

    # 삭제
    def delete(self,data):
        self._delete_node(self.root,data) # 루트 노드부터 시작하므로 재귀를 시작해야하므로

    def _delete_node(self,cur,data):
        if cur is None:
            return None
        elif data < cur.data:
            cur.left = self._delete_node(cur.left,data) # 왼쪽 자식 노드 정보 제거
            return cur
        elif data > cur.data:
            cur.right = self._delete_node(cur.right,data) # 오른쪽 자식 노드 정보 제거
            return cur
        else: # data == cur.data
            # Node to be removed has no children.
            if cur.left is None and cur.right is None:
                return None
            # Node to be removed has own children.
            elif cur.left is not None and cur.right is None:
                return cur.left
            elif cur.left is None and cur.right is not None:
                return cur.right
            # Node to be removed has two children.
            else:
                # 오른쪽 서브트리에서 가장 작은 값
                min_node = self._successor_node(cur.right)
                cur.data = min_node.data # cur.left 정보는 유지하기 위해 min_node.data만 가져옴
                self._delete_node(cur.right,min_node.data) # cur.right에는 이미 저장하고 있으므로 저장 안해도
                return cur

    # 후계 노드 찾기
    def _successor_node(self,cur):
        while cur.left is not None:
            cur = cur.left
        return cur


    # 전위 순회
    def _pre_order_traverse(self):
        if self.root is not None:  # 루트 노드가 존재한다면 탐색
            self._pre_order(self.root)

    def _pre_order(self, cur):
        self.pre_order_lst.append(cur.data)
        if cur.left is not None:
            self._pre_order(cur.left)
        if cur.right is not None:
            self._pre_order(cur.right)

    # 후위 순회
    def _post_order_traverse(self):
        if self.root is not None:
            self._post_order(self.root)

    def _post_order(self, cur):
        if cur.left is not None:
            self._post_order(cur.left)
        if cur.right is not None:
            self._post_order(cur.right)
        self.post_order_lst.append(cur.data)


arr = [11,10,13,12,15,14,16,17]
bst = BinarySearchTree()
for val in arr:
    bst.insert(val)

참고

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

https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/

https://comdoc.tistory.com/entry/20-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC%EC%99%80-%EC%9D%B4%EC%A7%84-%EA%B2%80%EC%83%89-%ED%8A%B8%EB%A6%AC3-%EC%82%AD%EC%A0%9C-%ED%8C%8C%EC%9D%B4%EC%8D%AC

Author And Source

이 문제에 관하여([Data Structure] 이진 탐색 트리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@psj8532/Data-Structure-이진-탐색-트리

우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)

Programmers / 21.03.11 오픈채팅방

[GO] #3-5. 패키지 탐방 (bytes)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다

[Data Structure] 이진 탐색 트리

개념

조건

트리의 노드

삽입

코드

탐색

삭제

후계자의 조건

전체 코드

참고

Author And Source

좋은 웹페이지 즐겨찾기