이진탐색트리 (BST)

이진 탐색 알고리즘

= 정렬된 데이터로 된 리스트에서 찾고자 하는 데이터가 있는지 알아보는 알고리즘 (리스트를 인수로 받음)

if 모든 요소 순회 -> O(n) !! 노답

이진 -> O(log n) !! 굳

 

방식: 중간값과 타깃을 비교 -> 중간값이 크면 좌측으로이동해서 또 중간값비교 이거계속

그래서 결국 중간값=타깃 되면 그 인덱스 리턴

*리스트는 정렬되어있다고 가정

 

이진 탐색 트리

(데이터 삽입,  삭제, 탐색 모두 빠른거 !!)

이진트리 -> 특별한 형태의 연결리스트. 부모는 두 자식의 참조를 가지고 있고, 자식은 부모의 참조를 가지고 있음

 

이진탐색트리는

노드에 데이터 직접 저장 x , 데이터에 대한 참조만 저장함

중요한 것은 데이터가 아니라, 이 데이터의 참조를 저장하고 있는 노드를 나타내는 키!

 

이진 탐색 트리의 정의

1. 모든 키는 유일
2. 어떤 노드를 특정했을 때, 이 노드의 키 값은 왼쪽 서브트리의 그 어떤 키보다 큼 (걍 한 키는 무조건 왼쪽보다 큼)
3. 어떤 노드를 특정했을 때, 이 노드의 키 값은 오른쪽 서브트리의 그 어떤 키보다 작음
4. (재귀적 정의) 노드의 서브트리도 이진탐색트리입니다 (당연)

< | < 이렇게 외우면 됩니다. 해당노드의 서브애들기준 < | < 이러캐 !!

 

함수들

•  prev : 해당 노드의 키보다 하나 작은거 찾는 함수

* 현재 노드가 왼쪽 자식이 없을 때, 부모의 오른쪽 자식이 현재노드입니다 = 부모노드가 현재노드의 이전노드다 !

(무조건 prev 요소임 ! 왜냐면 그부모노드< 현재노드&현재노드의 서브 , 현재노드<현재노드의 서브! (왼쪽자식없으니까) -> 부모<현재<현재서브! 당연 ~)

 

-왼쪽 자식이 잇다 -> 왼쪽자식에서 가장 큰애 골라오면 됨 (현재노드의 왼쪽애들은 다 현재노드보다 작으므로, 걍 max 함수 쓰면 됨)

-왼쪽 자식이 없다 -> 부모의 오른쪽자식이 현재노드면 그 부모가 prev ! 계속올라가면서 부모가 오른쪽 자식 갖을 때 그 부모 구하면됨

   -> while문은 부모의 left가 현재노드면 계속해서 올라가도록 함 !! 그러다가 right찾으면 while문 끝 !

 

• next : 그냥 prev 반대로 하면 됩니다