이진 탐색 트리

트리(Tree)

가계도와 같이 계층적인 구조를 표현할 때 사용 할 수 있는 자료구조

 

루트 노드(root node) : 부모가 없는 최상위 노드

단말 노드(leaf node) : 자식이 없는 노드

 

트리 용어 정리

트리 부모와 자식 관계 성립

형제 관계 : 트리의 같은 레벨선상에 있는 노드들이 서로 형제

 

깊이(depth) : 루트 노드에서의 길이(length)

길이(length) : 출발 노드에서 목적지 노드까지 거쳐야 하는 간선의 수

높이(height) : 루트 노드에서 가장 깊은 노드 까지의 길이를 의미

 

이진 트리(Binary Tree)

최대 2개의 자식을 가질 수 있는 트리

 

이진 탐색 트리(Binary Search Tree)

다수의 데이터를 관리(조회, 저장, 삭제)하기 위한 가장 기본적인 자료구조

왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

 

이진 탐색 트리 삽입 연산

루트 노드에서 출발하여 아래쪽으로 내려오면서, 삽입할 위치를 찾는다.

삽입할 노드의 키가 작으면 왼쪽으로, 삽입할 노드의 키가 크면 오른쪽 삽입

 

이진 탐색 트리 삭제 연산

루트 노드에서 출발하여 아래쪽으로 내려오면서, 삭제할 원소에 접근한다.

 

트리의 순회(traversal)

트리의 모든 노드를 특정한 순서에 따라서 방문하는 방법

 

전위 순회 : 루트 > 왼쪽 자식 > 오른쪽 자식
중위 순회 : 왼쪽 자식 > 루트 > 오른쪽 자식
후위 순회 : 왼쪽 자식 > 오른쪽 자식 > 루트

 

편향 이진 트리

같은 높이의 이진 트리 중 최소 개수의 노드 개수를 가진다.

왼쪽 혹은 오른쪽으로 한방향에 대한 서브 트리를 가진다.