RBtree 구현하는 방법은 잘 이해 됬는데
그 기저에 깔린 원리, 왜 색깔을 칠하는지에 대한 이해가 결여되어 있으니까
오래동안 기억이 유지가 될지는 잘 모르겠습니다.
이해를 할 만한 글이나 링크가 있습니까?
나는 원한다 지혜로운 도움 당신들
오래 살것이다 누구 나를 도운 사람들
항상 감사하십시오
RBtree 구현하는 방법은 잘 이해 됬는데
그 기저에 깔린 원리, 왜 색깔을 칠하는지에 대한 이해가 결여되어 있으니까
오래동안 기억이 유지가 될지는 잘 모르겠습니다.
이해를 할 만한 글이나 링크가 있습니까?
나는 원한다 지혜로운 도움 당신들
오래 살것이다 누구 나를 도운 사람들
항상 감사하십시오
루트부터 모든 리프노드까지 내려갔을때 검은 노드수가 비슷하도록 설계된거아님? 일케하면 리프노드까지 길이들의 편차가 크지않아서 평균수행시간에서 크게엇나가지않음 - dc App
검은 노드수는 항상 같다는건 알겠는데 색을 칠하는 이유?는 잘 모르겠음 AVL트리하고 차이점을 잘 몰르곘음
가장 이해가 안되는 건 왜 색을 칠하느냐? 임 색을 칠하는게 어떠한 의미를 갖길래?
AVL 트리의 경우에는 리프노드간의 높이 차이가 아무리 많아야 1밖에 허용이 되지 않도록 만들어서 회전 연산이 자주 발생함
RB 트리의 경우에는 리프 노드간의 높이 차이가 아무리 많이 나도 2배 이상 차이 나지 않게 해서 회전 연산의 횟수를 줄이는 것이 목적
아 무슨 뜻인지 알것 같음 색을 나눠서 관리를 하는거구나 적당히