Data Structure & Algorithm
3주차 - 재귀로 짜는 이진 트리 순회, 그리고 BST가 성능을 보장하는 이유
전위/중위/후위 순회를 재귀로 구현하며 결과 배열을 함수 밖에 두는 대신 중첩 함수로 감싸는 방법부터, 이진 트리 구조 자체는 탐색 성능을 보장하지 않는다는 것, 균형이 무너지면 O(log n)이 O(n)이 되는 이유, 캐시 지역성 때문에 DB가 이진 트리 대신 B+트리를 쓰는 이유까지.
이진트리
하나의 주제로 이어지는 배움의 기록.
2개의 기록 최신순
Data Structure & Algorithm
3주차 - 트리가 한쪽으로 쏠리는 것을 막는 균형 이진 트리, RB트리
BST가 데이터 쏠림으로 O(n)까지 느려질 수 있다는 문제에서 출발해서, RB트리의 색 규칙과 Black Height, 그리고 Rotation·Recoloring으로 Double Red를 복구하는 과정을 정리.