이진트리 변환방법 (스테픈 2km완료)
오늘은 자료구조를 듣네요
선택트리, 숲, 이진트리 개수에 대해서 나가는듯 한데요
사실 요즘 수업듣기보다 기출문제를 푸는걸 더 많이 하고있습니다.
결국 시험성적이 중요한 상황이라...
수업은 계속 듣다보니 어느사잉네가 50%를 넘어갔네요
문제는 그만큼 머리에 남아있는게 많지는 않다는점인데..
문제풀어보면 정말 하나도 모르겠다는게 느껴집니다
문제풀며 공부하는게 좀더 나은것 같아요
아마 알고리즘 수업을 나가면 배우는 내용인듯 하다.
합병 정렬 (Merge Sort)
합병 정렬은 분할 정복 알고리즘의 하나로,
배열이나 리스트를 작은 부분으로 나누고,
각각을 정렬한 후 병합하여 전체를 정렬하는 방식인데
코딩으로 구현했던 내용같긴 하다..
이런 순서로 진행되는데
분할: 배열을 절반으로 나눈다. 이 과정을 재귀적으로 배열의 크기가 1이 될 때까지 반복한다.
정복(정렬): 배열의 크기가 1인 경우는 이미 정렬된 상태이므로, 병합 과정을 통해 작은 배열들을 결합한다.
병합: 분할된 두 배열을 정렬된 상태로 합친다.
아마 내 기억으로는 재귀함수로 쪼개가면서 배열의 길이가 1 이하가 되면 종료시키는 탈출조건을 걸고
만들었던거로 기억한다.
선택 트리는 여러 개의 정렬된 리스트에서 가장 작은 값을 선택하는 데 특화되어 있으며,
이 과정에서 비교 횟수를 줄여준다.
승자트리는
구성전 단계를 좀 봐야 이해가 쉬운데
이런식으로 위로 하나씩 올라간다 치면
형제들끼리 비교해서
더 작은값이 위로 올라가게된다.
이런식으로 계속 비교해서 올라가는게 승자트리 구조이다
숲의 이진트리 구성도 조건이 정해져있다.
이런형태의 구조를
이진트리로 변경시키게되면
이진 트리에서는 각 노드가 왼쪽 자식과 오른쪽 자식만 가질 수 있으므로,
삼진 트리를 다음과 같은 규칙으로 바꿀 수 있습니다:
왼쪽 자식: 기존 트리의 왼쪽 첫 번째 자식.
오른쪽 자식: 나머지 형제 노드들.
- 변환 규칙:
A는 루트로 유지됩니다.
B는 A의 왼쪽 자식이 됩니다.
C는 B의 오른쪽 자식이 됩니다.
D는 C의 오른쪽 자식이 됩니다. - 이진 트리 구조:
A는 B를 왼쪽 자식으로,
B는 C를 오른쪽 자식으로,
C는 D를 오른쪽 자식으로 가집니다.
해당 방식대로 내리는 규칙을 적용하면 이런식으로 처리된다.
스테픈도 겨우 완성했다.
