[Python] Tree/ Binary Tree/ Binary Search Tree의 개념

 

 

< Image 1 - 기본 트리 구조 >

 

1. 트리의 종류

 

•  트리(Tree)란?

   - Node와 Branch를 이용하여 사이클을 이루지 않도록 구성한 데이터 구조

   - <Image1> 에서 왼쪽 node 중 3과 6은 Siblings 관계이지만, branch로 이어질 수 없기 때문에 사이클이 이루어지지 않는 것이다.

 

• 이진 트리(Binary Tree)란?

    - Node의 최대 Branch가 2인 트리. 그 이상의 연결은 불가하다.

 

•  이진 탐색 트리란(Binary Search Tree)란?

    - 이진트리와 구성은 같으나, 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당노드와 값이 같거나 큰 값을 갖는 조건이 추가된 트리이다.

 

<Image2 - BST Process>

1. 먼저 21의 값을 가진 노드가 입력되어, ROOT NODE를 생성한다.

2. 다음으로 14의 값을 가진 노드가 입력되면, 14 < 21인 것을 확인 후, 왼쪽에 배치한다.

3. 다음으로 28의 값을 가진 노드가 입력되면, 28 > 21인 것을 확인 후, 오른쪽에 배치한다.

 

이와같은 과정으로 노드가 들어올 때 마다 크기에 따라 배치한다.

 

2. 이진 탐색 트리의 주요 용도와 장/단점

 - 주요 용도 : 데이터 검색(탐색)

 - 장점 : 탐색 속도 개선

 - 단점 : 복잡함

 

 

<Image3 - BST Merit>

입력된 데이터 중에서 27을 찾아야 할 때, BST와 배열의 탐색 과정을 비교해 보자.

 

- BST에서는 

   1. ROOT NODE인 21의 값 확인 --> 27이 더큼 ---> 오른쪽 Child Node 확인

   2. Child Node(Current Node)인 28의 값 확인 ---> 27이 작음 ---> 왼쪽 Child Node 확인

   3. Current Node인 25의 값 확인 ---> 27이 더 큼 ---> 오른쪽 Child Node 확인

   4. 27 찾음!

-----> 총 3단계로 '27'을 찾았음.

 

- 일반 정렬된 배열

   1. 가장 작은 값인 5부터 하나씩 확인

   2. 5 -> 11 -> 12 *** 27까지 총 10번을 확인하여 27까지 도달

-----> 만약 배열에 10,000까지의 수가 정렬되어 있고, 5700이라는 숫자를 찾아야 한다면,

         5700번의 단계를 걸쳐야 한다.

 

이러한 과정을 통해 BST가 데이터를 탐색하는 시간이 훨씬 짧다는 것을 알 수 있다.

 

 

 

 

 

출처: https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)

5 Gifs to Understand Binary Search Trees