×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,312,121명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형




이진 탐색 트리의 경우 한 쪽으로 노드들이 쏠릴 수 있다.





이러한 불균형 트리구조 때문에 균형 잡는 방법을 생각하다가 만들어 진 것이 Red-Black Tree이다.


< Red-Black Tree의 조건>


1. root는 항상 블랙이어야 한다.

2. 블랙 밑에 블랙은 가능, 블랙 밑에 레드도 가능, 레드 밑에 블랙도 가능하다.


3. root는 블랙일 때, root 부터 leaf까지 경로가 있는데 내가 지나가는 블랙 노드의 개수는 항상 똑같아야 한다.

즉, root->leaf까지 가는 블랙 노드의 개수는 항상 같다.




(결국 이 말에서 유추할 수 있는 것은 제일 짧은 경로는 블랙으로만 이루어 진다는 것이고,

제일 긴 경로는 레드와 블랙으로 섞여있다. 하지만, root에서 leaf로 가는동안 블랙을 만나는 개수는 항상 같다.)





< Red-Black Tree의 특성>


1. 부모 노드가 black, 자식 노드 두개가 red인 경우 부모 노드는 red, 자식 노드가 black으로 바꿀 수 있다. (반대로도 가능하다.)

 

아래 그림은 상향 색변환이고,  반대로 할 시, 하향 색변환이라고 한다.





2. 다음과 같이 구성된 4가지 트리는 오른쪽과 같이 변형될 수 있다. 




반응형