반응형 redblacktree1 Red-black Tree 유명한 알고리즘인 Red Black Tree에 대해서 알아보자 복잡도는 다루지 않을 것이며 삽입 과정만 다루겠다 Red Black Tree를 이해하기 위해선 2-3-4 트리의 이해가 우선적으로 되어야지 조금 쉽다. 왜냐하면 2-3-4 트리의 단점을 극복하기 위해 제안된 것이 Red-Black Tree 이기 떄문이다. Red = 다수의 노드, black은 보통 이라고 임의로 정의한다 Red Black Tree는 3가지 핵심 규칙이 있다. 1. Root node는 모두 black이다. 2. Root에서 외부노드(끝)까지의 경로 상에는 연속된 2개의 Red node가 포함되지 않는다. 3. 루트에서 각 외부 노드까지의 경로에 있는 Black node의 수는 모두 같다. 그리고 Red-Black Tree는 Bi.. 2021. 10. 22. 이전 1 다음 반응형
