[파이썬] 이진 탐색 트리(Binary Search Tree) 직접 구현하기

  트리(Tree)는 Node와 Branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조로, 주로 최대 Branch 갯수가 2개인 이진 트리(Binary Tree)를 많이 사용한다.

트리(Tree)

 

  이진 탐색 트리(Binary Search Tree, BST)는 이진 트리인 동시에 왼쪽 자식 노드는 해당 노드보다 작은 값, 오른쪽 자식 노드는 해당 노드보다 큰 값을 가지는 특징을 지닌다. 이 자료구조는 데이터 검색 속도에 강점을 가진다.

이진 탐색 트리(Binary Search Tree)

< 이진 탐색 트리 구현하기 >

* 이진 탐색 트리의 시간 복잡도

  트리의 높이(Depth)를 ℎ 라고 한다면, 시간 복잡도는 O(ℎ) 이다. ℎ=𝑙𝑜𝑔𝑛 에 가까우므로, O(𝑙𝑜𝑔𝑛) 이라고 말할 수 있다.

하지만 아래와 같이 최악의 경우는 연결리스트(Linked List)와 동일한 성능을 보인다. ( O(n) )

이진 탐색 트리의 최악의 경우