[자료구조] Red Black Tree (레드 블랙 트리) | 레드 블랙 트리란, 경계 노드, black-height(흑색높이), Left-Rotate(좌회전), Right-Rotate(우회전), C언어 구현
레드 블랙 트리(Red Black Tree)는 이진 검색 트리의 한 종류이다. 이진 검색 트리가 무엇인지는 아래 문단에서 간단하게만 정리해두었으나, 이진검색트리의 순회나 노드의 삽입, 삭제 과정등을 전혀 모른다면 이진 검색트리를 먼저 공부한 후 레드 블랙트리를 공부하는 게 더 좋은 공부 순서일 것 같다! 💡 이진 검색 트리 이진트리의 한 종류. 각 노드들은 key, 부모 노드(p), 왼쪽 자식노드(left), 오른쪽 자식노드(right) 필드를 가지고 있고, 부모나 자식 노드가 없는 경우 각 필드는 NIL*값을 가진다. 부모가 없는 루트노드는 부모가 NIL인 유일한 노드이다. (*NIL이란 아무것도 없음을 뜻한다) 이진트리와 이진 검색 트리의 차이점은 모든 노드에서 왼쪽 자식은 부모노드보다 작거나 같고,..
2022. 10. 24.
