Tree

트리

0개 이상의 다른 노드에 대한 레퍼런스가 들어 있는 노드로 구성

한 노드를 참조하는 노드는 하나

노드는 구조체, 클래스로 표현

포인터 또는 레퍼런스만 있다면 어떤 언어로든 구현 가능

보통 노드의 공통적인 부분을 하나의 클래스로 정의하고 노드에 들어가는 데이터를 서브클래스를 만들어서 사용

public abstract class Node{
	private Node[] children;

	public Node(Node[] children){
    	this.children = children;
    }
    
    public int getNumChildren(){
    	return children.length;
    }
    
    public Node getChild(int index){
    	return children[index];
    }
}

public class IntNode extends Node{
	private int value;
    
    public IntNode(Node[] children. int value){
    super(children);
    this.value=value;
    }
    
    public int getValue(){
    return value;
    }
}

부모 : 다른 노드를 가리키는 노드는 그 노드의 부모가 된다.

자식 : 루트를 제외한 모든 노드는 그 노드를 가리키는 노드의 자식이 된다.

자손 : 특정 노드로 부터 자식노드로 이어지는 경로를 따라 도달 할 수 있는 모든 노드는 그 특정 노드의 자손이다.

조상 : 어떤 노드를 자손으로 삼고 있는 노드는 모두 그 노드의 조상이다.

잎 : 자식이 없는 노드를 잎이라고 부른다

 

이진트리

한 노드에 자식이 최대 두개 까지만 있을 수 있으며 그 두 자식은 각각 왼쪽 자식과 오른쪽 자식이라고 부른다.

//이진트리
public class Node{
	private Node left;
    private Node right;
    private int value;
    
    public Node(Node left,Node right,int value){
    	this.left = left;
        this.right = right;
        this.value =value;
    }
    
    public Node getLeft(){return left;}
    public Node getRight(){return right;}
    public int getValue(){return value;}
}

이진 검색 트리

노드의 왼쪽 자식의 값이 반드시 자신의 값이하이며, 오른쪽 자식의 값은 반드시 자신의 값 이사이앋.

데이터가 값으로 정렬된다.

어떤 노드의 왼쪽 방향의 자손들은 전부 그 노드 이하의 값을 가지며 오른쪽 자손들은 모두 그 노드 이상의 값을 가진다.

룩업연산을 빠르고 간단하게 처리 할 수 있다.

Node findNode(Node root, int value){
	while(root != null){
    	int currval = root.getValue();
        if( currval == value) break;
        if( currval < value){
        	root = root.getRight();
        }else { // currval > value
        	root = root.getLeft();
        }
    }
    return root;
}

힙

노드의 각 자식의 값은 노드 자신의 값 이하여야한다

루트노드의 값은 그 트리에서 가장 큰 값이며 최댓값을 상수 시간으로 구하는 것이 가능하다

삽입과 삭제는 O(log(n))

룩업은 O(n)

ex, 병원 응급실에서 대기 중인 환자들을 힙으로 모델링

우선순위 부여

 

일반적인 검색 방법

너비 우선 검색

O(n)

어떤 층을 검색할 때 그 층에 있는 모든 노드의 자식노드를 저장해둬야 하기 때문에 메모리도 꽤 사용한다

 

깊이 우선 검색

원하는 노드를 찾을 때까지 또는 끝에 다다를 때까지 한 가지를 따라 쭉 내려가는 방식

 

종주 (traversal)

방법에 따라 노드를 방문하는 순서가 달라진다

프리오더 종주 : 항상 노드를 자식들보다 먼저 방문

인오더 종주 : 왼쪽 서브트리를 먼저 방문하고 노드 자체를 방문한 다음 오른쪽 서브 트리 방문

포스트오더 종주 : 왼쪽자손 작업 수행 후 오른쪽자손 작업 마지막으로 그 노드 자체 처리

재귀호출로 구현