[CS스터디] Binary Search Tree

by VICENTE97P4

March 17, 2022, 2:31 p.m.

Tree

Tree는 노드들이 나뭇가지처럼 연결된 비선형 계층구조로, cycle이 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 의미합니다.

(비선형 자료구조는 데이터를 순차적으로 저장하지 않는 자료구조를 의미합니다.)

Tree 관련 용어

- Root node: 트리에서 최상위 노드

- Parent node: 노드 A가 노드 B를 가리킬 때 노드 A를 부모 노드(parent node)라고 합니다.

- Child node: 위 경우에서 노드 B를 자식 노드(child node)라고 합니다.

- child node는 parent node를 1개씩만 갖습니다.

- Sibling node: 같은 parent node를 갖는 노드

- Leaf node: 자식 노드가 없는 노드

- Internal node: leaf node가 아닌 노드

- Depth: 루트에서 어떤 노드까지 간선(edge) 수(Level 또한 같은 정의를 가질 수 있습니다.)

- Height: 어떤 노드에서 리프 노드까지 가장 긴 경로의 간선 수

- Distance: 두 노드 사이에 최단 경로에 있는 간선 수

- Degree: 노드의 자식 수

- Path: 한 노드에서 다른 노드에 이르는 길 사이에 놓여있는 노드들의 순서

- Forest: Tree가 여러개 모이면 Forest라고 합니다. tree에서 루트를 제거하면 forest가 됩니다.

중요한 부분은 아닌데, 이렇게 볼 수도 있다는 것을 공유하고 싶어 넣어봤습니다.

추가적으로, 노드가 n개인 트리는 반드시 n-1개의 간선을 가집니다.

- binary tree니까 당연히 자식은 최대 2개까지만 가질 수 있습니다.

- binary tree에서 level i는 최대 2^(i-1)개의 노드를 가질 수 있습니다.

- Full binary tree: 자식 수가 0개 또는 2개인 binary tree

- complete binary tree: 마지막 level을 제외하고 모든 level이 채워진 tree, level을 채울 때는 왼쪽부터 빠짐없이 채워야 합니다.

- complete binary tree의 depth는 ceil(log(n+1))(밑은 2)입니다.

위 그림은 complete binary tree이지만 full binary tree는 아닙니다.

Traverse

- In-order: 왼쪽 자식을 먼저 traverse, 현재 노드 visit, 오른쪽 자식 traverse

- Pre-order: 현재 노드 visit, 왼쪽 자식 traverse, 오른쪽 자식 traverse

- Post-order: 왼쪽 자식을 먼저 traverse, 오른쪽 자식 traverse, 현재 노드 visit

- Level-order: level 순으로 traverse

코드는 In-order iteration, level-order iteration만 적어보겠습니다. 

void iterInorder (Tree node) {
    Tree stack[MAX_SIZE];
    for (; ;) {
        for (; node; node = node -> leftChild) // 왼쪽으로 쭉~ 가면서 stack에 저장
            push(node);
        node = pop(); // 탐색 안 한 제일 왼쪽 값 pop
        if (!node) break; // 없으면 loop 탈출

        printf(“%d”, node -> data); // 방문 출력
        node = node -> rightChild; // 오른쪽 값 stack에 넣어줌
    }
}

void levelOrder (Tree ptr) {
    Tree queue[MAX];
    if (!ptr) return;
    addq(ptr);
    for (; ; ) {
        ptr = deleteq(); // 1개 뽑음

        if (ptr) {

            printf(“%d”, ptr->data); // 방문 출력

        if (ptr -> leftChild) // 왼쪽 자식 q에 넣음

            addq(ptr -> leftChild);

        if (ptr -> rightChild) // 오른쩍 자식 q에 넣음

            addq(ptr -> rightChild);

        }

        else break;

    }

}

Expression Tree

수식트리입니다.

수식을 트리로 만들었습니다.

leaf node는 피연산자, internal node는 연산자로 이루어져있습니다.

inorder, preorder, postorder 중 뭐로 traverse 하냐에 따라 중위, 전위, 후위 표기식이 나옵니다.

(threaded tree는 오버라고 판단하여 넣지 않았습니다.)

BST(Binary Search Tree)

이진 탐색과 연결 리스트를 결합한 자료구조입니다. 이진탐색의 효율적인 탐색능력을 유지하면서, 빈번한 자료 입력과 삭제가 가능하다는 장점이 있습니다. 

탐색, 삽입, 삭제의 시간복잡도는 O(h)(O(logn))입니다.

트리의 높이에 영향을 받는데, 트리가 균형이 맞지 않으면 워스트 케이스가 나올 수 있습니다.

그래서 균형을 맞추는 Tree로 AVL, RedBlack Tree가 있습니다.

Tree에 있는 모든 노드 X에 대하여

- X의 왼쪽 subtree에 있는 값들은 X의 값보다 작습니다.

- X의 오른쪽 subtree에 있는 값들은 X의 값보다 큽니다.

