[Java] Binary Tree

Binary Tree는 트리를 통해 데이터를 비선형적으로 관리하는 자료구조이다.

앞서 포스팅에서 BST(Binary Search Tree)에 대해서 설명했는데 BST도 이진 트리를 기반한 자료구조이다.

 

왜 Binary Tree를 사용할까?

Tree Post에서도 설명했는데 일반 DAG와 같은 Tree는 효율성 측면에서 너무 부족하다. 그저 Graph와 다름이 없다.

그래서 실제 데이터 처리를 하기 위해 Binary Tree로 효율성을 극대화하는 방법을 채택한 것이다.

 

크게 Binary Tree의 두 종류를 알아보자.

 

1. 완전 이진 트리

2. 편향 트리 

이 외에도 많지만 Binary Tree의 핵심을 설명하기에 두 가지가 최고인 것 같다.

 

위 두가지 개념을 언급한 이유는 BST의 문제점 때문이다.

앞서 작성한 BST 코드에서 작은 값은 왼쪽, 큰 값은 오른쪽에서 sub tree를 생성하면서 잘 정리가 되어있었다.

편향트리

만약, 그림처럼 오름차순으로만 데이터를 입력한다면? 편향트리가 발생한다는 것이다.

데이터가 100만개가 오름차순일 때, Log_2(100만) 에서 선형탐색으로 바뀐다는 것이다.

약 50,000만 배 느려진다. 물론 데이터가 더 많아질수록 더 느려질 것이다. 이런 문제가 BST에서 발생한다는 것이다.

 

실제로 이것을 해결하기 위한 방법 중 하나가 완전 이진트리를 유지하는 것인데 왼쪽 사진에서 4를 지웠더니 완전 이진트리가 유지되지 않고 있다는 것이다. 이것을 해결하는 방법이 자가균형트리 (Self-Balancing Tree) 이며 대표적으로 Red-Black Tree, AVL Tree가 존재한다.

 

이 자가균형 트리를 이용한 것이 Java의 TreeSet과 TreeMap 인데 시간이 되면 한 번 작성해보자...

 

번외로 Binary Tree에는 문자열 검색을 위한 Trie, 최솟값과 최댓값 검색에 효율적인 Heap이라는 자료구조 또한 존재한다.