160108P(금)

자료구조 Chapter 10 - 트리

 

트리(tree)

비선형구조(non-linear structure)이다.

선형구조에 비해서 삽입과 삭제, 탐색이 O(logN)로 모두 빠르다.

 

선형 구조

배열

탐색 = O(logN)

삽입, 삭제 = O(N)

 

연결 리스트

탐색 = O(N)

삽입, 삭제 = O(logN)

 

트리의 일반적인 성질

1. 트리구조에서 한 노드에서 다른 노드로 가는 경로는 유일하다.

선택된 두 노드는 반드시 최소 공통 선조(least common ancestor)까지 올라갔다가 다시 다른 노드로 내려오는 유일한 경로만이 존재한다.

트리가 그래프(gragh)와 구별되는 중요한 성질이다.

 

2. N개의 노드를 갖는 트리를 N-1개의 링크(Edge)를 가진다.

여기서 -1은 루트를 의미한다.

 

이진트리(binary tree)

자식을 최대로 2개까지 가질 수 있는 트리구조

왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 크다.

이러한 성질을 이용해서 이진탐색을 시행한다.

 

완전 이진트리(complete binary tree)

마지막 레벨을 제외하고는 각 레벨의 노드들이 순서대로 꽉 차있고 마지막 레벨에서는 노드들이 순서대로 존재

 

꽉 찬 이진트리(full binary tree)

완전 이진트리에서 모든 레벨이 꽉 찬 이진트리

 

순회(traverse)

1. 전위순회(preorder traverse)

1. 노드방문

2. 왼쪽 하위트리 방문

3. 오른쪽 하위트리 방문

 

2. 중위순회(inorder traverse)

1. 왼쪽 하위트리 방문

2. 노드 방문

3. 오른쪽 하위트리 방문

 

3. 후위순회(postorder traverse)

1. 왼쪽 하위트리 방문

2. 오른쪽 하위트리 방문

3. 노드 방문

 

탐색(finding or searching)

current보다 작으면 왼쪽 자식으로, 크면 오른쪽 자식으로 탐색

 

최소값(minimum)

왼쪽 자식을 찾아 내려가면서 더이상 왼쪽 자식이 없는 노드

 

최대값(maximum)

오른쪽 자식을 찾아 내려가면서 더 이상 오른쪽 자식이 없는 노드

 

삽입(inserting)

노드가 삽입될 위치를 찾아야 삽입할 수 있다.

탐색 과정과 동일하지만 찾지 못했을 경우가 없다.

 

삽입을 위한 위치 탐색 중 마지막으로 만나는 null이 아닌 노드를 삽입하려는 노드가 가리키게 하는 것

 

삭제(deleting)

트리의 삭제는 상당히 복잡하다.

 

1. 삭제하려는 노드가 잎 노드일 때(자식 노드가 없음)

부모노드에서 현 노드를 가리키는 링크를 null로 만들면 된다.

garbage collection을 통해서 저절로 사라진다.

 

2. 삭제하려는 노드의 자식이 하나일 때

삭제 노드의 자식노드를 삭제노드의 부모노드와 이어주면 된다.

 

3. 삭제하려는 노드의 자식이 둘일 때

삭제될 노드의 위치를 채워줄 올바른 후보노드를 찾는것이 중요하다.

1. 삭제될 노드의 키 값보다 바로 위의 키 값을 가진 노드를 후보 노드로 선정

삭제될 노드의 오른쪽 하위트리중에서 가장 작은 값을 가진 노드

 

ㄱ. 후보노드가 삭제 노드의 오른쪽 자식일 경우

후보노드를 루트로 하는 하위트리를 삭제될 노드의 위치로 올리면 된다.

1. 부모노드에서 삭제노드에 대한 링크를 끊고 후보노드로 그 링크를 연결한다.

2. 삭제노드의 왼쪽 자식은 삭제노드와의 링크를 끊고 후보노드의 왼쪽 자식으로 링크를 연결한다.

 

 

ㄴ. 후보노드가 삭제 노드의 왼쪽 자식일 경우

1. 후보노드의 오른쪽 자식을 후보노드의 부모노드의 왼쪽 자식으로 만든다.

2. 삭제 노드의 오른쪽 자식을 후보노드의 오른쪽 자식으로 만든다.

3. 부모노드에서 삭제노드에 대한 링크를 끊고 후보노드로 그 링크를 연결한다.

4. 삭제노드의 왼쪽 자식은 삭제노드와의 링크를 끊고 후보노드의 왼쪽 자식으로 링크를 연결한다.

 

 

 

