이진 탐색 트리 활용 상품 관리 프로그램

메뉴 -> 원하는 기능 선택

이진 탐색 트리 활용

 

기능

(1) 상품 등록 : 상품 번호와 상품명 입력하여 등록

(2) 상품 삭제 : 상품 번호 입력하여 그에 대응하는 상품 삭제

(3) 상품 검색 : 상품 번호 입력하여 그에 대응하는 상품명 출력 -> '상품 삭제 완료' 출력

(4) 전체 상품 조회 : 등록된 상품이 없을 경우 '등록된 상품이 없습니다.' 출력 / 있을 경우 '상품번호 상품명' 출력

(5) 종료 : '종료합니다.' 출력 후 프로그램 종료

 

구현 시 고려해야 할 이진 탐색 트리의 특징

컴퓨터의 탐색 = 레코드(Record)의 집합에서 특정한 레코드를 찾아내는 작업

레코드 : 하나 이상의 필드(Field)로 구성

레코드를 서로 구별하려면?

필드들 중에서 서로 중복되지 않는 고유한 값을 가지는 필드 활용 -> 이것이 바로 키(Key)

결국 탐색이란 주어진 키를 가진 레코드를 찾는 작업.

이진탐색트리에서는 레코드가 노드에 저장되고, 모든 노드는 유일한 키를 가짐.

이진 탐색 트리를 활용한 검색 기능의 목적 -> 주어진 키를 가진 노드를 찾기

 

모든 연산은 이진 탐색 트리의 조건을 유지하며 처리되어야 함

- 모든 노드는 유일한 키를 가진다.

- 왼쪽 서브 트리 키들은 루트 키보다 작고, 오른쪽 서브 트리 키들은 루트 키보다 크다.

- 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

 

<탐색>

탐색은 항상 루트 노드에서 시작.

루트 노드와의 비교 결과는 세 가지 중 하나

1. 키가 루트의 키값과 같으면 루트 = 찾는 노드 -> 탐색 성공

2. 키가 루트의 키값보다 작으면 찾는 노드는 왼쪽 서브 트리에 있음 -> 왼쪽 자식을 기준으로 다시 탐색 시작

3. 키가 루트의 키값보다 크면 찾는 노드는 오른쪽 서브 트리에 있음 -> 오른쪽 자식을 기준으로 다시 탐색 시작

 

<삽입>

이진 탐색 트리에서 노드 삽입을 위해서는 탐색 수행이 선행되어야 함

이유 : 이진 탐색 트리에서는 같은 키 값을 갖는 노드가 없어야 함 -> 탐색에 실패한 위치가 새로운 노드 삽입 위치가 됨

 

<삭제>

노드 삭제 후에도 이진 탐색 트리의 특성을 유지하도록 구현하는 것 중요

고려해야 할 3가지 경우

1. 단말 노드를 삭제하는 경우

2. 자식이 하나인 노드를 삭제하는 경우

3. 두 개의 자식을 모두 갖고 있는 노드를 삭제하려는 경우

 

(1) 단말 노드 삭제

단말 노드 -> 자식 노드가 없음 -> 해당 노드를 지우고 부모 노드의 링크 필드도 변경해줘야 함

 - 오른쪽에 위치한 단말 노드를 지우기 -> 그 부모 노드의 오른쪽 자식 링크를 NULL로 변경

 - 왼쪽에 위치한 단말 노드를 지우기 -> 그 부모 노드의 왼쪽 자식 링크를 NULL로 변경

= 어떠한 노드 삭제를 위해서는 기본적으로 부모 노드가 무엇인지도 알아야 함

 

(2) 자식이 하나인 노드의 삭제

자신을 삭제 + 유일한 자식을 부모 노드에 연결

고려할 사항

1. 삭제할 노드의 자식이 왼쪽 자식일 수도 있고 오른쪽 자식일 수도 있음

2. 삭제할 노드가 부모의 왼쪽 자식일 수도 있고 오른쪽 자식일 수도 있음

 

(3) 두 개의 자식을 모두 갖는 노드의 삭제

노드를 지우고 그 밑의 자식 노드를 끌어 오는 경우 자식 노드가 3개가 되는 경우 발생 가능 -> 더이상 이진 트리가 아님

1. 삭제할 노드를 대신할 적절한 후계자 노드를 찾는다

2. 후계자 노드는 삭제할 노드의 왼쪽 서브트리의 가장 오른쪽에 위치하거나, 오른쪽 서브트리의 가장 왼쪽에 위치

3. 노드를 삭제하는 대신, 후계자 노드를 삭제 위치로 복사 (링크가 아닌 데이터만을 복사)

4. 후계자로 사용한 노드를 삭제

(+) 후계자 노드는 지울 노드의 왼쪽 서브트리에서 가장 큰 값, 혹은 오른쪽 서브트리에서 가장 작은 값

     = 중위 순회 했을 때, 이 두 값들은 지울 노드 바로 전후에 위치함 -> 지울 노드의 키 값을 대체하는 데에 적합한 후계자 노드임

Node 클래스 구성

public class Node {
    int prdNo;
    String prdName;
    Node leftChild;
    Node rightChild;

    public Node(int prdNo, String prdName) {
        this.prdNo = prdNo;
        this.prdName = prdName;
        this.leftChild = null;
        this.rightChild = null;
    }
}