코멘트 하나 남깁니다~ * 매우 복잡해보이는 레드블랙트리를 최대한 이해하기 쉽게 설명한 영상입니다 - 1부 : ua-cam.com/video/2MdsebfJOyM/v-deo.html - 2부 : ua-cam.com/video/6drLl777k-E/v-deo.html (현재 영상)
RB tree 를 구현하는 과제를 진행중이였는데, 개념을 다지기 위해서 자료를 찾아보다 이런 고급 자료를 발견하게되다니 행운입니다! 2편을 걸쳐서 전부 봤는데, 복잡한 삽입, 삭제 예제를 그림으로 천천히 보여주면서 설명해주셔서 큰 도움이 되었습니다! 헷깔릴 때 마다 다시 와서 복습하면서 구현해봐야겠어요! 감사합니다!
우선 감사드립니다. 이런 멋진 영상을 올려주셔서요. 단순히 어느 조건에서 이렇게 해라 저렇게 해라라는 설명과는 비교가 안 되는 설명이고 레드블랙트리로 며칠을 씨름했는데 비로소 이 영상을 마지막으로 마음의 평화를 찾게 되었습니다 _ _) 영상 중에 18:19 에서 B와 D의 색을 바꿔준다는 게 이해가 안 갔습니다. extra black 를 개념과 17:00 에서 나오는 개념 등을 통해 근거를 두고 진행하시는데 색깔을 바꿔주는 데에는 아무 근거가 없는 것 같더라구요. 저 같은 사람이 있지 않을까 해서 댓글을 봤는데 저와 같은 부분에서 막힌 분은 없어보였습니다. 결국은 나름 이해를 하게 되어 저와 같은 분이 있을까 이해한 부분을 적어놓습니다. 18:19 에서 의아했던 게 red 를 왼쪽 서브 트리로 옮기는 게 '목적'인 건 알겠는데 근거는 알 수 없었습니다. 회전하기 전에 B 와 D 의 색을 서로 바꿔주면 B 의 윗쪽에서 B 를 거쳐 A 로 갈 때의 블랙의 개수와 B 의 윗쪽에서 B 를 거쳐 D 로 갈 때의 블랙의 개수가 달라져 버리니까요. 그런데 제가 이 부분에서 몰랐던 게, 'B 와 D 의 색을 서로 바꿔주는 것' 과 '회전' 을 별개로 봤었는데 B와 D의 색을 '바꿔 줘야만' 회전 후에도 레드블랙트리의 속성이 유지되는, 그러니까 두 노드의 색깔 바꾸기는 회전과 별개가 아니라 회전 과정의 일부였던 것이죠. 18:50 의 상태를 보면, 오른쪽 작은 그림은 회전 전의 그림이고, 왼쪽 큰 그림은 작은 그림에서 'B, D 의 색깔을 교환'한 후 회전 후를 나타낸 것인데, 우선 작은 그림의 속성 5 를 만족할 때 큰 그림도 속성 5를 만족하는지 알아야 합니다. '교환 후에' 회전을 했을 때 만족을 한다는 것을, '교환 하지 않으면' 만족하지 않는다는 것을 확인하기 위해서요. 작은 그림에서 i, j, p, q, x, y 에 들어있을 블랙 노드의 상대적인 개수를 보면, i, j 를 0 이라고 한다면, p, q, x, y, 는 1 이어야 합니다. A 에 블랙이 2개 있다면 레드인 D 를 거쳐가는 경우 2 를 만족해야 하는데 C 와 E 는 각각 블랙이 1이므로 p, q, x, y 어딘가에 블랙이 하나 더 있어야 하기 때문입니다. 이제 상대적인 크기이므로 알아보기 쉽게 p, q, x, y 를 1 로 두고, i, j 를 0 으로 두고 회전 후의 상태인 왼쪽 큰 그림을 보면 됩니다. 오른쪽 작은 그림에서 B + A + j = 파랑 + 2 + 0 = 파랑 + 2 이고, B + D + C + q = 파랑 + 0 + 1 + 1 = 파랑 + 2 B + D + E + x = 파랑 + 0 + 1 + 1 = 파랑 + 2 왼쪽 큰 그림에서 D + B + A + j = 파랑 + 0 + 2 + 0 = 파랑 + 2 D + B + C + p = 파랑 + 0 + 1 + 1 = 파랑 + 2 D + E + x = 파랑 + 1 + 1 = 파랑 + 2 가 됩니다. B, D 의 색깔을 교환하지 않고 회전을 했다면 왼쪽 큰 그림에서 B : 파랑, D 빨강일 테고, D + B + A + j = 빨강 + 파랑 + 2 + 0 = 0 + 파랑 + 2 = 파랑 + 2 D + B + C + p = 빨강 + 파랑 + 1 + 1 = 0 + 파랑 + 2 = 파랑 + 2 D + E + x = 빨강 + 1 + 0 = 0 + 1 = 1 이 되어 균형이 맞지 않게 됩니다. ∴ B 와 D 의 색깔 교환은 속성 5를 유지하기 위해 '회전' 전에 반드시 해야 하는 작업이며, '오른쪽 서브 트리의 레드를 왼쪽 서브 트리로 옮기려면 '회전'을 해 주면 됩니다.'
안녕하세요, 저도 이 부분에서 한참 고민하고 있었는데 덕분에 이해하는데 도움을 받았어요 감사합니다! 이 글을 읽고 생각해보니까 삽입 연산에서도 회전 전에 Grandparent와 Parent만 색을 교환하고 Uncle은 교환하지 않았었네요 삽입 연산 강좌 들을 때는 그냥 그렇구나 했었는데 ㅋㅋㅋ 여기서는 문득 왜 둘만 색을 교환하는건지 의문이 들었는데 회전 작업의 일부라고 이해하니까 일관성이 생기네요
저도 이 부분 갑자기 색을 바꿔도 괜찮나하면서 의문이 들었었는데 이렇게 글로 남겨주셔서 정말 정말 감사드립니다. 덕분에 이해했습니다. 이해를 해도 그걸 남들이 이해하기 쉽게 해당영상처럼만들거나 글로 쓰는게 진짜 쉽지 않은데 감사드립니다. 근데 마지막에 D+E+x에서 x의 상대적블랙이 1이므로 0 + 1 + 1 = 2가 되어야 할 것 같습니다. 아무쪼록 진짜 감사드립니다.
질문이 있습니다! 1. 인터넷에서 레드블랙트리 시뮬레이터의 경우 root node 삭제시 왼쪽에서 제일 큰 값을 root node로 선정하는데 선생님 코드는 오른쪽에서 제일 작은 값으로 선정하는 부분이 제가 생각했을 땐 방법의 차이일뿐 동작에 문제 없다고 생각하는데 맞을까요? 2.선생님이 delete 예제 하신것을 모두 수행했을때 결과가 동일하게 나오면 레드블랙트리를 제대로 구현했다고 생각해도 되는 걸까요? 예전에 선생님 영상을 보면서 레드블랙트리를 만들었는데 다시 확인해보니 문제가 좀 있어서 수정을 하였습니다. 결과적으로 delete 예제의 test예제는 모두 통과할수 있게 수정을 했는데 test 예제들을 모두 통과하면 문제 없이 구현된걸까요?
와 미친설명입니다. ㅋㅋㅋ 1부터 봤는데, 삽입/삭제시 해당 케이스에서 문제 해결을 어떻게 하려고 하는지 아이디어를 알려주셔서, 진짜 좋았네요@@!! 마지막 AVL 트리 비교 까지! AVL 트리 사례는 궁금해서 저도 찾아본 내용이었는데, 또 이렇게 똭! 떠먹여주시다니! 감사합니다. ㅎㅎ
@@ez. 공부하다가 이해가 잘 되지 않는 부분이 있어서 답글 남기게 됐어요! 18:02 에 등장하는 슬라이드에서 해당 트리 상태가 여전히 #5 속성을 만족한다고 말씀하셨는데, 이 부분에 대한 이해가 잘 되지 않아서 질문 드립니다! 저는 만족하지 않는 경우가 있다고 생각이들어서 이해가 되지 않았던 것 같은데, 예를 들어, B 노드가 루트 노드(=Black)이고, C 노드가 Black 인 경우 그리고 슬라이드에서 i, j, p, q, x, y 모두 nil 노드로 가정했을 때, B 노드 기준으로 리프 노드까지의 Black 노드 수를 카운트하면 나머지는 다 세 개씩 나오는데 B -> D -> E -> nil 경로에서는 두 개가 카운트돼서 #5 속성에 부합하지 않다고 생각이 들었어요! 만약에 나머지 조건이 같고, C 노드가 Red 인 경우에는 B -> D -> C (+extra black) -> nil = 2개 B -> D -> E -> nil = 2개 B -> A (+extra black) -> nil -> 3개 위 처럼 계산이 돼서 마찬가지로 #5 속성에 부합하지 않다고 생각이 들었습니다! 제가 뭔가 계산 과정에서 착오가 있는 것 같아서 앞뒤로 다시 한 번 들어봤는데 그래도 잘 이해가 되지 않아서 질문 남기게 됐습니다 ㅠㅠ ! 늘 좋은 자료 제공해주셔서 감사합니다!
@@devyun1954 오오 예리한 질문이십니다!! 자세히 답변 드려볼게요~ --- 질문주신 18:02 는 4번 case를 해결하는 와중에 나온 부분인데요 그래서 4번 case의 출발점인 15:19 로 돌아가 보겠습니다 사실 이 부분도 그림만 놓고 보면 5번 조건을 위반하는 것 처럼 보입니다 예를 들어 i, j, p, q, x, y 서브 트리가 모두 nil 노드라면, B에서 i, j로 갈 때의 경로와 x, y로 갈 때의 경로에서 블랙 수가 차이가 나니까요 하지만 실제로는 15:19 에서 5번 조건을 위반하는 경우는 존재하지 않는데요, 왜 그런지 설명드리면, case 1, 2, 3, 4는 black을 삭제 후 5번 조건을 다시 만족시키기 위해 extra black을 부여했더니 doubly black이 생긴 경우를 네 가지 케이스로 분류한 것이기 때문입니다 즉, case 1, 2, 3, 4는 5번 조건을 만족한 상태에서 시작합니다 헷갈릴 만한 포인트가 생긴 이유는, 5번 조건을 만족하고 있는 doubly black이 있는 트리를 네 가지 케이스로 일반화 시켜서 분류하다보니 서브트리로 표현하게 됐고, (그래서 B위에 화살표가 있는 것도 일반화 시켜서 표현하려다 보니 부모 노드가 있을 수 있다는 것을 나타내기 위해서 표기하게 된 것이고요,) 그러다 보니, 그림만 놓고 보면 5번 조건을 만족하지 않는 케이스도 있는 것처럼 보이기 때문인 것 같습니다 그래서 정리하자면 그림에서 서브트리로 표현된 부분은 '모든 가능한 레드-블랙 노드의 조합'을 의미하는 것이 아니라, '5번 조건을 만족하는 doubly black을 가진 트리의 서브트리들'이라고 봐야 합니다 애초에 5번 조건을 만족하고 있던 트리였는데, 그림만 놓고 보면 5번 조건을 만족하지 않는 케이스도 보이다 보니 헷갈리는 포인트가 생긴 것 같아요 (저도 처음 공부할 때 이것 때문에 헷갈렸어요 ㅠㅠ) 다시 처음 질문으로 돌아가서, 그렇다면 18:02 도 5번 조건을 만족합니다 왜냐하면 5번 조건을 만족하던 15:19 에서 출발해서 5번 조건을 위반하지 않도록 하면서 18:02의 형태까지 도달했기 때문이죠 --- 답변이 도움이 됐길 바라면서,, 항상 애청해 주시고 열심히 봐주셔서 정말 감사합니다!! 그리고 정말 멋지십니다!!!
영상 정말 잘 봤습니다. 정말 쉽게 설명해주시는 것 같아요. 과정을 따라가다보니 의문이 생겼습니다. 삭제되는 노드가 2개의 자식을 가질 경우, 그 successor는 우측 서브트리의 최솟값이 되는 노드이므로 이중흑색은 항상 그 위치를 대체하는 NIL에게만 부여된다고 이해했는데 이게 맞을까요? 핵심과 거리가 있는 질문이지만 궁금해서 남겨봅니다.
오, 생각해보니 그렇게 될 것 같아요 자녀가 두 개인 노드를 삭제할 경우, doubly black이 발생하려면 1. successor의 색이 black이고 2. successor의 위치에 올라온 친구도 black이어야 하는데, successor는 특성 상 자녀가 없거나 오른쪽 자녀만 있을거라서, - 자녀가 없다면 NIL 노드에 extra black이 부여가 될 거고, - 오른쪽 자녀가 있다면 successor의 오른쪽 자녀에게 extra black이 부여될텐데, 오른쪽 자녀의 색도 black인 경우는 NIL 노드 뿐이므로 (만약 오른쪽 자녀가 NIL노드가 아닌데 black이라면 트리가 이미 조건 5를 위반하고 있었다는 말이 되는데, 삭제하기 전 상태는 모든 조건을 만족하던 상태였으므로 이는 모순이 되기 때문) 결론은 '자녀가 두 개인 노드를 삭제할 때 doubly black이 발생한다면 항상 NIL 노드에서만 발생한다'고 볼 수 있겠네요
19:45에서 RB tree 5번 조건을 만족하지 않는 경우가 생기지 않나요? 만약 D와 C 모두 빨강색이면 D번 노드를 기준으로 i, j, p, q, x, y로 가는 경로에서 검은색 노드들의 갯수가 각각 2, 2, 1, 1, 1, 1이라서 5번 조건을 위반한 것이라고 생각됩니다
안녕하세요 :) 우선 결론부터 말씀드리면 5번 조건을 위반하지 않습니다. 왜 그런지 설명을 드리려다가, 사실 저도 공부할 때 비슷한 생각을 해본적이 있고 결국 무엇을 놓친 것인지 깨닫게 됐을 때 흥미롭고 기분이 좋았던 기억이 있어서, 그런 기분을 느낄만한 기회를 제가 빼앗으면 안되는 것 아닐까라는 생각이 들더라구요~ 그래서 혹시 괜찮으시다면, 왜 이게 5번 조건을 위반하지 않는지 그 답을 찾아보시겠어요? 첫번째 힌트는, 4번 case의 출발점인 15:20에서도 말씀하신 방법대로 접근한다면 5번 조건을 위반한다고 봐야합니다. 하지만 15:20도 5번 조건을 위반하지 않습니다. 15:20이 왜 5번 조건을 위반하지 않는 것인지 이해가 되시면 19:45도 왜 5번 조건을 위반하지 않은 것인지 이해가 되실 거예요 두번째 힌트는, extra black의 탄생 이유입니다. 세번째 힌트는, 5번 조건은 임의의 자손 'nil 노드'까지 가는 경로에서의 블랙 수를 확인합니다. 마지막으로 네번째 힌트는,, i, j, p, q, x, y는 노드가 아닙니다. 서브트리입니다. 혹시나 힌트 때문에 더 헷갈리셨다면,, 죄송합니다.. ㅠ 추가 설명이 혹시 필요하시면 댓글 남겨주세요
아무래도 드린 힌트가 오히려 방해가 된 것 같네요.. 죄송합니다 바로 답변을 드리겠습니다 만약 말씀하신 방식으로 접근을 하게 되면, 4번 case의 출발점인 15:20 또한 5번 조건 위반이라고 해석해야 합니다. 예를 들어 i, j, p, q, x, y 서브 트리가 모두 nil 노드라면, B에서 i, j로 갈 때의 경로와 x, y로 갈 때의 경로에서 블랙 수가 차이가 나니까요. 하지만 실제로는 5번 조건을 위반하는 경우는 존재하지 않습니다. 왜 그런지 설명드리면, case 1, 2, 3, 4는 black을 삭제 후 5번 조건을 다시 만족시키기 위해 extra black을 부여했더니 doubly black이 생긴 경우를 네 가지 케이스로 분류한 것이기 때문입니다. 즉, 5번 조건은 이미 만족하고 있습니다. 5번 조건을 만족하고 있는 doubly black이 있는 트리를 네 가지 케이스로 일반화 시켜서 분류하다보니 서브트리로 표현하게 된 것이고, B위에 화살표가 있는 것도 일반화 시켜서 표현하다보니 부모 노드가 있을 수 있다는 것을 나타내기 위함인 것입니다. 그러므로 서브트리로 표현된 부분은 '모든 가능한 레드-블랙 노드의 조합'을 의미하는 것이 아닙니다. 이 서브트리들은 '5번 조건을 만족하고 있는 doubly black을 가진 트리의 서브트리들'을 의미합니다. 애초에 5번 조건을 만족하고 있던 트리였는데, 서브트리에 5번 조건을 만족하지 않는 케이스를 골라서 생각했기 때문에 헷갈리는 포인트가 생긴 것입니다. 같은 이유로 19:45도 5번 조건을 만족합니다. 애초에 5번 조건을 만족하던 15:20에서 출발해서 5번 조건을 위반하지 않도록 하면서 19:45의 형태로 도달했기 때문입니다.
우선 정말 쉬운 설명에 감탄하고 감사합니다. 알고리즘 공부를 시작한지 얼마 되지 않아 아직 궁금한 점이 많습니다. 다름이 아니라 레드 블랙 트리 구현 중 궁금한 것이 생겨 간단한 질문 드리는데 노드를 구현할 때 노드가 멤버 변수로 닐 노드 두 개를 기본적으로 모두 들고 있게 구현 하는 것이 일반적인가요?? 만약 그렇다면 닐 노드는 다른 노드와 비교하여 그저 데이터 값만 가지고 있지 않으면 되는 것인지요 또한 만약 힙 영역에 할당한다면 유효한 데이터 값 생성 시 그 자식인 닐 노드 또한 할당은 하되 데이터를 가지고 있지 않은 것인지 궁금하여 질문 드립니다! 구현 부분에 대하여 질문드려 죄송합니다 ㅠㅠ
개념적으로 설명을 드리면 레드블랙트리는 닐 노드가 중요한 역할을 하기 때문에 기본적으로 닐 노드는 유효한 값을 가지지 않는 노드로 존재해야 합니다 '일반적으로' 구현을 어떻게 하는지에 대한 부분은 저도 여러 구현을 본 것은 아니기 때문에 답변드리기는 조금 어렵고요, 대신 nil 노드를 매번 생성하면 메모리 낭비가 있으니, 어차피 닐 노드는 특징이 모두 같으니까 닐 노드 용도로 쓸 노드 하나를 만들고 모든 닐 노드는 그 하나의 닐 노드를 공유해서 쓰는 형태로 사용했던 것 같습니다~
22:00 분 그래프의 상태를 보면 노드 D의 black height가 속성 5를 위반하는거 아닌가요?, 설명이 틀린것 같습니다. "회전 이전의 상태" 를 보면 노드D black height를 k라고 할때, 서브트리 p, q, x, y 내부의 블랙 노드의 개수는 k-1 입니다. 그런데. 회전하고 D노드는 왼쪽 서브트리 q의 내부 블랙 노드의 개수는 k-1 보다 오른쪽 서브트리가 블랙노드가 k개이며, 1개 더 많습니다. 속성 5를 위배합니다.
회전 이전 상태(21:29)이 속성5를 만족한다고 한다고 했을 때, i, j, p, q, x, y 끼리의 상대적인 블랙 노드 개수를 확인해 보면 p, q 는 i, j, x, y 보다 내부 블랙 노드의 개수가 하나 많아야 합니다. 빨강인 C 를 거쳐서 지나갔는데도 속성 5를 만족하니까요. 상대적인 개수이므로 간단하게 q 를 +1, x 와 y 를 0 으로 두고, 회전한 후의 D 의 좌우 서브 트리를 보면 D 의 왼쪽 서브 트리 = C + q = 0 + 1 과 D 의 오른쪽 서브 트리 = C + E + (x or y) = 0 + 1 + 0 이 되어 양쪽 black-height 는 일치하게 됩니다.
크~~! 유익하게 봐주셔서 감사합니다 :) 질문주신 22:20은 case4번을 적용할 수 있는 상황이 됐기 때문에 case4번을 해결하는 방식으로 해결하는 순간이에요 그래서 핵심은 '왜 B와 D를 black으로 바꿔주느냐' 일텐데요, 요 내용은 case4번 설명(15:19)을 자세히 보시면 이해하실 수 있을 것 같아요~ 글로 쓰려니까 글 만으로는 설명에 한계가 있을 것 같고, 영상과 같이 설명을 들으시는게 더 쉽게 이해하실 수 있을 것 같아서 15:19 부분으로 가이드를 드리게 됐어요~ 혹시 case4번을 해결하는 부분을 보시고 헷갈리시는 부분이 있다면 어떤 부분이 헷갈리시는지 알려주시면 제가 자세히 설명드리도록 하겠습니다~!
맞습니다~! 기본적으로 삭제 방식은 BST 삭제 방식과 동일하기 때문에 그렇습니다~ (관련 링크 : ua-cam.com/video/i57ZGhOVPcI/v-deo.html) 대신 레드블랙트리에서는 자녀가 둘인 노드를 삭제할 때는 삭제되는 색이 successor의 색이라는 것만 잘 기억해 주시면 좋을 것 같아요~
다른 댓글에 적은 설명인데 21:29 를 기준으로 i, j, p, q, x, y 를 상대적인 black 개수를 적어보면 i, j, x, y = 0 p, q = 1 이 됩니다. 이 숫자를 22:26 에도 적용을 해 보면 C 에서 nil 노드로 찾아갈 때 black 의 개수가 2 로 일정함을 알 수 있습니다. 중간 과정에도 마찬가지로 표시해 보면 모든 경우에서 속성 5가 유지됨을 알 수 있습니다. 그리고 C 와 D 의 색깔을 교환하는 것은 '레드블랙트리에서' 회전을 했을 때 '속성 5를 유지하기 위해 필요한 작업'으로 회전 전에 반드시 해야 하는, 레드 블랙트리에서의 회전 작업의 일부라고 볼 수 있습니다. 그러니 색깔 교환 시에 추가 작업을 필요로 하지 않습니다. (이 부분에 대한 설명은 다른 장문의 댓글에 해 놓았습니다.)
코멘트 하나 남깁니다~
* 매우 복잡해보이는 레드블랙트리를 최대한 이해하기 쉽게 설명한 영상입니다
- 1부 : ua-cam.com/video/2MdsebfJOyM/v-deo.html
- 2부 : ua-cam.com/video/6drLl777k-E/v-deo.html (현재 영상)
진짜 교수님이 설명해주실땐 4시간 붙잡아도 이해못했었는데 이 강의 한번에 팍 이해되네요 역시 유튜브가 짱입니다...
유투브에서 시각화 + 설명이 둘 다 좋은 자료 찾기가 쉽지 않은데, 덕분에 이해가 한 번에 되었습니다 :) 구독하고 틈틈이 다른 영상도 다 봐야겠네요!
우아 칭찬과 구독 감사합니다!!! 레드블랙트리는 특히 시간과 고생이 많이 들어간 영상인데 그렇게 말씀해주셔서 저도 많이 뿌듯합니다 :)
책이랑 같이 보니까 얼마나 잘 설명하시는 지 감탄할 따름입니다. 감사합니다.
저도 RB tree 구현 과제를 하고 있는 학생입니다. 아주 잘 정제된 고오급 정보라는 소식을 듣고 이렇게 댓글을 남깁니다 . AVL 트리까지 남김없이 잘 보겠습니다!!! 진심으로 감사합니다.
크~~~ 소식 듣고 이렇게 먼걸음 해주셔서 댓글까지 남겨주시고 정말 감사합니다!! 계속해서 좋은 영상으로 찾아뵐게요 :)
정말 많은 노력을 투자한 영상이라는 것이 느껴집니다 ㅎㅎ
RB tree를 공부 중이었는데 정말 큰 도움이 되었습니다!
오래오래 좋은 영상 만들어 주시면 감사하겠습니다~
크~~ 맞습니다 ㅠㅠ 레드블랙트리가 지금까지 만든 영상들 중에 제일 많은 시간과 수고가 들어간 영상이에요 ㅎㅎ
유익하게 봐주셔서 감사합니다!!
앞으로도 좋은 영상들로 찾아뵐게요
자주자주 놀러와 주세요 :)
끝까지 본 저희가 최고가 아니라 핵심만 쉽게 설명해주시고 좋은영상 제공해주시는 쉬운코드님이 더 최고십니다!! 안봐도 준비기간이 너무 힘들고 길었을거같습니다ㅠㅠ이번 주제는 조금 어려워서 여러번 돌려봤는데 좀더 숙달해봐야겠네요!! 영상 아주 잘 봤습니다 감사합니다!!
항상 응원해주셔서 감사합니다 지수님 ㅠㅠ 정말 최고십니다!!
레드블랙트리는 영상 준비할 때 저도 많이 힘들더라구요
트리 자체가 이해하기 어렵긴 합니다
그래도 잘 이해하시고 나면 '꽤 재밌는 이진균형트리구나' 느껴지실 거에요 :)
영상 너무 잘봤습니다. 마침 RB tree 구현 과제를 하고 있었는데 이런 양질의 자료를 제공해주셔서 이해에 정말 많은 도움이 되었습니다. 감사합니다!
우와 댓글 감사합니다! 레드블랙트리 영상을 진짜 정말 열심히 만들었는데 댓글 덕분에 힐링도 되고 뿌듯합니다 ㅠㅠ
RB tree 를 구현하는 과제를 진행중이였는데, 개념을 다지기 위해서 자료를 찾아보다 이런 고급 자료를 발견하게되다니 행운입니다!
2편을 걸쳐서 전부 봤는데, 복잡한 삽입, 삭제 예제를 그림으로 천천히 보여주면서 설명해주셔서 큰 도움이 되었습니다!
헷깔릴 때 마다 다시 와서 복습하면서 구현해봐야겠어요! 감사합니다!
댓글 감사합니다~! 지금까지 올렸던 영상 중에 제일 노력과 시간이 많이 들어간 영상이 레드블랙트리 영상이었어요 ㅎㅎ
큰 도움이 됐다니 너무나 뿌듯하네요 :)
과제 화이팅입니다!!
42?
영상이 너무 훌륭하네요. 레드블랙트리를 처음 보는 사람에게도 엄청난 도움이 되었습니다. 구독과 좋아요 가겠습니다 감사합니다.
와우~~! 대단히 감사합니다~! 레드블랙트리가 꽤 복잡한 구조인데 최대한 쉽게 설명하려고 노력했어요~ 좋게 봐주셔서 감사합니다 :) 계속해서 좋은 영상으로 찾아뵐게요~
우선 감사드립니다. 이런 멋진 영상을 올려주셔서요. 단순히 어느 조건에서 이렇게 해라 저렇게 해라라는 설명과는 비교가 안 되는 설명이고
레드블랙트리로 며칠을 씨름했는데 비로소 이 영상을 마지막으로 마음의 평화를 찾게 되었습니다 _ _)
영상 중에 18:19 에서 B와 D의 색을 바꿔준다는 게 이해가 안 갔습니다. extra black 를 개념과 17:00 에서 나오는 개념 등을 통해 근거를 두고 진행하시는데
색깔을 바꿔주는 데에는 아무 근거가 없는 것 같더라구요. 저 같은 사람이 있지 않을까 해서 댓글을 봤는데 저와 같은 부분에서 막힌 분은 없어보였습니다.
결국은 나름 이해를 하게 되어 저와 같은 분이 있을까 이해한 부분을 적어놓습니다.
18:19 에서 의아했던 게 red 를 왼쪽 서브 트리로 옮기는 게 '목적'인 건 알겠는데 근거는 알 수 없었습니다.
회전하기 전에 B 와 D 의 색을 서로 바꿔주면 B 의 윗쪽에서 B 를 거쳐 A 로 갈 때의 블랙의 개수와
B 의 윗쪽에서 B 를 거쳐 D 로 갈 때의 블랙의 개수가 달라져 버리니까요.
그런데 제가 이 부분에서 몰랐던 게, 'B 와 D 의 색을 서로 바꿔주는 것' 과 '회전' 을 별개로 봤었는데
B와 D의 색을 '바꿔 줘야만' 회전 후에도 레드블랙트리의 속성이 유지되는,
그러니까 두 노드의 색깔 바꾸기는 회전과 별개가 아니라 회전 과정의 일부였던 것이죠.
18:50 의 상태를 보면, 오른쪽 작은 그림은 회전 전의 그림이고, 왼쪽 큰 그림은 작은 그림에서 'B, D 의 색깔을 교환'한 후 회전 후를 나타낸 것인데,
우선 작은 그림의 속성 5 를 만족할 때 큰 그림도 속성 5를 만족하는지 알아야 합니다.
'교환 후에' 회전을 했을 때 만족을 한다는 것을, '교환 하지 않으면' 만족하지 않는다는 것을 확인하기 위해서요.
작은 그림에서 i, j, p, q, x, y 에 들어있을 블랙 노드의 상대적인 개수를 보면,
i, j 를 0 이라고 한다면,
p, q, x, y, 는 1 이어야 합니다. A 에 블랙이 2개 있다면 레드인 D 를 거쳐가는 경우 2 를 만족해야 하는데
C 와 E 는 각각 블랙이 1이므로 p, q, x, y 어딘가에 블랙이 하나 더 있어야 하기 때문입니다.
이제 상대적인 크기이므로 알아보기 쉽게 p, q, x, y 를 1 로 두고, i, j 를 0 으로 두고 회전 후의 상태인 왼쪽 큰 그림을 보면 됩니다.
오른쪽 작은 그림에서
B + A + j = 파랑 + 2 + 0 = 파랑 + 2 이고,
B + D + C + q = 파랑 + 0 + 1 + 1 = 파랑 + 2
B + D + E + x = 파랑 + 0 + 1 + 1 = 파랑 + 2
왼쪽 큰 그림에서
D + B + A + j = 파랑 + 0 + 2 + 0 = 파랑 + 2
D + B + C + p = 파랑 + 0 + 1 + 1 = 파랑 + 2
D + E + x = 파랑 + 1 + 1 = 파랑 + 2
가 됩니다.
B, D 의 색깔을 교환하지 않고 회전을 했다면 왼쪽 큰 그림에서
B : 파랑, D 빨강일 테고,
D + B + A + j = 빨강 + 파랑 + 2 + 0 = 0 + 파랑 + 2 = 파랑 + 2
D + B + C + p = 빨강 + 파랑 + 1 + 1 = 0 + 파랑 + 2 = 파랑 + 2
D + E + x = 빨강 + 1 + 0 = 0 + 1 = 1
이 되어 균형이 맞지 않게 됩니다.
∴ B 와 D 의 색깔 교환은 속성 5를 유지하기 위해 '회전' 전에 반드시 해야 하는 작업이며,
'오른쪽 서브 트리의 레드를 왼쪽 서브 트리로 옮기려면 '회전'을 해 주면 됩니다.'
안녕하세요, 저도 이 부분에서 한참 고민하고 있었는데 덕분에 이해하는데 도움을 받았어요 감사합니다! 이 글을 읽고 생각해보니까 삽입 연산에서도 회전 전에 Grandparent와 Parent만 색을 교환하고 Uncle은 교환하지 않았었네요 삽입 연산 강좌 들을 때는 그냥 그렇구나 했었는데 ㅋㅋㅋ 여기서는 문득 왜 둘만 색을 교환하는건지 의문이 들었는데 회전 작업의 일부라고 이해하니까 일관성이 생기네요
저도 이 부분 갑자기 색을 바꿔도 괜찮나하면서 의문이 들었었는데 이렇게 글로 남겨주셔서 정말 정말 감사드립니다. 덕분에 이해했습니다. 이해를 해도 그걸 남들이 이해하기 쉽게 해당영상처럼만들거나 글로 쓰는게 진짜 쉽지 않은데 감사드립니다.
근데 마지막에 D+E+x에서 x의 상대적블랙이 1이므로 0 + 1 + 1 = 2가 되어야 할 것 같습니다.
아무쪼록 진짜 감사드립니다.
복잡한 내용을 이렇게 이해하기 쉽게 설명하시는게 대단합니다!
정말 이해하는데 많은 도움이 되었습니다. 이런 양질의 콘텐츠 항상 감사합니다!
감사합니다 !! 레드블랙트리는 특히나 시간과 노력이 많이 들어간 영상인데요, 좋은 피드백을 받아서 저도 기분이 좋고 뿌듯하네요 !!ㅎ
자주 놀러와 주세요~ 좋은 컨텐츠로 준비해 놓을게요 👍
진짜 누가봐도 이해할 수 있도록 설명해주셔서 감사합니다
검색해서 찾아봐도 그게 뭔소린지 알 수 없었는데 이 영상보고 이해했습니다 ㅎㅎㅎㅎ
어제 1부에 이어 오늘 2부도 잘 보고 갑니다! 엄청 복잡한 내용이라 레드블랙트리라는 이름만 들어도 막막했는데, 구성이 너무 깔끔해서 도움이 정말 많이 됐습니다. 감사합니다!
맞아요 저도 그랬어요 레드블랙트리는 처음에 이해할 때 너무 복잡하더라고요
그래서 보시는 분들에게 최대한 잘 와닿고 이해되기 쉽게 설명하려고 내용 구성할 때 정말 많은 고민을 했었죠 👍
좋게 유익하게 봐주셔서 감사합니다 !!
영상 정말 잘 봤습니다! 찰떡 같은 설명 감사합니다ㅠㅠ
크~~ 도움된 것 같아서 뿌듯하네요 :)
와 진짜 설명 잘해주시네요.. 오래오래 해주세요 감사합니다
극찬 정말 감사합니다 ㅠㅠ 꾸준히 해야죠!ㅎㅎ 앞으로도 많이 애청해주세요 :)
당신은 신입니다. 정말 감사드려요!!
과찬이십니다~! 자주 자주 놀러와 주세요
좋은 영상으로 기다리고 있겠습니다 :)
삭제되는 노드의 자식의 수가 0이든 1이든 2이든 doubly black은 NIL노드에만 부여되는 것 같은데 맞을까요?
질문이 있습니다!
1. 인터넷에서 레드블랙트리 시뮬레이터의 경우 root node 삭제시 왼쪽에서 제일 큰 값을 root node로 선정하는데
선생님 코드는 오른쪽에서 제일 작은 값으로 선정하는 부분이 제가 생각했을 땐 방법의 차이일뿐 동작에 문제 없다고 생각하는데 맞을까요?
2.선생님이 delete 예제 하신것을 모두 수행했을때 결과가 동일하게 나오면 레드블랙트리를 제대로 구현했다고 생각해도 되는 걸까요?
예전에 선생님 영상을 보면서 레드블랙트리를 만들었는데 다시 확인해보니 문제가 좀 있어서 수정을 하였습니다.
결과적으로 delete 예제의 test예제는 모두 통과할수 있게 수정을 했는데 test 예제들을 모두 통과하면 문제 없이 구현된걸까요?
와 미친설명입니다. ㅋㅋㅋ 1부터 봤는데, 삽입/삭제시 해당 케이스에서 문제 해결을 어떻게 하려고 하는지 아이디어를 알려주셔서, 진짜 좋았네요@@!! 마지막 AVL 트리 비교 까지! AVL 트리 사례는 궁금해서 저도 찾아본 내용이었는데, 또 이렇게 똭! 떠먹여주시다니! 감사합니다. ㅎㅎ
오호홍 넘 뿌듯하네요 ㅎㅎㅎ 레드블렉트리가 진짜 고생 많이 해서 만든 영상이었거든요 ㅠㅠ
칭찬 해주시니까 기분이 넘 좋습니다 ✌✌
다른 영상들도 유익한 내용이 많으니까요 자주 자주 놀러와 주세요 :)
쉬운코드님 이 영상은 진짜 많은 노력이 느껴지는 영상인 것 같아요 ㅠㅠ 감사합니다!!!!
레드블랙트리는 지금까지 만든 영상 중에 제일 고생 많이 했던 영상이었죠 ㅎㅎ
알아봐 주셔서 정말 감사합니다 ㅠㅠ
@@ez. 공부하다가 이해가 잘 되지 않는 부분이 있어서 답글 남기게 됐어요!
18:02 에 등장하는 슬라이드에서 해당 트리 상태가 여전히 #5 속성을 만족한다고 말씀하셨는데, 이 부분에 대한 이해가 잘 되지 않아서 질문 드립니다!
저는 만족하지 않는 경우가 있다고 생각이들어서 이해가 되지 않았던 것 같은데,
예를 들어, B 노드가 루트 노드(=Black)이고, C 노드가 Black 인 경우 그리고 슬라이드에서 i, j, p, q, x, y 모두 nil 노드로 가정했을 때,
B 노드 기준으로 리프 노드까지의 Black 노드 수를 카운트하면 나머지는 다 세 개씩 나오는데 B -> D -> E -> nil 경로에서는 두 개가 카운트돼서 #5 속성에 부합하지 않다고 생각이 들었어요!
만약에 나머지 조건이 같고, C 노드가 Red 인 경우에는
B -> D -> C (+extra black) -> nil = 2개
B -> D -> E -> nil = 2개
B -> A (+extra black) -> nil -> 3개
위 처럼 계산이 돼서 마찬가지로 #5 속성에 부합하지 않다고 생각이 들었습니다!
제가 뭔가 계산 과정에서 착오가 있는 것 같아서 앞뒤로 다시 한 번 들어봤는데 그래도 잘 이해가 되지 않아서 질문 남기게 됐습니다 ㅠㅠ !
늘 좋은 자료 제공해주셔서 감사합니다!
@@devyun1954 오오 예리한 질문이십니다!!
자세히 답변 드려볼게요~
---
질문주신 18:02 는 4번 case를 해결하는 와중에 나온 부분인데요
그래서 4번 case의 출발점인 15:19 로 돌아가 보겠습니다
사실 이 부분도 그림만 놓고 보면 5번 조건을 위반하는 것 처럼 보입니다
예를 들어 i, j, p, q, x, y 서브 트리가 모두 nil 노드라면, B에서 i, j로 갈 때의 경로와 x, y로 갈 때의 경로에서 블랙 수가 차이가 나니까요
하지만 실제로는 15:19 에서 5번 조건을 위반하는 경우는 존재하지 않는데요,
왜 그런지 설명드리면,
case 1, 2, 3, 4는 black을 삭제 후 5번 조건을 다시 만족시키기 위해 extra black을 부여했더니 doubly black이 생긴 경우를 네 가지 케이스로 분류한 것이기 때문입니다
즉, case 1, 2, 3, 4는 5번 조건을 만족한 상태에서 시작합니다
헷갈릴 만한 포인트가 생긴 이유는,
5번 조건을 만족하고 있는 doubly black이 있는 트리를 네 가지 케이스로 일반화 시켜서 분류하다보니 서브트리로 표현하게 됐고,
(그래서 B위에 화살표가 있는 것도 일반화 시켜서 표현하려다 보니 부모 노드가 있을 수 있다는 것을 나타내기 위해서 표기하게 된 것이고요,)
그러다 보니, 그림만 놓고 보면 5번 조건을 만족하지 않는 케이스도 있는 것처럼 보이기 때문인 것 같습니다
그래서 정리하자면
그림에서 서브트리로 표현된 부분은 '모든 가능한 레드-블랙 노드의 조합'을 의미하는 것이 아니라,
'5번 조건을 만족하는 doubly black을 가진 트리의 서브트리들'이라고 봐야 합니다
애초에 5번 조건을 만족하고 있던 트리였는데, 그림만 놓고 보면 5번 조건을 만족하지 않는 케이스도 보이다 보니 헷갈리는 포인트가 생긴 것 같아요
(저도 처음 공부할 때 이것 때문에 헷갈렸어요 ㅠㅠ)
다시 처음 질문으로 돌아가서, 그렇다면 18:02 도 5번 조건을 만족합니다
왜냐하면 5번 조건을 만족하던 15:19 에서 출발해서 5번 조건을 위반하지 않도록 하면서 18:02의 형태까지 도달했기 때문이죠
---
답변이 도움이 됐길 바라면서,,
항상 애청해 주시고 열심히 봐주셔서 정말 감사합니다!!
그리고 정말 멋지십니다!!!
@@ez.
아아 답변 해주신 내용 읽어보니 이해가 됐습니다! 논리적으로 전제를 짚어주시니까 바로 이해가 됐어요 ㅎㅎ
빠른 답변 감사드립니다 : - ) ㅎㅎㅎ
댓글을 안 남길 수가 없네요! 모르는거 있으면 바로 쉬코로 올게요
넵~!! 자주 들러주세요 :) 알찬 영상으로 많이 준비해 놓겠습니다 👍
설명도 자세하고 쉽게 설명해주셔서 이해하기 좋았습니다
어려운 작업해 주셔서 감사합니다!
영상을 좋게 봐주셔서 감사합니다 :)
응원의 메시지 덕분에 많이 뿌듯하네요 헿
설명 너무 깔끔해요~ 진짜 감사합니다!!!!
영상 정말 잘 봤습니다. 정말 쉽게 설명해주시는 것 같아요. 과정을 따라가다보니 의문이 생겼습니다.
삭제되는 노드가 2개의 자식을 가질 경우, 그 successor는 우측 서브트리의 최솟값이 되는 노드이므로 이중흑색은 항상 그 위치를 대체하는 NIL에게만 부여된다고 이해했는데 이게 맞을까요? 핵심과 거리가 있는 질문이지만 궁금해서 남겨봅니다.
오, 생각해보니 그렇게 될 것 같아요
자녀가 두 개인 노드를 삭제할 경우, doubly black이 발생하려면
1. successor의 색이 black이고
2. successor의 위치에 올라온 친구도 black이어야 하는데,
successor는 특성 상 자녀가 없거나 오른쪽 자녀만 있을거라서,
- 자녀가 없다면 NIL 노드에 extra black이 부여가 될 거고,
- 오른쪽 자녀가 있다면 successor의 오른쪽 자녀에게 extra black이 부여될텐데, 오른쪽 자녀의 색도 black인 경우는 NIL 노드 뿐이므로 (만약 오른쪽 자녀가 NIL노드가 아닌데 black이라면 트리가 이미 조건 5를 위반하고 있었다는 말이 되는데, 삭제하기 전 상태는 모든 조건을 만족하던 상태였으므로 이는 모순이 되기 때문)
결론은 '자녀가 두 개인 노드를 삭제할 때 doubly black이 발생한다면 항상 NIL 노드에서만 발생한다'고 볼 수 있겠네요
19:45에서 RB tree 5번 조건을 만족하지 않는 경우가 생기지 않나요? 만약 D와 C 모두 빨강색이면 D번 노드를 기준으로 i, j, p, q, x, y로 가는 경로에서 검은색 노드들의 갯수가 각각 2, 2, 1, 1, 1, 1이라서 5번 조건을 위반한 것이라고 생각됩니다
안녕하세요 :)
우선 결론부터 말씀드리면 5번 조건을 위반하지 않습니다. 왜 그런지 설명을 드리려다가, 사실 저도 공부할 때 비슷한 생각을 해본적이 있고 결국 무엇을 놓친 것인지 깨닫게 됐을 때 흥미롭고 기분이 좋았던 기억이 있어서, 그런 기분을 느낄만한 기회를 제가 빼앗으면 안되는 것 아닐까라는 생각이 들더라구요~
그래서 혹시 괜찮으시다면, 왜 이게 5번 조건을 위반하지 않는지 그 답을 찾아보시겠어요?
첫번째 힌트는, 4번 case의 출발점인 15:20에서도 말씀하신 방법대로 접근한다면 5번 조건을 위반한다고 봐야합니다. 하지만 15:20도 5번 조건을 위반하지 않습니다. 15:20이 왜 5번 조건을 위반하지 않는 것인지 이해가 되시면 19:45도 왜 5번 조건을 위반하지 않은 것인지 이해가 되실 거예요
두번째 힌트는, extra black의 탄생 이유입니다.
세번째 힌트는, 5번 조건은 임의의 자손 'nil 노드'까지 가는 경로에서의 블랙 수를 확인합니다.
마지막으로 네번째 힌트는,,
i, j, p, q, x, y는 노드가 아닙니다. 서브트리입니다.
혹시나 힌트 때문에 더 헷갈리셨다면,, 죄송합니다.. ㅠ
추가 설명이 혹시 필요하시면 댓글 남겨주세요
@@ez. 5번 힌트는 이해가 가질 않습니다. 서브트리가 반드시 여러 노드일 필요는 없지 않나요? 또한 nil 노드 역시 서브트리라고 생각합니다. 마치 공집합이 부분 집합 중 일부인 것처럼요
아무래도 드린 힌트가 오히려 방해가 된 것 같네요.. 죄송합니다
바로 답변을 드리겠습니다
만약 말씀하신 방식으로 접근을 하게 되면, 4번 case의 출발점인 15:20 또한 5번 조건 위반이라고 해석해야 합니다.
예를 들어 i, j, p, q, x, y 서브 트리가 모두 nil 노드라면, B에서 i, j로 갈 때의 경로와 x, y로 갈 때의 경로에서 블랙 수가 차이가 나니까요.
하지만 실제로는 5번 조건을 위반하는 경우는 존재하지 않습니다.
왜 그런지 설명드리면,
case 1, 2, 3, 4는 black을 삭제 후 5번 조건을 다시 만족시키기 위해 extra black을 부여했더니 doubly black이 생긴 경우를 네 가지 케이스로 분류한 것이기 때문입니다.
즉, 5번 조건은 이미 만족하고 있습니다.
5번 조건을 만족하고 있는 doubly black이 있는 트리를 네 가지 케이스로 일반화 시켜서 분류하다보니 서브트리로 표현하게 된 것이고, B위에 화살표가 있는 것도 일반화 시켜서 표현하다보니 부모 노드가 있을 수 있다는 것을 나타내기 위함인 것입니다.
그러므로 서브트리로 표현된 부분은 '모든 가능한 레드-블랙 노드의 조합'을 의미하는 것이 아닙니다.
이 서브트리들은 '5번 조건을 만족하고 있는 doubly black을 가진 트리의 서브트리들'을 의미합니다.
애초에 5번 조건을 만족하고 있던 트리였는데, 서브트리에 5번 조건을 만족하지 않는 케이스를 골라서 생각했기 때문에 헷갈리는 포인트가 생긴 것입니다.
같은 이유로 19:45도 5번 조건을 만족합니다.
애초에 5번 조건을 만족하던 15:20에서 출발해서 5번 조건을 위반하지 않도록 하면서 19:45의 형태로 도달했기 때문입니다.
@@ez. 저도 해당 부분이 이해가 안되서 혼자서 계속해서 고민하고 있었는데 !! 제가 정말 궁금했던 사항에 관해서 꼭 집어서 설명해주셔서 속이 뻥 뚫렸습니다. 정말 감사합니다 !!
@@deniapark761 도움될 수 있어서 다행입니다! 귀한 댓글 감사해요 :) 👍
우선 정말 쉬운 설명에 감탄하고 감사합니다. 알고리즘 공부를 시작한지 얼마 되지 않아 아직 궁금한 점이 많습니다.
다름이 아니라 레드 블랙 트리 구현 중 궁금한 것이 생겨 간단한 질문 드리는데 노드를 구현할 때 노드가 멤버 변수로 닐 노드 두 개를 기본적으로 모두 들고 있게 구현 하는 것이 일반적인가요?? 만약 그렇다면 닐 노드는 다른 노드와 비교하여 그저 데이터 값만 가지고 있지 않으면 되는 것인지요 또한 만약 힙 영역에 할당한다면 유효한 데이터 값 생성 시 그 자식인 닐 노드 또한 할당은 하되 데이터를 가지고 있지 않은 것인지 궁금하여 질문 드립니다!
구현 부분에 대하여 질문드려 죄송합니다 ㅠㅠ
개념적으로 설명을 드리면 레드블랙트리는 닐 노드가 중요한 역할을 하기 때문에 기본적으로 닐 노드는 유효한 값을 가지지 않는 노드로 존재해야 합니다
'일반적으로' 구현을 어떻게 하는지에 대한 부분은 저도 여러 구현을 본 것은 아니기 때문에 답변드리기는 조금 어렵고요,
대신 nil 노드를 매번 생성하면 메모리 낭비가 있으니, 어차피 닐 노드는 특징이 모두 같으니까 닐 노드 용도로 쓸 노드 하나를 만들고 모든 닐 노드는 그 하나의 닐 노드를 공유해서 쓰는 형태로 사용했던 것 같습니다~
감사합니다...진짜 책보고 이해해보려다가 정신나갈뻔햇는데 구원받앗습니다😂
22:00 분 그래프의 상태를 보면 노드 D의 black height가 속성 5를 위반하는거 아닌가요?, 설명이 틀린것 같습니다.
"회전 이전의 상태" 를 보면 노드D black height를 k라고 할때, 서브트리 p, q, x, y 내부의 블랙 노드의 개수는 k-1 입니다.
그런데. 회전하고 D노드는 왼쪽 서브트리 q의 내부 블랙 노드의 개수는 k-1 보다 오른쪽 서브트리가 블랙노드가 k개이며, 1개 더 많습니다.
속성 5를 위배합니다.
회전 이전 상태(21:29)이 속성5를 만족한다고 한다고 했을 때, i, j, p, q, x, y 끼리의 상대적인 블랙 노드 개수를 확인해 보면
p, q 는 i, j, x, y 보다 내부 블랙 노드의 개수가 하나 많아야 합니다. 빨강인 C 를 거쳐서 지나갔는데도 속성 5를 만족하니까요.
상대적인 개수이므로 간단하게 q 를 +1, x 와 y 를 0 으로 두고, 회전한 후의 D 의 좌우 서브 트리를 보면
D 의 왼쪽 서브 트리 = C + q = 0 + 1 과
D 의 오른쪽 서브 트리 = C + E + (x or y) = 0 + 1 + 0 이 되어 양쪽 black-height 는 일치하게 됩니다.
영상 감사합니다!!! 최고입니다!!!
ProT A님도 최고입니다!!!
영상 너무 감사하게 잘 봤습니다ㅎㅎㅎ!
그런데 22:20 에서 C와 C의 부모의 색을 swap하고 왼쪽 회전을 하는건 이해되는데 왼쪽 회전 직전에 "D도 black으로 만들고 왼쪽 회전을 하는 이유"가 궁금해요ㅠㅠ
크~~! 유익하게 봐주셔서 감사합니다 :)
질문주신 22:20은 case4번을 적용할 수 있는 상황이 됐기 때문에 case4번을 해결하는 방식으로 해결하는 순간이에요
그래서 핵심은 '왜 B와 D를 black으로 바꿔주느냐' 일텐데요,
요 내용은 case4번 설명(15:19)을 자세히 보시면 이해하실 수 있을 것 같아요~
글로 쓰려니까 글 만으로는 설명에 한계가 있을 것 같고,
영상과 같이 설명을 들으시는게 더 쉽게 이해하실 수 있을 것 같아서 15:19 부분으로 가이드를 드리게 됐어요~
혹시 case4번을 해결하는 부분을 보시고 헷갈리시는 부분이 있다면 어떤 부분이 헷갈리시는지 알려주시면 제가 자세히 설명드리도록 하겠습니다~!
대박입니다. ㅋㅋㅋ 저는 이 영상 다 보는데 거의 5 시간 정도 걸렸네요. 그래도 마지막에 삭제 예제 먼저 풀어보고 다 맞췄네요 ㅎㅎ
와 다섯시간~!! 유대감님 리스펙트 합니다 👍👍👍
설명 너무 좋아요!! 감사합니다!!
어려운 내용을 쉽게 설명해주셔서 정말 감사합니다!
유익하게 봐주셔서 저도 정말 감사합니다 :) 👍
자식이 둘인 노드를 삭제할때는, successor 의 값만 삭제할 노드에 옮긴후 successor 를 삭제하는 것과 같나요? 이때 successor은 항상 자식이 하나거나 없으니까, 만약 문제를 그렇게 바꿀 수 있다면 제가 더 이해하기 편한거 같아서요!
맞습니다~! 기본적으로 삭제 방식은 BST 삭제 방식과 동일하기 때문에 그렇습니다~ (관련 링크 : ua-cam.com/video/i57ZGhOVPcI/v-deo.html)
대신 레드블랙트리에서는 자녀가 둘인 노드를 삭제할 때는 삭제되는 색이 successor의 색이라는 것만 잘 기억해 주시면 좋을 것 같아요~
@@ez. 아 자식 노드가 하나거나 없는successor을 삭제하는것과 같아지니까, 결국 successor의 색이 사라지는거군요. 감사합니다!!
감사히 보겠습니다.
사랑합니다
진짜 너무 감사합니다 독학이라 블로그 뒤져가며 공부해도 한계가 있었는데 덕분에 이해가 잘 됐습니다
도움드릴 수 있어서 정말 뿌듯합니다 !!ㅎ
댓글 감사합니다 👍
영상 참 잘 만드시네요 감사합니다
크 ㅠㅠ 좋게 봐주셔서 감사합니다 :)
덕분에 좋은 내용 잘 보고 갑니다.
정말 감사합니다.
유익하게 봐주셔서 감사합니다~! 👍
완전 잘가르치십니다!!
영상 잘 보고 있습니다. 감사합니다!
저도 항상 애청해 주셔서 감사합니다 :) 👍
22:26 분 그래프의 상태도 속성 5를 위배하는것 같습니다.
C와 D의 색을 변경할때 extra black을 E에 추가해 주어야 됩니다.
다른 댓글에 적은 설명인데 21:29 를 기준으로 i, j, p, q, x, y 를 상대적인 black 개수를 적어보면
i, j, x, y = 0
p, q = 1 이 됩니다. 이 숫자를 22:26 에도 적용을 해 보면 C 에서 nil 노드로 찾아갈 때 black 의 개수가 2 로 일정함을 알 수 있습니다.
중간 과정에도 마찬가지로 표시해 보면 모든 경우에서 속성 5가 유지됨을 알 수 있습니다.
그리고 C 와 D 의 색깔을 교환하는 것은 '레드블랙트리에서' 회전을 했을 때 '속성 5를 유지하기 위해 필요한 작업'으로 회전 전에 반드시 해야 하는,
레드 블랙트리에서의 회전 작업의 일부라고 볼 수 있습니다. 그러니 색깔 교환 시에 추가 작업을 필요로 하지 않습니다.
(이 부분에 대한 설명은 다른 장문의 댓글에 해 놓았습니다.)
감사합니다!!
좋은 영상 감사합니다!!
대박입니다........... 잘먹고가요!!