트리(Tree)

트리(Tree)의 정의

: 트리는 계층적인 형태를 띄는 구조를 표현 할 때 쓰이는 자료구조이다.

트리의 용어

부모노드(Parent Node): 계층적구조에서 어느 한 노드의 바로 위의 노드를 부모노드라고 한다. 

자매,형제노드자매,형제노드(Sibling Node): 계층적구조에서 어느 한 노드의 아래로 연결된 노드를 자매,형제노드라고 한다. 

루트노드(Root Node) : 트리의 가장 위에 있는 원조노드를 말한다.

리프노드(Leaf Node) : 자식이 없는 노드를 리프노드라고 한다. 

터미널노드(Terminal Node) : 리프노드와 같다.(끝난다는 의미이다.)

일반트리(General Tree) : 둘 이상의 자식 노드를  가질 수 있는 트리를 말한다.

이진트리(Binary Tree) : 자식이 없거나, 최대 두개인 트리를 말한다.

트리의 레벨(Level) 

: 루트노드를 레벨 0으로 하고 아래로 내려오면서 증가한다. 

트리의 높이(Height)

: 트리의 최대 레벨 = 트리의 높이

포화이진트리(Full Binary Tree)

: 1) 리프노드의 위쪽 노드는 반드시 자식 노드 두개를 거느리고 있어야 한다. 2) 모든 노드의 왼쪽 자식의 높이와 오른쪽 자식의 높이는 같아야 한다.

완전이진트리(Complete Binary Tree)

: 레벨(높이-1)까지는 모든 노드들이 자식을 두 개로 다 채워야하고, 마지막 리프노드는 왼쪽에서 오른쪽으로 채워져 있는 트리를 말한다.

트리를 배열로 구현하는 방법(간략소개)

: 완전이진트리를 배열로써  표현 할 수 있다. 

다음과 같은 규칙으로 노드에 접근 할 수 있다.

루트노드를 기준으로 

n은 부모노드의 인덱스를 말한다.

왼쪽 자식에 접근하는 법 => (2n + 1)

오른쪽 자 식에 접근하는 법 => (2n + 2)

(2 * 0 + 1) => B [1]로써 0번인덱스노드의 왼쪽 자식노드에 접근

(2 * 0 + 2) => C [2]로써 0번인덱스노드의 오른쪽 자식노드에 접근

E에 접근하기 위해서는 ? 

=> (2*2 + 1) = 5인덱스로 접근하면 된다. 

D에 접근하기 위해서는 ?

=> (2*2 + 2) = 6인덱스로 접근하면 된다.

트리를 포인터로 구현하는 방법(간략소개)

: 노드를 데이터값, 다음왼쪽노드주소값, 다음오른쪽노드주소값 으로 구성한 후에 연결하면 된다.

트리를 배열로 표현할때와 포인터로 표현할때의 장단점?

=> 리스트와 비슷하다. 

[배열로 표현]

장점 : 인덱스로 접근하므로 굉장히 빠르게 접근이 가능하다.

단점 : 사용될 메모리를 미리 선언해야한다. 10000개의 노드를 사용하겠다고 선언해놨지만 100개밖에 사용하지 않는다면 낭비가 될 수 있다.

[리스트로 표현]

장점 : 사용될 메모리를 프로그램을 실행하면서 늘릴 수 있다. 메모리를 효율적으로 사용 할 수 있다.

단점 : 주소를 타고 타고 들어가야하므로 탐색성능은 배열에 비해 느리다.

스레드트리(Thread Tree)란?

이진탐색트리(Binary Search Tree)란?

이진탐색트리의 조건

1) 노드 N에 대하여 N의 왼쪽 하위트리는 N보다 작고, N의 오른쪽 하위트리는 N보다 크다.

2) 노드 N에 대해여 N의 왼쪽 하위트리와 오른쪽 하위트리 모두 이진탐색트리이다.

다음과 같은 트리가 이진탐색트리(Binary Search Tree)이다.

이진탐색트리의 탐색, 삽입, 삭제의 방법?

[탐색방법]

* 8을 찾고 싶다?

(1) 루트노드인 7보다 찾는 노드(8)가 크다 => 오른쪽 자식 노드로 진입

(2) 현재노드인 21보다 찾는 노드(8)가 작다. => 왼쪽 노드로 진입

(3) 현재노드인 8과 찾는 노드(8)가 같다! (찾음)

[삽입방법]

* 6을 삽입하고 싶다?

(1) 루트노드인 7보다 찾는 노드(6)가 작다 => 왼쪽 자식 노드로 진입

(2) 현재노드인 3보다 찾는 노드(6)가 크다 => 오른쪽 노드로 진입

(3) 현재노드인 5보다 찾는 노드(6)가 크다 => 오른쪽 노드로 진입

(4) 오른쪽 노드가 NULL이다. => 이 곳에 삽입

[삭제방법]

삭제하는 유형과정에는 크게 세 가지가 있다. 

[1] 삭제하려는 노드가 자식노드가 없다. => 그냥 삭제하면 된다.

[2] 삭제하려는 노드가 자식노드가 1개다. => 삭제하고 자식노드로 대체한다.

[2] 삭제하려는 노드가 자식노드가 2개다. => 삭제하고 왼쪽서브트리 중에서 가장 큰거 OR 오른쪽서브트리 중에서 가장 작은거를 선택해서 대체한다.

* 5를 지우고 싶다(자식노드가 없는 경우)

이진탐색을 통해 5를 찾는다. => 5를 그냥 삭제한다.

* 2를 지우고 싶다(자식노드가 1개인 경우)

이진탐색을 통해 2를 찾는다. => 2를 삭제하고 그 자식노드를 연결한다.

* 3을 지우고 싶다(자식노드가 2개인 경우)

이진탐색을 통해 3을 찾는다 

=> 오른쪽 서브 트리 중에서 가장 작은 수 OR 왼쪽 서브 트리 중에서 가장 큰 수를 선택 찾는다.

=> 3을 지우고 위에 선택된 수로 대체한다. 

=> 가장 작은 수 또는 가장 큰 수의 노드를 제거한다. 

* 6을 지우고 싶다(해당하는 노드가 없는 경우)

6을 탐색한다. 없다. 끝.

==> 이 부분은 실제 소스를 통해서 구현하면서 자잘한 부분에 대해서 설명하는 편이 낳을 것 같다.

 

이진탐색트리의 효율 및 최악의 케이스?

이진탐색트리는 보통 O(logN)의 시간효율을 갖는다. 

하지만 다음과 같은 경우(편향이진트리) 에는 O(N)시간이 걸린다.

편향이진트리 역시 이진트리이다. 자식을 두 개까지 가질 수 있는 트리이기 때문이다. 하지만 이건 트리가 아니라 리스트라고 할 수 있겠다.

편향이진트리에서 리프노드까지 5번이동해야 한다.

보통의 이진트리에서는 리프노드까지 logN의 이동만에 도달할 수 있는데에 비해서 정말 느린것이다.

그렇다면 O(logN)과 O(N)의 시간 차이가 그렇게 큰 것인가?

예를 들어 트리노드의 개수가 100,000개라고 쳐보자!

O(log100000) => 5

O(100000) => 100000

이렇게나 엄청난 차이가 난다.!!!