- 원칙적으로 같은 값을 갖는 노드가 생기는 것을 허용하지 않습니다.

find 코드
Node Find( ElementType X, SearchTree T )
{
    if ( T == NULL )
        return NULL;
    if ( X < T->Element ) // 찾으려는 값이 더 작은 경우
        return Find( X, T->Left );
    else if ( X > T->Element ) // 찾으려는 값이 더 큰 경우
        return Find( X, T->Right );
    else /* 찾은 경우 */
        return T;
}

Insert 코드

SearchTree Insert ( ElementType X, SearchTree T )
{
    if( T == NULL ) { // insert할 위치를 찾은 경우입니다.
        T = malloc( sizeof( struct TreeNode ) );
        if( T == NULL ) // 메모리 없을 경우인데 사실 없어도 됩니다!
            FatalError( “Out of space!!!” );
        else
        {
                T->Element = X;
                T->Left = T->Right = NULL;
        }
    } else if( X < T->Element ) { // insert할 값이 더 작을 경우입니다.
        T->Left = Insert( X, T->Left );
    } else if( X > T->Element ) // insert할 값이 더 클 경우입니다.
        T->Right = Insert( X, T->Right );
/* X가 이미 tree에 있는 경우는 아무런 동작도 하지 않습니다. */
    return T; /* 까먹지 맙시다! insert한 노드를 반환해줘야죠! */
}

delete

delete는 생각보다 까다롭습니다. 따져야 할 경우가 있어서 그렇죠.

1. 내가 지울 node가 자식이 없다면 편하게 그냥 지워주면 됩니다.

2. 자식이 1개라면 지우고 자식을 바로 이식해줍니다.

3. 자식이 2개인 경우가 골때립니다.

지울 노드의 바로 오른쪽 노드의 자식 중 제일 작은 값을 넣어주고 그 제일 작은 자식을 삭제해줍니다.

이 경우에는 왜 이렇게 복잡하냐면, 양 쪽 자식이 모두 살아있기 때문에 무작정 대체해줄 수 없기 때문입니다.

BST 특성을 맞춰줄 대체제를 찾아줘야 하기 때문입니다.

지워진 값과 가장 가까운 값으로 대체해줘야 BST가 깨지지 않기 때문이죠.

따라서 제일 오른쪽 자식의 제일 작은 값이 아니라 왼쪽 자식의 제일 큰 값을 넣어도 됩니다.

이건 정하기 나름이죠.

코드

SearchTree Delete( ElementType X, SearchTree T )
{
    Node TmpCell;
    if ( T == NULL )
        Error( “Element not found” ); // 지울 값을 못 찾은 경우입니다.
    else if ( X < T->Element ) // 지울 값이 더 작아 왼쪽으로 이동하는 경우입니다.
        T->Left = Delete( X, T->Left );
    else if ( X > T->Element ) // 지울 값이 더 커서 오른쪽으로 이동하는 경우입니다.
        T->Right = Delete( X, T->Right );
    else if ( T->Left && T->Right ) { // 삭제할 노드를 찾았는데 자식이 2개인 경우입니다.
        TmpCell = FindMin( T->Right ); // 오른쪽 자식 중 제일 작은 노드를 찾습니다.
        T->Element = TmpCell->Element; // 값을 이식합니다.
        T->Right = Delete( T->Element, T->Right ); // 제일 작은 노드를 삭제해줍시다.
    } else { // 자식이 1개 있거나 없는 경우입니다.
        TmpCell = T;
        if( T->Left == NULL ) // 지울 노드가 오른쪽 자식만 있거나 없는 경우입니다.
            T = T->Right;
        else if( T->Right == NULL ) // 지울 노드가 왼쪽 자식만 있는 경우입니다.
            T = T->Left;
        free(TmpCell); // 지워줍니다. JAVA나 PYTHON에서는 garbage collector가 있어 불필요합니다.
    }
    return T;
}

Tree 용례

- 컴퓨터의 directory 구조

• HTML DOM
  • document.body 도 객체이고, 이에 대해 사용할 수 있는 메서드가 있습니다. body의 child(하위 태그)는 document.body.children 을 통해 확인할 수 있습니다.

사실 개념보다는 화이트보드 손 코딩이 중요한 부분입니다.

왜 BST는 같은 값을 갖지 못하게 할까?

FindMax code 물어보기(iteration)

same tree 물어보기

Symmetric Tree 물어보기(https://leetcode.com/problems/symmetric-tree/)

어떤 이진 트리의 모양을 유지하면서 BST로 변환하기

이진트리 병합

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

class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if t1 and t2:
            node = TreeNode(t1.val + t2.val)
            node.left = self.mergeTrees(t1.left, t2.left)
            node.right = self.mergeTrees(t1.right, t2.right)

            return node
        else:
            return t1 or t2

Expression tree in-order traversal 의미 파악, 수식으로부터 ET 만들기