Search
Duplicate

이진 탐색 트리(Binary Search Tree)

간단소개
이진 탐색 트리 간단 정리글
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
CS
자료구조
태그
자료구조
Scrap
8 more properties

이진 탐색 트리

탐색 작업을 효율적으로 하기 위한 자료구조
모든 원소는 서로 다른 유일한 키를 갖는다.
key(왼쪽 서브트리) < key(루트 노드) < key(오른쪽 서브트리)
왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리다.
중위 순회하면 오름차순으로 정렬된 값을 얻을 수 있다.
-이진 탐색 트리-

이진 탐색 트리 - 연산

탐색 연산

루트에서 시작한다.
탐색할 키 값 x를 루트 노드의 키 값과 비교한다.(키 값 x = 루트 노드의 키 값) : 원하는 원소를 찾았으므로 탐색연산 성공(키 값 x < 루트 노드의 키 값) : 루트 노드의 왼쪽 서브트리에 대해서 탐색연산 수행(키 값 x > 루트 노드의 키 값) : 루트 노드의 오른쪽 서브트리에 대해서 탐색연산 수행
서브트리에 대해서 순환적으로 탐색 연산을 반복한다.
-트리에서 13을 탐색하는 과정-

삽입 연산

먼저 탐색 연산을 수행삽입할 원소와 같은 원소가 트리에 있으면 삽입할 수 없으므로, 같은 원소가 트리에 있는지 탐색하여 확인한다.탐색에서 탐색 실패가 결정되면 위치가 삽입 위치가 된다.
탐색 실패한 위치에 원소를 삽입한다.
-5를 트리에 삽입하는 과정-