24.03_Binary Search Tree_22.09.23

>Tree 구조 발전 과정

: 기존 트리는 편리한 구조로 저장할 순 있었지만, 특정 데이터를 검색하기 위해선 거의 모든 node를 순회하며 찾아야했음.

: 효율적인 탐색을 위해 만들어진 새로운 tree구조를 만들어 나감

>Tree 구조 종류

• 이진트리(Binary tree)

: 자식 노드가 최대 두 개인 트리

: 왼쪽 자식 노드, 오른쪽 자식 노드로 구분 가능

: 자료의 삽입, 삭제 방법에 따라 종류가 나뉨

• 정 이진 트리(Full binary tree)

: 각 노드의 자식 노드는 0개 혹은 2개인 트리

• 완전 이진 트리(Complete binary tree)

: 마지막 레벨을 제외하면, 모든 레벨에는 노드들이 가득 찬 트리

: 마지막 레벨의 노드는 왼쪽부터 채워짐

• 포화 이진 트리(Perfect binary tree)

: 정 이진 트리 + 완전 이진 트리

: 마지막 레벨(리프 노드 레벨)외에는 모든 레벨의 노드들이 가득 찬 트리

: 마지막 레벨(리프 노드 레벨)에서만 0개 혹은 2개의 노드로 구성

Binary Search Tree

>의미

: 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 지닌 트리 구조

: 정렬의 개념이 생김.

: 하지만, 값의 순서에 따라 한쪽으로 트리 구조가 몰릴 가능성이 있음. 알고리즘을 추가하여 이를 조정할 필요가 있음.

 

이진 탐색 트리 구현 클래스

>기초 : 이진 트리 구현 클래스 필요

>이진 트리 구현 클래스(Node)

필드1

: 노드의 값(data)저장 변수

필드2

: 노드 왼쪽 자식 주소 저장 변수

필드3

: 노드 오른쪽 자식 주소 저장 변수

생성자

: data만 받고, 필드2, 3은 null 할당

getter, setter

>이진 탐색 트리 구현 클래스

필드1

: Node형 값 저장 변수

생성자

: 매개변수 없이 필드1에 null 할당

insert

=>현재 노드, 왼쪽 자식 노드, 오른쪽 자식 노드의 값의 유무 및 대소 비교, 그리고 중복 여부를 통해 값을 추가하는 메서드

: 매개변수로 노드의 값(data)형의 값을 전달받고, 이를 인자로 한 newNode를 생성

: 현재 노드가 비어있다면, newNode를 할당

: 현재 노드의 값(data)와 인자의 값(data)이 일치하면 종료

: 현재 노드가 비어있지 않고, 중복 값도 아닌 경우 하위 노드 탐색

: currentNode와 parentNode를 임시로 생성 후, 각가 현재 노드의 주소와 null을 할당

: 무한 루프 반복문 생성

: parentNode에 currentNode를 할당

: 인자 값(data)이 currentNode의 값(data)보다 작을 때, 클 때로 조건을 나눔 (같은 경우는 위에서 해결됨)

: 작을 경우, currentNode의 왼쪽 자식 노드 주소를 currentNode 재할당 후, 재할당된 currentNode가 비어있으 parentNode의 왼쪽 자식 노드에 newNode를 지정함 (만약, 재할당된 currentNode의 값과 newNode의 값(data)이 같으면 종료)

: 클 경우, currentNode의 오른쪽 자식 노드 주소를 currentNode 재할당 후, 재할당된 currentNode가 비어있으면 parentNode의 오른쪽 자식 노드에 newNode를 지정함 (만약, 재할당된 currentNode의 값과 newNode의 값(data)이 같으면 종료)

contains

=> 이진 탐색 트리 노드에 해당 값의 존재 유무를 확인하는 메서드

: 현재 노드, 자식 노드 순으로 파악하며, 값의 크기로 방향을 정하기 때문에 효율적으로 찾을 수 있다.

: currentNode를 생성하여 contains를 호출한 노드(현재 노드)의 주소값을 할당

: currentNode이 null이라면, false반환

: currentNode이 null이 아니라면, 반복문 순회

: currentNode의 값(data)이 인자로 제공받은 값(data)와 같다면 true

: currentNode의 값(data)이 인자로 제공받은 값(data)보다 크다면, currentNode에 currentNode의 왼쪽 자식 노드 주소값을 할당 후 반복문으로 복귀

: currentNode의 값(data)이 인자로 제공받은 값(data)보다 작다면, currentNode에 currentNode의 오른쪽 자식 노드 주소값을 할당 후 반복문으로 복귀

 

>이진 탐색 트리 순회 메서드

전위 순회: [루트 - 왼쪽 자식 - 오른쪽 자식] 순으로 순회

중위 순회: [왼쪽 자식 - 루트 - 오른쪽 자식] 순으로 순회

후위 순회: [왼쪽 자식 - 오른쪽 자식 - 루트] 순으로 순회

참고 링크: https://withhamit.tistory.com/282