[Java 자료구조] 여러가지 자료 구조 (2)

비선형 자료구조

트리 (Tree)

• 부모 노드와 자식 노드간의 연결로 이루어진 자료구조를 말한다.
• 트리 중에서도 프로그래밍에서 가장 많이 사용되는 트리는 이진트리이다. (자식 노드 개수 =< 2)
• 이진트리 중 child 개수가 꽉 찬 트리를 포화 이진 트리(Full Binary Tree)라고 한다.
• 루트 노드를 시작으로 왼쪽에서 오른쪽으로 채워나간 트리를 완전 이진 트리(Complete Binary Tree)라고 한다.

 

이진 트리로 구현하는 자료구조

1) 힙(Heap)

• 완전 이진 트리로 구현
• max heap : 부모 노드 값 >= 자식 노드 값
• min heap : 부모 노드 값 <= 자식 노드 값
• max heap 또는 min heap에서 요소를 하나씩 꺼내면 큰 값(or 작은 값)부터 출력되어 정렬된다. (heap sort)
• priority queue : 우선 순위 높은 element부터 꺼냄
• 자료의 중복은 허용됨

 

2) 이진 검색 트리(Binary Search Tree)

• 자료(key)의 중복을 허용하지 않는다.
• 부모 노드 기준으로 left subtree는 작은 값(큰 값), right subtree는 큰 값(작은 값)을 가진다.
• 자료 검색 시 한 단계마다 절반씩 범위가 줄어듦으로 검색 성능은 O(logn)이다.

• 최악의 경우(skewed-tree)에는 자료의 개수에 따라 검색 시간이 dependent하므로 검색 성능은 O(n)이다.
• 이를 방지하기 위해 AVL과 같이 스스로 밸런스를 유지해주도록 구현한다.
• traversal(순회) 방식에는 preorder, inorder, postorder 방식이 있다.
• inorder traversal 탐색을 하면 lchild → parent → rchild 순으로 출력되므로 sorting된다.

 

그래프 (Graph)

• vertex(정점)와 edge(간선)의 집합 G = (V,E)
• 간선은 방향성이 있는 경우와 없는 경우가 있다.
• 그래프를 구현 하는 방법 : 인접 행렬(adjacency matrix), 인접 리스트(adjacency list)
• 그래프를 탐색하는 방법 : BFS, DFS

 

해싱 (Hashing)

• 검색을 위한 자료구조
• 키(key)에 대한 자료를 검색하기 위한 사전(dictionary) 개념의 자료구조
• 유일한 key에 대한 value를 쌍으로 저장한다.
• key에 대한 index를 반환하기 위해 해시 함수를 이용한다. index = h(key)
• 되도록 유일한 index를 반환하는 것이 해시 충돌(hash collision)을 방지할 수 있으므로 좋다.
• 해시 함수를 이용하여 인덱스 연산이 산술적으로 가능하기 때문에 검색 속도가 빠르다. O(1)
• 해시 충돌이 발생했을 경우 데이터를 추가, 삽입, 검색하는데 시간이 소요될 수 있다.
• array 형태로 저장되는 해시 테이블, 인덱스 array와 그에 대응되는 value 값으로 저장되는 체이닝으로 구현할 수 있다.
• 해시 테이블은 배열 형태로 저장되기 때문에 메모리 낭비가 발생할 수 있고 체이닝은 구현은 복잡하지만 슬롯이 부족하거나 메모리 낭비가 되는 일은 없다.