빡치게 사진도 안 올라가고 무한 글...되네..노션 아놔

📌이진트리?

트리의 각 부분의 명칭과 용어(나무위키!에서 긁어옴)

트리 ?

부모 노드 밑에 여러 자식 노드가 연결되고 다시 자식 노드가 연결되는 재귀적 형태의 자료구조. 그러나 자식 노드의 자식이 부모로 연결되는 경우는 트리로 인정하지 않음.

이진 트리

부모 노드 밑의 자식 노드 개수를 최대 2개로 제한하는 트리의 가장 간단한 형태.

보통 자식 트리를 서브 트리라고 하는데, 이 서브 트리는 공백이 될 수 있음.

https://kingpodo.tistory.com/27

위 트리를 해석… 해보자면 자식 트리가 없는 리프 노드는 D, H, F, I이며 노드 E와 G는 공백이 아닌 서브 트리를 하나씩 가지고 있다.

참고로 이진 트리에서

https://kingpodo.tistory.com/27

이런식으로 나오면 두 트리는 다른 트리이다.

이진 트리의 종류`

👇편향 이진트리(skewed binary tree)
노드가 한 쪽으로 몰린 트리. 모든 노드의 자식 노드는 하나임
👇포화 이진 트리(full binary tree) 2^(높이+1) -1 >> 높이 2인 포화 이진트리는 노드 개수가 7개임
노드 개수를 수학 공식으로 구하기 가능
모든 노드가 꽉 차있는 상태의 트리이다, 모든 트리의 자식 노드는 0개 or 2개이다 =
👇완전 이진 트리(comlete binary tree)포화 이진 트리와 비슷하게 왼쪽부터 번호가 매겨지지만, 끝 노드= 리프노드는 반드시 비어있어야 함. 3번 노드에 만약 자식이 생긴다면 완전 이진트리가 아님.

이진 트리의 연결 표현

: 그래서 이진 트리를 어케 표현하는가?

보통은 비선형 구조. 순서가 뒤죽박죽인 트리는 각각의 노드가 포인터를 가지고 구현된다.

그러나 완전 이진 트리는 왼쪽부터 빠짐없이 채워나가서 = 배열로 표현 가능함

👇 배열을 이용한 완전이진트리의 연결 표현https://kingpodo.tistory.com/27목표 노드 인덱스 값 조건

노드 x의 부모 [x/2] i > 1

노드 x의 왼쪽 자식 [2*x] 2*x≤n

노드 x의 오른쪽 자식 [2*(x+1)] (2*x+1)≤n

루트노드 [1] 0<n

0번째 인덱스는 사용하지 않아서 1부터 루트 노드가 시작된다.
: 비어있는 노드의 배열은 비워둔 채로 놔두면…. 이진트리 완성이다!
👇 비선형 구조의 이진 트리 연결 표현https://kingpodo.tistory.com/27
: 사진과 같으며, 이중 연결 리스트를 사용한다. 리프 노드들은 null 해주면 된다.

이진 트리 순회 방법

: 노드의 데이터를 처리하려면 트리를 한 번 순회함이 필요함. 트리의 데이터를 선형으로 만들거나, 데이터를 빼고 이동하기 위해서. 그럴 때 쓰는 순회 방법은 3가지다.

👇중위 순회(in -order traversal)
1. 자신의 왼쪽 자식 노드 > 자기자신 > 오른쪽 자식 노드 순으로 순회.
👇전위 순회(pre-order traversal)
1. 루트 노드 > 왼쪽 자식 트리 전위 순회 > 오른쪽 자식 트리 전위 순회
2. DFS가 생각나는데 전위순회나 후위순회는 DFS의 종류임
👇후위 순회(post-order traversal)
1. 왼쪽 자식 트리의 리프 노드 부터 후위 순회 > 오른쪽 자식 트리의 리프 노드 부터 후위 순회
👇레벨 순서 순회(level-order traversal)BFS가 생각나는데 맞음. 너비 우선 순회라고도 한다.

중위, 전위, 후위는 스택을 활용, 레벨 순서는 큐를 활용하여 구현 가능함

지금까지는 “이진 트리”에 대해 알아봤음

밑은 이진 트리의 일종인 트리들을 설명

이원 탐색 트리 (BST) ?

: 이진 트리의 일종.

노드의 왼쪽 가지에는 노드의 값보다 작은 값들만 있고, 오른쪽 가지엔 큰 값들만 있도록 구성됨

이렇게 구성해 두면 트리 자체가 이진 탐색을 하기에 적합한 구성이 됨. 값 탐색, 삽입, 삭제 모두 시간 복잡도가 O(logN)이 된다!

https://namu.wiki/w/트리(그래프)

BST외에도

AVL-tree(자가 균형 이진 탐색 트리- 이진 탐색 트리가 O(N)의 시간이 걸리는 최악의 경우 보완)
- 균형은 좋지만 삽입과 제거가 좀 느리고 탐색은 빠르다
Red-Black-tree(AVL의 일종)
- 노드에 색깔 속성이 붙음
- 최악의 상황에서도 탐색 삽입 삭제 모두 시간 복잡도가 O(logN)인 트리!
- 자세한건 https://en.wikipedia.org/wiki/Red –black_tree 참고
스레드 이진 트리
힙 트리
B-tree

…등 많다…

그럼!! 이제 코드로 이진탐색트리(BST)를 구현해보자

진짜 클래스의 생성자 뭐…이런거 복잡한 거 나도 아직 정확히 이해 안 돼서 안 쓰고 싶었는데 아무리 찾아도 예제가 다 똑같아서 어쩔 수 없이 ^^….복붙해서 해석만 해봄

from collections import deque

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

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

    def insert(self, val):
        self.root = self._insert(self.root, val)
        return self.root is not None

    def _insert(self, node, val):
        if node is None:
            return TreeNode(val)

        if val < node.val:
            node.left = self._insert(node.left, val)
        else:
            node.right = self._insert(node.right, val)

        return node

    def search(self, val):
        return self._search(self.root, val)

    def _search(self, node, val):
        if node is None or node.val == val:
            return node

        if val < node.val:
            return self._search(node.left, val)
        else:
            return self._search(node.right, val)

    def delete(self, val):
        self.root = self._delete(self.root, val)

    def _delete(self, node, val):
        if node is None:
            return None

        if val < node.val:
            node.left = self._delete(node.left, val)
        elif val > node.val:
            node.right = self._delete(node.right, val)
        else:
            if node.left is None:
                return node.right
            if node.right is None:
                return node.left

            node.val = BinarySearchTree._get_min_val(node.right)
            node.right = self._delete(node.right, node.val)

        return node

    @classmethod
    def _get_min_val(cls, node):
        min_val = node.val
        while node.left:
            min_val = node.left.val
            node = node.left
        return min_val

    def to_list(self):
        return self._to_list(self.root)

    def _to_list(self, node):
        if node is None:
            return []
        return self._to_list(node.left) + [node.val] + self._to_list(node.right)

    def print_by_ascending(self):
        self._inorder(self.root)

    def _preorder(self, node):
        if node:
            print(node.val, end=' ')
            self._inorder(node.left)
            self._inorder(node.right)

    def _inorder(self, node):
        if node:
            self._inorder(node.left)
            print(node.val, end=' ')
            self._inorder(node.right)

    def _postorder(self, node):
        if node:
            self._inorder(node.left)
            self._inorder(node.right)
            print(node.val, end=' ')

    def level_order(self, node):
        if node is None:
            return

        queue = deque()
        queue.append(node)

        level = 0
        while queue:
            values = []
            for _ in range(len(queue)):
                cur = queue.popleft()
                if cur:
                    values.append(cur.val)
                    queue.append(cur.left)
                    queue.append(cur.right)

            if values:
                print(f'level : {level}, values : {values}')

            level += 1

nums = [10, 3, 4, 11, 32, 21, 45, 8, 1, 18]

bst = BinarySearchTree()
for n in nums:
    bst.insert(n)

print('\\n\\n오름 차순 정렬 출력')
bst.print_by_ascending()

# Search
assert bst.search(10) is not None
assert bst.search(18) is not None
assert bst.search(100) is None

# Delete
bst.delete(10)
bst.delete(18)
assert bst.search(10) is None
assert bst.search(18) is None

print('\\n\\n오름 차순 정렬 출력')
bst.print_by_ascending()

print('\\n\\n레벨 오더 순회')
print(bst.level_order(bst.root))

print('\\n\\n이진 트리의 값을 오름 차순 정렬 리스트 자료구조로 반환')
print(bst.to_list())

BST를 이용한 전위 후위 중위 순회를 해보자

#노드 클래스
class Node:
    def __init__(self,val=0,left = None,right =None):
        self.val = val
        self.left = left
        self.right = right
def bst(list):
    if not list:
        return
    i = len(list)//2
    node =Node(list[i])
    node.left = bst(list[:i])
    node.right = bst(list[i+1:])
    return node
    
    
    
#전위순회
def preorder(node):
    if not node:
        return
    print(node.val)
    preorder(node.left)
    preorder(node.right)
    
#중위순회
def inorder(node):
    if not node:
        return
    inorder(node.left)
    print(node.val)
    inorder(node.right)

#후위순회
def postorder(node):
    if not node:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.val)
    
char_list = ['1','2','3','4','5','6','7','8','9']
my_node = bst(char_list)

#preorder(my_node)
#inorder(my_node)
postorder(my_node)

728x90

노드 x의 부모	[x/2]	i > 1
노드 x의 왼쪽 자식	[2*x]	2*x≤n
노드 x의 오른쪽 자식	[2*(x+1)]	(2*x+1)≤n
루트노드	[1]	0<n