검색트리(Tree) - accidentlywoo/Java-Algorithm GitHub Wiki

검색 트리

트리와 이진트리

트리

계층적인 구조를 표현

조직도
디렉토리와 서브디렉토리 구조
가계도

트리는 노드(node)들과 노드들을 연결하는 링크(link)들로 구성됨

맨 위의 노드를 "루트(root)"라고 부름

노드들을 연결하는 선을 "link", "edge", "branch"등으로 부름

부모(parent) - 자식 관계(child) - 형제(sibling)

루트노드를 제외한 트리의 모든 노드들은 유일한 부모 노드를 가짐

리프노트가 아닌 노드들을 내부(internal)노드라고 부름

자식이 없는 노드들을 "leaf노드"라고 부름

부모 - 자식 관계를 확장한 것이 조상 - 자손(Ancestor-Descendant) 관계이다.

level과 height

트리의 기본적인 성질

노드가 N개인 트리는 항상 N-1개의 링크(Link)를 가진다.
트리에서 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의의 두 노드간의 경로도 유일하다. (같은 노드를 두 번 이상 방문하지 않는다는 조건하에).

이진 트리

이진 트리에서 각 노드는 최대 2갸의 자식을 가진다.

각각의 자식 노드는 자신이 부모의 왼쪽 자식인지 오른쪽 자식인지가 지정된다. (자식이 한 명인 경우에도)

부모의 자식의 방향이 구별이 된다. (자식의 같은 자식들이라도 왼오가 다르면 다른 트리)

ex) Expression Tree (x + y) * ((a + b) / c)

ex) Huffman Code 데이터 압축, 인코딩하는 가장 기본적인 알고리즘 : 파일을 인코딩했을때,최종적으로 파일의 길이가 최소가 되도록 압축하는 알고리즘

ex) Full and Complete Binary Trees

Full Binary Tree : 모든 이진트리가 할당

Complete Binart Tree : leaf노드가 아닌 노드는 모두 차있고, leaf노드는 왼쪽부터 채워져있어야 한다.

높이가 h인 full binary tree는 2^h-1개의 노드를 가진다.
노드가 N개인 full 혹은 complete 이진 트리의 높이는 O(logN)이다. (노드가 N개인 이진트리의 높이는 최악의 경우 N이 될 수 있다.)
연결구조(Linked Structure) 표현 각 노드에 하나의 데이터 필드와 왼쪽자식(left), 오른쪽 자식(right), 그리고 부모노드(p)의 주소를 저장 (부모노드의 주소는 반드시 필요한 경우가 아니면 보통 생략 함)

이진트리 순회 (traversal)

순회 : 이진 트리의 모든 노드를 방문하는 일
준순위(inorder) 순회
선순위(preorder) 순회
후순위(postorder) 순회
레벨오더(level-order) 순회

Inorder 순회 먼저 3등분 해서 recursive하게 탐색 -> 본질적으로 Recursive 하다

INORDER-TREE-WALK(x)
    if x != NULL
       then INORDER-TREE-WALK(left[x])
            print ket[x]
            INORDER-TREE-WALK(left[x])

x를 루트로 하는 트리를 inorder 순회

시간 복잡도 O(n)

LEVEL-ORDER-TREE-TRAVELSAL()
   visit the root;
   Q <- root;
   while Q is not empty do
      v <- dequeue(Q);
      viit children of v;
      enqueue children of v into Q;
   end.
end.

이진검색트리

Dynamic Set

여러개의 키(key)를 저장

다음과 같은 연산들을 지원하는 자료구조

INSERT - 새로운 키의 삽입
SEARCH - 키의 탐색
DELETE - 키의 삭제

ex) 심볼 테이블

called Dynamic Set, Dictionary or Search Structure

다양한 방법들

정렬된 혹은 정렬되지 않은 배열 혹은 연결 리스트를 사용할 경우

INSERT, SEARCH, DELETE 중 적어도 하나는 O(n)

이진탐색트리(Binary Search Tree), 레드-블랙 트리, AVL-트리등의 트리에 기반한 구조들
Direct Address Table, 해쉬 테이블 등

검색 트리

Dynamic set을 트리의 형태로 구현
일반적으로 SEARCH, INSERT, DELETE 연산이 트리의 높이(height)에 비례하는 시간복잡도를 가짐
이진검색트리(Binary Search Tree), 레드-블랙 트리(red-black tree), B-트리 등

이진검색트리(BST : Binary Search Tree)

이진 트리이면서
각 노드에 하나의 키를 저장
각 노드 v에 대해서 그 노드의 왼쪽 부트리(subtree)에 있는 키들은 key[v]보다 작서나 같고, 오른쪽 부트리에 있는 값은 크거나 같다.

TREE-SEARCH(x, k) //x -> 루트노드, k -> 찾는값
    if x = NULL or k = key[x]
        then return x
    if k < key[x]
        then return TREE-SEARCH(left[x], k)
        else return TREE-SEARCH(right[x], k)

시간복잡도 : O(h), 여기서 h는 트리의 높이

Iterative Version

ITERATIVE-TREE-SEARCH(x, k)
    while x != NULL and k != ket[x]
        do if k < key[x]
            then x <- left[x]
            else x <- right[x]
return x

시간복잡도 : O(h), 여기서 h는 트리의 높이