[Section2][자료구조/알고리즘] 자료구조 - Binary Search Tree

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

앞선 게시물 "2022. 07.26 - [Section2] [자료구조/알고리즘] 자료구조 - Tree" 을 통해 이진트리에 대해 알아보았다.

그럼 이번에 말하는 이진 탐색 트리는 도대체 뭐냐!

음, 사실 검색을 많이 해봐도 정식 문서를 보아도 명확하게 정의를 내려준곳은 아직 발견하지 못했다.

아니 힌트를 준곳을 하나 발견하였다.

그 관점에서 바라보고선 스스로 정리하여 답을 내려보았다.

 

일단, 이진트리란

1. 각 데이터는 노드의 형태를 가진다 (자신의 데이터와 하위 노드를 가질 수 있으므로)

2. 각 노드는 최대 2개의 하위 노드를 가질 수 있다.

3. 각 노드의 방향성은 하위로 뻗어 나간다. (루트로부터 역방향은 존재하지 않는다.)

 

이란 특징을 가지는 데이터 구조이다.

특징이 더 있을 수는 있지만, 대표적인(지금 기억나는것..)을 적어봤다.

즉, 그냥 데이터들이 존재하는 구조형태만을 말한것이다.

그러므로, 왼쪽 자식 노드는 루트 혹은 부모보다 작은 값이 와야하고,

오른쪽 자식 노드는 루트 혹은 부모보다 큰 값이 와야하는 그런 개념이 없다. 

말하자면.... 배열의 그냥 구조형태는 무엇인가?

같은 타입의 데이터가 [0][1][2][3][4] 그냥 이런식으로 순차적으로 존재하는 데이터 구조가 아니던가??

이진트리도 그냥 아래와 같이  개념으로 데이터들이 연결되어 있는 구조를 자체를 나타내는 명칭이고.

이진탐색트리란!!!!

이진트리에 데이터가 삽입될때 기준이 존재하는것이다.

그 기준은 다음과 같다

 

1.왼쪽 자식 노드가 부모 노드보다 작습니다 

2.오른쪽 자식 노드가 부모 노드보다 큽니다.

 

그래서 아래와 같은 트리 구조가 만들어지고 이것을 이진탐색트리라고 한다.

 

출처 : https://lowelllll.github.io/til/2018/11/17/TIL-BST/