4 - BST(Binary Search Tree) Insert, InOrder, minValue

 

이진 탐색 트리에 대해 알아보겠습니다.

 

굉장히 많이 들어본 것 중에 하나입니다.

 

얘는 root 보다 작은애는 왼쪽, 큰 애는 오른쪽으로 보내줍니다.

 

[50,30,20,40,70,60,80]

 

만약에 이런 애가 있다고 하면

 

50을 root로 지정하고, root보다 작은 애는 왼쪽, 큰 애는 오른쪽으로 처리해줍니다.

 

 

 

자, 그렇다면 얘를 왜 쓰는가? 에 대한 의문입니다.

 

만약 80을 찾는다고 가정했을 때 초기 배열은

 

[50,30,20,40,70,60,80]

 

50 -> 80까지 전체를 훑어야 하는데, BST같은 경우는 

 

50 -> 70 -> 80 이렇게 가면 끝입니다. 훨씬 더 간단합니다.

 

때문에, BST를 씁니다.

 

탐색에 걸리는 시간 복잡도는 logN ~ N 입니다.

 

아래와 같은 경우가 최악의 경우입니다.

 

 

 

얘를 파이썬 코드로 구현해보겠습니다.

 

일단 Insert랑 Inorder(작은순서대로 출력), inValue(가장작은값 찾기) 부터 구현해보겠습니다.

 

 

와 같이 출력하면 결과값은 아래와 같이 나옵니다 :)

 

 

 

 

참조

[1] - https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/