트리(tree)

트리

: 부모-자식 관계의 노드들로 이루어지며 계층적인 구조를 나타내는 자료구조

부모는 여러 자식을 가질 수 있지만 자식은 하나의 부모를 갖는다.

이진트리는 각 노드가 최대 2개의 자식을 가지는 트리

위의 그림은 포화이진트리 구조이다.

모든 노드가 2개의 자식을 가지고 있다.

트리의 최상단 노드를 루트(root)라고 한다.

루트로부터 어떤 노드까지의 거리를 그 노드의 깊이(Depth)라 한다.

깊이가 같은 노드끼리의 집합을 레벨(level)이라 한다.

같은 부모를 가진 노드들을 형제(Sibling)노드라 한다.

트리의 표현

배열표현법 : 각 노드에 인덱스를 부여하여 배열에 저장하는 방법

링크표현법 : 다음 노드를 가리키는 포인터 변수를 이용하여 부모노드가 자식노드를 가리키는 방법

<배열표현법>

트리의 순서가 배열의 인덱스가 되어 1번부터 차례로 값이 들어간다.

배열 표기법은 트리 노드의 삽입 또는 삭제에 따라 배열의 크기를 동적으로 변경할 수 없다는 단점이 있다.

그리고 링크표현법에 비해 트리의 구조를 한눈에 알아보기가 힘들다.

<링크표현법>

각 노드는 왼쪽 자식을 가리키는 포인터, 오른쪽 자식을 가리키는 포인터, 데이터영역을 가진다.

만일 자식이 없다면  NULL로 표현

링크 표현법은 트리 노드의 삽입 또는 삭제에 따라 크기를 동적으로 변경할 수 있지만

배열표현법보다 코드가 복잡하다는 단점이 있다.

이진트리(Binary Tree)

: 각 노드가 최대 2개의 서브트리를 가지는 트리

public class Node {  //트리의 노드를 정의
    private int data; //데이터영역 data 변수
    private Node left; // 왼쪽 서브트리를 가리키는 left
    private Node right; // 오른쪽 서브트리를 가리키는 right
 
    public Node(int data) { //생성자를 통해 데이터값을 넣어준다.
        this.setData(data);
    }
 
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public Node getLeft() {
        return left;
    }
    public void setLeft(Node left) {
        this.left = left;
    }
    public Node getRight() {
        return right;
    }
    public void setRight(Node right) {
        this.right = right;
    }
}
public class BinaryTree{
 
    public static void main(String[] args) {
        // 노드 생성
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        
        // 트리에 노드 추가
        node1.setLeft(node2);
        node1.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
    }
}
 
 Colored by Color Scripter

<결과값>

이진탐색트리

이진탐색트리는 이진트리를 활용해 탐색작업을 효율적으로 하기 위한 자료구조

탐색 구조에서 탐색을 하기 위해서 찾을 자료를 식별할 수 있는 유일한 값을 키(key)라고 한다.

이진탐색에서는 저장할 데이터의 크기, 즉 키에 따라 노드의 위치를 정의한다.

그리고 이진탐색트리를 중위순회방법으로 순회하면 숫자 크기 순으로 정렬된다는 성질이 있다.

이진탐색트리의 정의

1. 모든 노드의 키는 유일하다.

2. 왼쪽 서브 트리의 원소의 키는 그 루트의 키보다 작다.

3. 오른쪽 서브트리의 원소의 키는 그 루트의 키보다 크다.

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

왼쪽 서브트리에 있는 값들(7,3,12)은 루트 노드인 18보다 작고

오른쪽 서브트리에 있는 값들(26,21,31)은 루트노드인 18보다 크다.

그리고 이진탐색트리를 중위순회방법으로 순회하면

(3-7-12-18-21-26-31)로 숫자들의 크기 순이 된다.

이진탐색트리의 탐색연산

이진탐색트리의 탐색연산은 루트노드부터 시작한다.

특정 키 값을 가진 노드를 찾기 위해서는 먼저 주어진 탐색 키 값과 현재 노드의 키 값을 비교한다.

비교한 결과가 같으면 탐색이 성공적으로 끝나고,

주어진 키 값이 루트 노드의 키 값보다 작으면 탐색은 왼쪽 자식을 기준으로 다시 시작.

주어진 키 값이 루트 노드의 키 값보다 크면 탐색은 오른쪽 자신을 기준으로 다시 시작한다.

public class BinarySearchTree{
    public Node root;
    public BinarySearchTree(){
        this.root = null;
    }
 
    //탐색 연산
    public boolean find(int id){
        Node current = root;
        while(current!=null){
            //현재 노드와 찾는 값이 같으면
            if(current.getData()==id){
                return true;
            //찾는 값이 현재 노드보다 작으면
            } else if(current.getData()>id){
                current = current.getLeft();
            //찾는 값이 현재 노드보다
            } else{
                current = current.getRight();
            }
        }
        return false;
    }
 
}
 
 

탐색연산을 코드로 구현하는 방법은 재귀함수를 이용하는 방법,반복문을 이용하는 방법 2가지가 있다.

반복문을 이용하는 방법이 효율성이 뛰어나다.

if(루트 == 키 값) 탐색성공

else if(루트>키값) 루트의 왼쪽 서브트리에 대해 탐색연산 수행

else if(루트<키값) 루트의 오른쪽 서브트리에 대해 탐색연산 수행

이진탐색트리의 삽입 연산

삽입연산은 원소를 삽입하기 위해서는 먼저 탐색을 수행해야 합니다.

1. 트리에서 삽입하려는 원소에 대해 탐색을 먼저 수행

2. 탐색이 성공하면 이미 같은 원소가 트리에 있으므로 종료

3. 탐색이 실패하면 탐색이 끝난 지점에 노드를 삽입

public class BinarySearchTree{
    public Node root;
    public BinarySearchTree(){
        this.root = null;
    }
 
    //삽입연산
    public void insert(int id){
        Node newNode = new Node(id);
        if(root==null){
            root = newNode;
            return;
        }
        Node current = root;
        Node parent = null;
        while(true){
            parent = current;
            if(id < current.getData()){
                current = current.getLeft();
                if(current==null){
                    parent.setLeft(newNode);
                    return;    
                }
            } else{
                current = current.getRight();
                if(current==null){
                    parent.setRight(newNode);
                    return;
                }
            }
        }
    }
 
}
 
 

newNode는 새로 삽입하려는 노드/parent는 현재위치로부터 루트노드

current는 현재 노드

current가 null이면 삽입

이진탐색트리의 삭제 연산

3가지 경우

case 1. 삭제하려는 노드가 단말 노드인 경우

case 2. 삭제하려는 노드가 한개의 서브 트리만 가지는 경우

case 3. 삭제하려는 노드가 두개의 서브 트리를 가지는 경우

case 1.

case 2

탐색 이후 자기 노드는 삭제하고 그 서브트리는 자기 노드의부모노드에 붙여주면 된다.

case 3

노드를 삭제한 후 부모 노드의 자리를 왼쪽에 물려줄지 오른쪽에 물려줄지 선택해야 한다.

이진탐색트리의 성질에 따라

왼쪽 서브트리중 가장 큰값 또는 오른쪽 서브트리의 가장 작은 값이 올수 있다.