2. 삭제될 노드의 키 값보다 바로 아래의 키 값을 가진 노드를 후보 노드로 선정

삭제될 노드의 왼쪽 하위트리 중에서 가장 큰 값을 가진 노드

 

효율성

꽉 찬 트리

노드의 수 = N

레벨의 수 = L

 

N = 2^L - 1

2^L = N + 1

L = log⑵(N + 1)

 

= O(logN)

 

BinaryTree.java

class Node {

public int keyData;

 

public Node leftChild;

public Node rightChild;

 

public void showNode() {

System.out.print('[');

System.out.print(keyData);

System.out.print(']');

}

 

class BinaryTree {

private Node root;

 

public BinaryTree() {

root = null;

}

 

public void traverse(int type) {

switch(type) {

case 1: {

System.out.print("Preorder traversal : ");

preOrder(root);

 

break;

}

 

case 2: {

System.out.print("Inorder traversal : ");

inOrder(root);

 

break;

}

 

case 3: {

System.out.print("Postorder traversal : ");

postOrder(root);

 

break;

}

}

System.out.println();

}

 

private void preOrder(Node tempRoot) {

if(tempRoot != null) {

System.out.print(tempRoot.keyData + " ");

preOrder(tempRoot.leftChild);

preOrder(tempRoot.rightChild);

}

}

 

private void inOrder(Node tempRoot) {

if(tempRoot != null) {

inOrder(tempRoot.leftChild);

System.out.print(tempRoot.keyData + " ");

inOrder(tempRoot.rightChild);

}

}

 

private void postOrder(Node tempRoot) {

if(tempRoot != null) {

postOrder(tempRoot.leftChild);

postOrder(tempRoot.rightChild);

System.out.print(tempRoot.keyData + " ");

}

}

 

public void find(int key) {

Node current = root;

 

while(current.keyData != key) {

if(current == null) {

return null;

}

 

if(key < current.keyData) {

current = current.leftChile;

}

else {

current = current.rightChild;

}

}

return current;

}

 

public Node findMin() {

Node current = root;

 

while(current.leftChild != null) {

current = current.leftChild;

}

 

return current;

}

 

public Node findMax() {

Node current = root;

 

while(current.rightChild != null) {

current = current.rightChild;

}

 

return current;

}

 

public void insert(int key) {

Node insertNode = new Node();

insertNode.keyData = key;

 

if(root == null) {

root = insertNode;

}

else {

Node current = root;

Node parent;

 

while(true) {

parent = current;

 

if(key < current.keyData) {

current = current.leftChild;

 

if(current == null) {

parent.leftChild = insertNode;

 

return;

}

}

else {

current = current.rightChild;

 

if(current == null) {

parent.rightChild = insertNode;

 

return;

}

}

}

}

}

 

public boolean delete(int key) {

Node current = root;

Node parent = current;

 

while(current.keyData != key) {

if(current == null) {

return false;

}

 

parent = current;

if(key < current.keyData) {

current = current.leftChild;

}

else

current = current.rightChild;

}

 

// 자식이 없을 때

if(current.leftChild == null && current.rifhtChild == null) {

if(current == root) {

root = null;

}

else if(current == parent.leftChild) {

parent.leftChild = null;

}

else

parent.rightChild = null;

}

 

// 자식이 하나일 때

else if(current.rightChild == null) {

if(current == root)

root = current.leftChild;

else if(current == parent.leftChild)

parent.leftChild = current.leftChild;

else

parent.rightChild = current.leftChild;

}

else if(current.leftChild == null) {

if(current == root)

root = current.rightChild;

else if(current == parent.leftChild)

parent.leftChild = current.rightChild;

else

parent.rightChild = current.rightChild;

}

 

// 자식이 둘일 때

else {

Node candidate = getCandidate(current);

 

if(current == root) {

root = candidate;

}

else if(current == parent.leftChild) {

parent.leftChild = candidate;

}

else

parent.rightChild = candidate;

 

candidate.leftChild = current.leftChild;

}

 

return true;

}

 

private Node getCandidate(Node deleteNode) {

Node candidateParent = deleteNode;

Node candidate = candidateParent.rightChild;

 

// 삭제 노드 오른쪽 자식의 왼쪽 자식 찾기

while(candidate.leftChild != null) {

candidateParent = candidate;

candidate = candidate.leftChild;

}

 

// 후보노드가 삭제노드 오른쪽 자식의 왼쪽 자식일 때

if(candidate != deleteNode.rightChild) {

candidateParent.leftChild = candidate.rightChild;

candidate.rightChild = deleteNode.rightChild;

}

 

return candidate;

}

}

}