예전 블로그에서 HashMap 얘기를 진행하는데 Tree 내용을 언급된 바가 있었다.
자바 8부터 Seperate Chaining에서 데이터 개수가 많아지면 LinkedList대신 Tree(red black tree)를 사용해 성능적으로 더 좋아지게 하였다고 소개한 바가 있다.
즉, 처음에는 "해시 버킷"을 LinkedList로 하고 8개 이상의 키-값 쌍이 모이면 LinkedList(O(n))를 Tree(O(logN))구조로 바뀌게 된다. 만약 데이터가 삭제되어 버킷이 6개에 이르게 되면 다시 LinkedList 구조로 변경된다.
관련 블로그 : https://velog.io/@mooh2jj/Hash의-개념-및-설명
정리하면, HashMap은 key-value 쌍 데이터 개수가 일정 개수 이상이 되면, 해시 버킷의 수를 두배로 늘린다. 해시 버킷의 수를 늘려서 해시 충돌의 확률을 줄이는 것이다.
자, 그럼 대체 Tree가 무엇이길래 성능개선을 위해서 Tree가 언급되는 이유가 무엇일까?
Tree 란?
일단 트리(Tree)의 정의부터 보자.
Array, LinkedList, Stack, Queue와 같이 선형 개념의 자료구조가 아니라 부모-자식 개념을 가지는 비선형 개념의 Graph 자료구조의 일종이다.
비선형 자료구조는 하나의 자료 다음에 순차적으로 데이터가 나열되어 있는 것이 아니라 여러개의 자료가 존재할 수 있음을 의미한다.
Tree의 종류
이진트리 BinaryTree
트리(Tree) 중 이진트리(BinaryTree)는 컴퓨터 응용에서 가장 많이 활용되는 아주 중요한 트리구조이다.
이진트리의 중요한점은 왼쪽과 오른쪽 서브트리를 확실하게 구분한다는 것인데, 이진 트리는 모든 노드가 정확하게 두 개의 서브트리를 가지고 있다. 다만 서브트리는 공백이 될 수 있다.
노드의 유한 집합으로서 공백이거나 루트와 두 개의 분리된 이진트리인 경우 왼쪽서브트리와 오른쪽 서브트리로 구성된다.
편향 이진트리
Array 1차원 배열로 순차적으로 데이터를 쉽게 표현할 수 있지만, 편향 이진트리와 같은 데이터를 저장할 때에는 저장공간을 효율적으로 사용하지 못한다는 단점을 가지고 있다. (시간복잡도 O(n))
이진 탐색 트리
왼쪽 자식 노드 키 > 부모 노드 키 > 오른쪽 노드 키
시간복잡도: O(logn)
균형 이진 트리
편향 이진 트리로(선형화) 시간복잡도가 O(n)이 되는 것을 방지하기 위해
모든 노드의 왼쪽과 오른쪽 하위 트리의 높이가 최대 1만큼 차이가 날 수 있게 한 이진 트리.
종류: AVL(높이 균형 이진 탐색 트리), Red-Balck Tree, B-Tree 등
참고
