이진 검색 트리

정의

모든 노드가 최대 두 개의 자식 노드를 가지고,

왼쪽 자식 노드는 현재 노드보다 작은 값을,

오른쪽 자식 노드는 현재 노드보다 큰 값을 가지도록 구성되어 있는 자료구조

구조

어떻게 값을 찾아가는 지?

어떤 특정값을 찾으려고 할 때,

한 노드와 비교해서 비교한 노드보다

작은 값이면 왼쪽 자식 노드 방향으로,

큰값이면 오른쪽 자식 노드 방향으로 이동.

특징

-비교 범위가 1/2씩 줄어들어서 자료 검색이 빠름

-어떤 기준으로 값의 크기를 비교할 것인지는 개발자가 직접 구현해야함.

오름차순

맨 왼쪽 노드 부터 시작해서

왼쪽 👉 부모 👉 오른쪽순으로 순회

내림차순

맨 오른쪽 노드 부터 시작해서

오른쪽 👉 부모 👉 왼쪽순으로 순회

23, 10, 48, 15, 7, 22 , 56을 이진 검색트리로 만들어 보기