C++ Tree

Tree는 자료구조의 한 종류이며 계층관계를 표현할 때 많이 사용된다. 계층관계를 사용할 떄 용이함

Tree는 순회가 불가능 하다.

ex) 회사 조직도 ,폴더 구조 등

 

노드 : 1,2,3등등 객체가 노드

root : 부모가 없는 노드 트리의 맨위 1번노드

부모 : 자신보다 하위 노드를 가지고 있는 노드 1 2 3

자식 : 부모에 하위 노드 

리프(leaf) : 자식 노드를 가지고 있지 않는 노드 4 5 6 7

level : 루트부터 레벨 0 , 그 하위 단계를 레벨1, 점차 늘려감

 

이진트리 

자식에 갯수가 2개 이하인 트리

 

완전 이진트리

완전한 트리 형태를 가진 이진트리를 말한다. 보통 배열로 나타낸다.

 

배열의 자식은 2 * 인덱스 +1가 자식이다. 2k+1 예 1번 루트의 자식은  2*0 +1  인덱스 1에 있는 2가 자식

배열의 자식은 2 * 인덱스 +2가 자식이다. 2k+2 예 1번 루트의 자식은  2*0 +2  인덱스 2에 있는 3가 자식

이 된다. 

 

반대로 부모를 구하는 공식은 (인덱스 - 1) / 2의 몫이다. ex) 3의 부모는 (2-1)/2 = 0 3의 부모는 0이된다. 

이렇게 배열로 부모와 인덱스를 구할 수 있다.

 

 

이진 탐색 트리

B       S       T

Binart Search Tree

탐색을 위해서 만들어진 이진트리이다.

이진 탐색 트리는 배열에서 사용된다.

1~ 1000에 숫자가 있는데  100명에 사람들이 숫자를 랜덤으로 갖고 있다.  단 숫자는 순차적으로 갖고 있다. 만약 내가 225를 뽑은 사람을 찾고 싶은데 1번 부터 100명까지 찾는데 최악의 경우 100번째 사람이 225를 갖고있으면 100번 찾아야한다. 숫자가 많을 수록 더 많이 걸린다. 이럴 때 나오는 방식이 이진 탐색 트리이다.

배열의 중간 인덱스로 가서 인덱스이 값이 110이면 오른쪽에 있는것이고 그럼 나머지 50의 인덱스에서 또 중간으로 가서 값을 확인 후 330이면 왼쪽에 있고 남은 인덱스는 25개가 된다 이렇게 계속 중간으로 가서 값이 원하는 값이 나올 때 까지 찾는 방법이다 이렇게 하면 처음에 왼쪽에 있는 인덱스 50개를 안해도 된다. 이런 방식을 이진 탐색 트리라고 한다.

 

1. 데이터가 정렬 되어있어야한다. 순차적으로 되어 있어야함

2. 문제를 절반으로 탐색하는 방법

3. 최악인 경우는 log2(n)이다. log2(n)은 2가 몇승이 n의 값이 나오는가 

4. n의 값이 크면 클수록 효율이 늘어난다. ex)42억을 log2(42억)하면 값을 32번만에 찾을 수 있다.

5. 일반 백터는 최악인 경우 42억번을 찾아야 한다. 

6. 이진 탐색 트리는 log2(n) 알고리즘이라고 한다.

7. 데이터 입력시 O(logN) 효율

8. 탐색 효율은 O(logN) 효율

9. 트리의 모양이 밸런스가 유지되지 않으면 제대로 된 탐색 효율이 나오지 않는다. - 자가균형 기능 필요( AVL, Red/Blakc)

 

이진 탐색 트리는 루트부터 값을 비교해서 작으면 왼쪽으로 크면 오른쪽으로 값이 들어간다.

데이터를 넣을 때 비교하면서 넣어서 시간이 오래 걸린다. 하지만 그 단점이 무색할정도 탐색할 때 어마어마하게 빨라진다.

 

중위 순회 (inorder) : 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문

왼쪽자식->부모자식->오른쪽 자식

10 -> 20 -> 50 -> 70 ->100->200->300->400

전위 순회 (preodrder) : 뿌리(root)를 먼저 방문

부모->왼쪽자식->오른쪽 자식

100->50->20->10->70->300->200->400

후위 순회 (postoreder)  : 하위 트리 모두 방문 후 뿌리(root)를 방문

왼쪽자식->오른쪽 자식 -> 부모

10->20->70->50->200->400->300->100

 

이진 탐색 트리의 최악인 경우는 데이터가 순차적으로 들어가는 것이다.

ex)

그렇기에 최악의 상황을 방지하기 위해 self balanced(자가균형) 자가균형이 되는  레브 블랙 이진 탐색 트리를 구현 해줘야 한다. 자동으로 균형을 맞추어 준다.

출처 : https://www.youtube.com/c/AssortRockGameAcademy