[Algorithm] Red Black Tree

레드 블랙 트리 (Red Black Tree)란? 레드블랙 트리는 지난번에 포스팅했던 트리에서 이어진다. 균형 이진 탐색 트리의 예시에서 레드블랙 트리를 언급했었고, 상당히 내용이 있는 이론이기 때문에 새로운 포스팅으로 옮겼다. 따라서 이진 탐색 트리에 대해서 안다고 가정하고 이어서 작성해보려고 한다. 특징 모든 노드는 빨간색 또는 검은색이다. 루트 노드는 검은색이다. 잎 노드는 검은색이다. (NIL 노드) 빨간 노드의 자식은 모두 검은색이다. (레드 노드는 연달아 나타날 수 없다.) 루트 노드에서 모든 잎 노드 사이에 존재하는 검은색 노드의 수는 모두 동일하다. 구현 탐색의 경우 기존의 BST와 동일하게 해주면 된다. 하지만 노드의 삽입과 삭제에서 문제가 발생한다. 트리의 균형이 유지가 안되기 때문이다..