170808(화) - 알고리즘 for Java (Tree)

알고리즘 for Java (Tree)

Tree

- 비선형적 데이터구조 (non-linear data structures)

- LinkedList와 비슷한 구조 But! 각 node가 여러개의 node를 가리킨다.

- 구조의 계층적 속성을 그래프의 형태로 나타내기 좋다.

- ADT(Abstract Data Type)에서 항목의 순서는 중요하지 않지만 순서 정보가 필요하다면 선형 데이터 구조 사용 가능

Terms

- Depth

root로부터 그 node 까지의 경로의 길이

- Height

node로부터 가장 깊은 node 까지의 길이

- 크기

자기 자신을 포함해서 그 node 가 가진 child node의 수

Skew tree

- tree의 모든  node가 오직 한개의 자식을 가짐

- left skew tree

- right skew tree

Binary tree

- strict binary tree

모든 노드가 2개의 자식을 가지거나 없음

- full binary tree

모든 노드가 2개의 자식을 가지고 leaf node가 같은 level에 있음

- complete binary tree

ㆍroot 부터 1로 시작해서 트리안의 노드 수까지 완전한 순열을 얻음

ㆍnull pointer에도 숫자를 매겨야 한다.

ㆍ모든 node가 높이 h나 h-1에 있고 순열에서 빠진 숫자가 없을 때

Attribute

- full binary tree 

ㆍnode 개수

- 각 레벨의 node를 다 더해야 한다.

-

- h는 level

ㆍleaf 개수

2h

- complete binary tree 

ㆍnode 개수

- (최소값) 와 (최대값) 사이에 있다.

ㆍnull 연결(낭비된 포인터) 개수

- n + 1

- n은 노드의 개수

Structure

class BinaryTreeNode {

int data;

class BinaryTreeNode *left;

class BinaryTreeNode *right;

};

Calculate

- basic

ㆍadded node

ㆍremove node

ㆍsearch node

ㆍtraversal tree

- Additional 

ㆍtree size

ㆍtree height

ㆍ최대의 합을가진 레벨 search

ㆍLCA : least common ancestor 찾기

Example

- 컴파일러

- 데이터 압축

- BST

- Priority Queue

Binary Tree Search

- Tree traversal

트리의 모든 node 방문

- LDR, LRD, DLR, DRL, RDL...

- D의 위치를 중심으로 본다면

ㆍPreorder : DLR 

// recursive way

// O(n)

void PreOrder(BinaryTreeNode root) {

if (root != null) {

Systemout.println(root.getData());

PreOrder(root.getLeft());

PreOrder(root.getRight());

}

}

// non-recursive way

// O(n)

void PreOrderNonRecursive(BinaryTreeNode root) {

if (root == null) return null;

LStack s = new LStack;

while(true) {

while(root != null) {

System.out.println(root.getData());

s.push(root);

root = root.getLeft();

}

if (s.isEmpty()) break;

root = (BinaryTreeNode) s.pop();

root = root.getRight();

}

}

시간복잡도가 좀 이상한데?

O(n^2) 아닌가?

ㆍInorder : LDR

- 깊이 우선 탐색(Depth First Traversal)의 영향

// recursive way

// O(n)

void InOrder(BinaryTreeNode root) {

if (root != null) {

InOrder(root.getLeft());

System.out.println(root.getData());

InOrder(root.getRight());

}

}

// non-recursive way

// O(n)

void InOrderNonRecursive(BinaryTreeNode root) {

if (root == null) return null;

IStack s = new IStack();

while(true) {

while(root != null) {

s.push(root);

root = root.getLeft();

}

if (stack.isEmpty()) break;

root = (BinaryTreeNode) s.pop();

System.out.println(root.getData());

root = root.getRight():

}

}

설마 stack empty일때 break 때문에 O(n)이라고 한건가?

ㆍPostorder: LRD

- node가 두번씩 방문된다.

- node가 left에서 온것인지, right에서 온것인지 구분해야 한다.

- pop 한 node와 stack의 최상의 node의 right가 같으면 right에서 온(처리 완료) 것.

// recursive way

// O(n)

void PostOrder(BinaryTreeNode root) {

if (root != null) {

PostOrder(root.getLeft());

postOrder(root.getRight());

System.out.println(root.getData());

}

}

// non-recursive way

// O(n)

void PostOrderNonRecursive(BinaryTreeNode root) {

if (root == null) return null;

PStack s = new PStack();

while(true) {

if (root != null) {

s.push(root);

root = root.getLeft();

} else {

if (s.isEmpty()) { 

return

} else {

// leaf node까지 내려옴

if (s.top().getRight() == null) {

root = s.pop();

System.out.println(root.getData());

while (!s.isEmpty() && root == s.top().getRight()) {

root = s.pop();

System.out.println(root.getData());

}

}

}

if (!s.isEmpty()) {

root = s.top().getRight();

} else {

root = null;

}

}

}

}

// recursive로 하자 괜히 객기 부리지말고

- Level Order Traversal

ㆍ너비우선탐색(Breadth First Traversal)의 영향

ㆍ레벨 I를 방문하는 동안 I + 1의 모든 항목을 큐에 저장

// O(n)

void LevelOrder(BinaryTreeNote root) {

BinaryTreeNode temp;

LQueue q = new LQueue();

if (root == null) return;

while (!q.isEmpty()) {

temp = q.deQueue();

System.out.println(temp.getData());

if (temp.getLeft() != null) {

q.enQueue(temp.getLeft());

}

if (temp.getRight() != null) {

q.enQueue(temp.getRitfht());

}

}

}