어제는 좀 놀았고

오늘 다시 TIL시작하겠다

오늘은 RBTree 삽입 구현했다

여기 작성 시점에선 아직 구현 중이지만

금방 할듯 ㅇㅇ

현재 구현 상황은

RBTree의 회전하고 균형맞추기 구현해놨다

그리고 마지막에 트리 돌며 중위 순회 해야하는데…

스택, 큐 같은 거 만들어 할 수 있지만 그러기 싫고 피곤해

새로운 알고리즘 해봤다

Morris Traversal

모리스 순회

상당히 기가 막힌 방법이다

대강 요약 하자면…

트리에서 현재노드 cur 기록 하고 왼칸 이동, 가능 한 오른쪽 자식만큼 이동 하고

우측 자식이 NULL이나 끝이 되면 기록된 cur로 자식 연결 하고

cur에서 왼쪽 한 칸 이동하는 식으로 해서

그냥 왼쪽으로 쭉 내려가서 우측 자식만 따라가면 자연스레 중위 순회되게 하는 방법이다

이거랑 연동해서 배열 만들기도 했다