[Data Structure] HashMap 보다 Tree 를 써야 하는 곳에 대해 알아보면서 알게 된 내용들

[Data Structure] HashMap 보다 Tree 를 써야 하는 곳에 대해 알아보면서 알게 된 내용들

Wikipedia

https://brackece.wordpress.com/2012/09/18/hash-table-vs-binary-search-tree/

-

               F

       B              G

A           D             I

          C    E       H

Preorder(전위순회) or Depth-First Search (DFS, 깊이 우선순회)

    로직 : 노드 방문 -> 왼쪽 서브 트리 Preorder -> 오른쪽 서브 트리 Preorder

    ex) F -> B -> A -> D -> C -> E -> G -> I -> H

Inorder(중위 순회) or Symmetric Search

    로직 : 왼쪽 서브 트리 Inorder -> 노드 방문 -> 오른쪽 서브 트리 Inorder

    ex) A -> B -> C -> D -> E -> F -> G -> H -> I

Postorder(후위 순회)

    로직 : 왼쪽 서브 트리 Postorder -> 오른쪽 서브트리 Postorder -> 노드 방문

    ex) A -> C -> E -> D -> B -> H -> I -> G -> F

Level-order(레벨 순서 순회) or Breadth-First Search (BFS)

    Root 로부터 이웃을 먼저 찾아가며 Search 하는 방법

    ex) F -> B -> G -> A -> D -> I -> C -> E -> H

-

Array, LinkedList 와 같은 DS 는 Linear Data Structure 라고 부른다.

Tree 는 Hierarchical ( non-linear ) Data Structure 이다.

그래서 Tree 는 보통 hierarchy 가 있는 data 구조에 많이 쓰인다.

대표적인 녀석은 html 의 DOM 구조, file system 등이다.

-

Tree 는 Search 에 좋다. Binary Tree Search 의 경우 O(log N) 이다.

그래서 DBMS, 검색엔진 등에서 빠른 Search 를 위해 활용한다

B-TREE 는 노드의 삽입, 삭제후에도 균형 트리 유지로 균등한 응답속도를 보장한다.

그러나 삽입, 삭제시 트리의 균형을 유지하기 위해 재분배, 합병 등의 복잡한 연산이 필요하다. ( 이 과정이 없으면 한쪽으로 Tree 의 Height 가 커지면서 효율이 떨어질 수 있다, 균형잡힌 B-TREE 가 O(log N) 을 보장한다 )

-

<O(log N) 에 대한 이야기>

log N 은 divide and conquer 의 로직에 주로 적용된다.

(balanced) binary tree search ( BTS )  가 O(log n) 인데, BTS 케이스를 보면 이해하기 쉽다.

BTS 에서 node 가 2배 늘어났을 때 comparison 횟수가 2배가 늘어나는 것이 아니라 1회가 늘어난다. ( ex) 16개의 node 에서 32 개의 node 가 된 case 에 tree 의 depth 는 1개만 늘어나서 1회만 더 compare 하면 된다  )

다시 설명하면 n 이 exponentially 늘어날 때 time 이 linear 하게 늘어나는 케이스를 log N complexity 라고 이야기한다.

이것이 logarithm 의 개념과 맞아 log 로 표시하는 것이다.

참고로 O (n log n) 의 케이스는 quick sort 를 볼 수 있다.

quick sort 도 divide and conquer 정책을 사용하기 때문에 이 자체는 log n 이다.

그러나 log n 으로 선택된 부분에서의 정렬(sort) 자체는 O( n ) 이 걸리기 때문에 O (n log n) 이 된다.

-

HashMap 의 경우 hash function 을 사용해서 data 를 assign 해야할 장소를 지정해서 해당 장소에 값을 assign 한다.

만약 HashMap 의 사이즈가 100 이라면 hash function 은 0~99 값을 생성해서 값이 저장될 장소를 지정한다.

HashMap 의 사이즈가 적절히 선정된 경우에는 Insert, Lookup 은 O(1) 이다. ( Collision 이 별로 없는 경우 )

Collision 이 없는 경우 HashMap 의 O(1) 은 왠만해서는 O(log N) 보다 좋지만…

Collision 이 있는 경우는 이야기가 달라진다. Worst case 에는 O(n) 이 된다.

따라서 Tree 에 비해 HashMap 의 경우 Data 의 사이즈의 guessing 도 필요하다.

물론 실제 상용 HashMap 구현을 보면 Collision 이 많이 일어나면 HashMap 의 size up 을 시도하는데 이의 performance issue 도 무시할 순 없다. 기본적으로는 모든 element rehash 되어 reinsertion 이 되어야 하기 때문에 O(n) 의 time complexity 가 발생한다.

또한 Collision 이 없어도 HashMap 의 경우 Tree 보다 더 많은 Memory 를 소모할 수도 있다.

마지막으로 B-Tree 의 경우는 Sort 가 되어 있지만, HashMap 의 경우 Sorting 이 안 되어 있어. Sorting 관련 로직이 필요한 경우 Tree 더 빠를 수 있다.

-

HashMap vs. Tree 의 결론

메모리가 충분하며 Data 양 예측이 가능하며, 수정이 그렇게 많지 않은 경우에는 O(1) 의 search & insertion 을 보장하는 HashMap

그렇지 않다면 O( log N ) 의 Tree.

물론 이는 그렇게 Simple 하지는 않다. Hierarch 가 있는 Data Structure 를 표현해야 하는 경우라던지.. 

B-TREE, balanced binary tree search, BFS, binary tree search, breath first search, btree, BTS, DBMS, dbms tree, Depth-First Search, dfs, divide and conquert, exponentail data increase, file system, file system tree, hashmap collision, hashmap collision prevention, hashmap data size guessing, hashmap worst case, hierarchinal data structure, html dom tree, inorder, level order, linear data structure, log n, logarithm, logn, map vs tree, n log n, non-linear data structure, o log n, o n log n, postorder, preorder, Quick Sort, symmetricsearch, time linear increase, tree big o, Tree Example, tree search, wnddnl tnsghl, [Data Structure] HashMap 보다 Tree 를 써야 하는 곳에 대해 알아보면서 알게 된 내용들, 검색엔진, 균현 트리, 균형잡힌 btree, 깊이 우선순회, 노드 삽입 삭제, 레벨 순서 순회, 재분배, 전위 순회, 합병, 후위 순회