빨간색과 검은 나무
빨간색과 검은 나무는 데이터 구조와 알고리즘에 종종 언급되는 나무이지만 자세히 설명 할 수는 없습니다. 그들은 또한 기술 인터뷰에서 종종 질문을받는 나무입니다. 그러나 책의 자료이든 온라인 자료이든, 일반적으로 더 엄격하고 이해하기 어렵습니다. 더 직관적 인 방식으로 빨간색과 검은 나무를 이해할 수 있습니까? 이 기사는 빨간색과 검은 색 나무의 삽입 및 삭제 작업을 그래픽으로 설명합니다.
트리 구조를 배우는 것은 진보적 인 과정입니다. 우리가 일반적으로 접촉하는 나무는 이진 나무입니다. 간단히 말해서, 각각의 비 잎 노드에는 좌파 자녀와 오른쪽 자녀라고 불리는 두 자녀 만 가지고 있습니다. 이진 검색 트리라고 불리는 이진 트리에는 특수 유형의 트리가 있습니다. 이진 검색 트리는 순서대로 트리입니다. 각각의 비 잎 노드에 대해 왼쪽 하위 트리의 값은 그보다 작고 오른쪽 하위 트리의 값은 그보다 더 큽니다. 이진 검색 트리보다 더 많은 단계는 이진 밸런스 트리입니다. 순서를 보장하는 것 외에도 바이너리 밸런스 트리는 각 노드의 왼쪽과 오른쪽 하위 트리와 1 이하의 높이 차이를 유지할 수 있습니다. 일반적인 균형 나무는 AVL 나무, 트레그, 붉은 색 및 검은 나무, 스트레치 나무 등입니다.
빨간색과 검은 색 트리는 이진 검색 트리이지만 각 노드에 스토리지 비트를 추가하여 노드의 색상을 나타내며 빨간색 또는 검은 색 일 수 있습니다. 각 노드가 루트에서 잎까지의 경로에서 음영을 제한함으로써, 빨간 블랙 트리는 경로가 다른 경로보다 두 배나 길지 않도록하여 균형에 접근합니다.
빨간색과 검은 색 나무는 5 가지 속성을 충족합니다.
붉은 검은 나무에서 전통적인 바이너리 트리의 잎 노드의 아이를 닐로 가리키고 잎 노드를 빨간색 블랙 트리의 잎 노드라고 부릅니다. NIL 노드에는 부모 노드에 대한 포인터가 포함되어 있으며, 이는 NULL을 NIL로 변경 해야하는 이유 일 수 있습니다.
1. 작동을 삽입하십시오
먼저, 이진 검색 트리를 삽입하는 방식으로 새 노드를 삽입하고 (삽입 된 새 노드는 모두 리프 노드에 있습니다) 빨간색으로 그립니다. 그런 다음 색상을 다시 그리거나 회전하여 빨간색과 검은 나무의 특성을 유지하십시오. 조정은 다음 세 가지 상황으로 나뉩니다.
1 New Node N에는 부모 노드가 없습니다 (즉, 루트에 있습니다)
새 노드 n을 검은 색으로 페인트하십시오.
2 새 노드 N의 부모 노드 P는 검은 색입니다.
조정할 필요가 없습니다.
3 새 노드 N의 부모 노드 P는 빨간색입니다.
빨간색과 검은 색 트리는 두 개의 연속 빨간색 노드 (속성 4)를 허용하지 않으므로 조정해야합니다. N의 아저씨 노드의 색상에 따르면, 그것은 두 가지 상황으로 나뉩니다.
3.1 새 노드 n의 아저씨 노드 u는 빨간색입니다. 새 노드 N의 부모 노드 P 및 Uncle 노드 U는 검은 색으로 칠해지고 할아버지 노드 G는 g에서 각 널 노드까지의 경로에 포함 된 검은 색 노드의 수가 원래의 것과 일치하도록합니다. 그러나 우리가 g의 아버지가 빨간색으로 변하기 때문에 G의 아버지도 빨간색으로 변하기 때문에 두 개의 연속적인 붉은 노드 (자연 4를 위반)로 이어질 수 있으므로 G가 빨간색과 검은 나무의 특성을 위반하는지 여부를 다시 확인해야합니다.
3.2 새로운 노드 n의 아저씨 노드 u는 검은 색입니다. 새 노드 N이 부모 노드 P의 왼쪽 자식 인 경우, 부모 노드 P를 검은 색으로 그리고 할아버지 노드 G를 빨간색으로 그린 다음 한 번에 G를 회전시킵니다.
새 노드 n이 부모 노드 P의 올바른 자식 인 경우, 부모 노드에서 왼쪽 회전을 수행하면 문제가 왼쪽 자식의 상황으로 변환됩니다.
2. 작동 삭제
"알고리즘 소개"와 Wikipedia의 방법은 검은 색 노드 D를 삭제하는 것입니다. D의 검은 색을 "푸시"를 자식 노드 C로 푸시하는 것입니다. 즉, C는 자체 색상 외에 검은 색 층을 추가 한 다음 검은 색으로 검은 색으로 이동하여 검은 색으로 이동하여 검은 색으로 바꾸어 검은 색으로 바뀌 었습니다. 트리, 모든 경로의 검은 색 노드의 수가 하나씩 감소하고 동일하게 유지되도록합니다. 상향 이동하는 동안 경로의 검은 색 노드 수가 변경되지 않도록 일부 노드 색상을 회전하고 수정해야 할 수 있습니다.
이 접근법은 코드 구현에 도움이 될 수 있지만 (반복적 인 방식으로 사용될 수 있음) 이해하기 편리하지는 않습니다 (개인적으로 믿음). 우선 순위를 이해하기 위해, 나는 삭제 된 노드 d의 자녀가 nil인지에 따라 다음 분류를 만들었습니다.
1 노드 D가 삭제 된 두 어린이 모두 NIL입니다.
1.1 삭제 된 노드 D가 빨간색 인 경우 d를 nil로 바꾸십시오.
1.2 삭제 된 노드 D는 검은 색입니다 (예 : D를 예로 들어 봅시다)
1.2.1 형제 D가 삭제 된 노드 B의 두 자녀는
D의 Brother 노드 B는 빨간색으로 페인트되어 있으며, 상위 노드 P는 검은 색으로 칠해집니다.
그림의 반쪽과 반 검은 색은 노드가 빨간색 또는 검은 색 일 수 있음을 의미합니다. p가 빨간색으로 판명되면, 수정 후 경로의 검은 색 노드의 수는 deletion d 이전과 동일합니다. P가 검은 색으로 판명되면 d 삭제하면 삭제 전보다 경로에서 검은 색 노드가 줄어 듭니다. 따라서 P를 통과하는 경로에서 검은 색 노드 수의 변경이 빨간색과 검은 색 트리의 속성에 영향을 미치는지 계속 확인해야합니다.
1.2.2 노드 D의 형제 노드 B에는 자녀가 없습니다.
어린이는 빨간색이어야합니다. 그렇지 않으면 D의 상위 노드에서 각 리프 노드까지의 경로의 검은 노드 수는 다릅니다 (위반 5).
이 자녀가 올바른 자녀 인 경우 B의 올바른 아이를 검은 색으로 그리고 B를 부모 노드 P의 원래 색상으로 그립니다. P를 검은 색으로 그린 다음 왼쪽으로 P를 회전시킵니다.
이 자녀가 왼쪽 자녀 인 경우 B의 왼쪽 자녀를 검은 색으로, B를 빨간색으로, B를 올바르게 회전 시키면 문제가 오른쪽 자녀의 상황으로 변형됩니다.
1.2.3 삭제 된 노드 B의 두 자녀는
B가 빨간색이면 B의 두 자녀는 흑인이어야합니다. B를 검은 색으로, B의 왼쪽 아이를 빨간색으로 그린 다음 P의 왼쪽 회전을 수행하십시오.
B가 검은 색이면 B의 두 자녀는 빨간색이어야합니다. B의 상위 노드 P를 검은 색으로, B의 오른쪽 자식은 검은 색으로, B의 원래 색상은 부모 노드 P로서, P를 왼쪽으로 회전시킵니다.
2 노드 D가 삭제 된 두 어린이 모두 NIL이 아닙니다.
바이너리 검색 트리에 따르면 노드를 삭제하고 D의 후속 노드를 찾고 D와 S의 내용을 교환하고 (색상은 변경되지 않은 상태) S가됩니다. S가 NIL이 아닌 노드를 갖는 경우 삭제 된 노드의 양치가 NIL이 될 때까지 S의 후속 노드를 계속 대체합니다. 문제는 삭제 된 노드 D의 두 자녀가 NIL 인 상황으로 바뀝니다.
3 삭제 된 노드 D에는 자식이 없습니다
이 자식 C는 빨간색 노드 여야하며, 그렇지 않으면 D에서 각 Nil 노드로의 경로의 검은 노드 수는 다릅니다 (위반 5).
D와 C의 내용이 교환되고 (색상은 동일하게 유지됨) 삭제 된 노드는 C가되고 문제는 삭제 된 노드 D의 두 자녀가 NIL 인 상황으로 바뀝니다.
이진 나무의 횡단
이진 트리에는 세 가지 유형의 트래버스가 있습니다 : 선주문 트래버스, 중간 순회 및 우편선 순서. 트래버스 구현에는 두 가지 유형이 있습니다 : 재귀 및 반복. 이 기사에서는보다 우아한 코드를 사용하여 이진 트리의 횡단을 구현하는 방법에 대해 논의 할 것입니다.
먼저 바이너리 트리의 노드를 정의 할 것입니다.
공개 클래스 Treenode {int val; Treenode 왼쪽; 트린 노드 오른쪽; public treenode (int x) {val = x; }}
1. 선주문 트래버스
간단히 말해서, 선주문 횡단은 먼저 부모 노드에 액세스 한 다음 왼쪽 자식에 액세스 한 다음 마지막으로 오른쪽 자식, 즉 부모, 왼쪽 및 오른쪽의 순서대로 이동하는 것입니다.
재귀 구현은 매우 간단하며 코드는 다음과 같습니다.
공개 클래스 솔루션 {list <integer> result = new ArrayList <integer> (); 공개 목록 <integer> preorderTraversal (treenode root) {dfs (루트); 반환 결과; } private void dfs (treenode root) {if (root == null) {return; } result.add (root.val); DFS (root.left); DFS (루트 .right); }} 반복 구현에는 액세스되지 않은 오른쪽 노드를 저장하려면 스택이 필요합니다. 코드는 다음과 같습니다.
공개 클래스 솔루션 {public list <integer> preorderTraversal (treenode root) {list <integer> result = new ArrayList <integer> (); if (root == null) {return result; } stack <treenode> stack = new Stack <treenode> (); stack.push (루트); while (! stack.isempty ()) {treenode curr = stack.pop (); result.add (curr.val); if (curr.right! = null) {stack.push (curr.right); } if (curr.left! = null) {stack.push (curr.left); }} 반환 결과; }}
2. indert Traversal
간단히 말해서, 중간 주문 트래버스는 먼저 왼쪽 자식에 액세스 한 다음 부모 노드에 액세스 한 다음 마침내 오른쪽 자식, 즉 왼쪽, 부모 및 오른쪽의 순서대로 이동하는 것입니다.
재귀 코드는 다음과 같이 더 쉽습니다.
공개 클래스 솔루션 {public list <integer> inorderTraversal (treenode root) {list <integer> result = new arraylist <integer> (); reburse (root, result); 반환 결과; } private void Recurse (Treenode root, list <integer> result) {if (root == null) return; reburse (root.left, result); result.add (root.val); reburse (root.right, result); }} 위의 쓰기 방법은 재귀 적 사전 주문 트래버스 코드와 다릅니다. 우리는 멤버 변수를 사용하여 선주문 트래버스에 Traversal의 결과를 저장하며 여기서는 방법 매개 변수를 사용하여 Traversal의 결과를 저장합니다. 두 글쓰기 방법은 모두 괜찮으며 원하는 것을 사용하십시오.
미드 주문 트래버스의 반복 구현은 선주문 트래버스만큼 간단하지 않습니다. 또한 스택이 필요하지만 반복 종료 조건은 다릅니다. 이진 트리의 경우 먼저 액세스하는 노드가 가장 왼쪽 노드라고 상상해보십시오. 물론 우리는 while 루프를 통해 가장 왼쪽 노드에 도달 할 수 있지만, 우리가 넘어지면 노드의 왼쪽 자식에 액세스되었는지 어떻게 알 수 있습니까? Curr 변수를 사용하여 현재 액세스 한 노드를 기록합니다. 하위 트리의 오른쪽 노드에 액세스하면 하위 트리의 상위 노드로 돌아 가야합니다. 현재 Curr은 NULL이므로 노드의 왼쪽 하위 트리에 액세스되었는지 여부를 구별하기 위해 이것을 사용합니다. 코드는 다음과 같습니다.
공개 클래스 솔루션 {public list <integer> inorderTraversal (treenode root) {list <integer> result = new arraylist <integer> (); 스택 <treenode> stack = 새 스택 <treenode> (); Treenode Curr = 루트; while (curr! = null ||! stack.isempty ()) {while (curr! = null) {stack.push (curr); curr = curr.left; } curr = stack.pop (); result.add (curr.val); curr = curr.right; } 반환 결과; }}
3. 우편선 순회
간단히 말해서, 우편 순서 트래버스는 먼저 왼쪽 자식에 접근하고 오른쪽 자식에 접근하고, 최종적으로 부모 노드, 즉 왼쪽, 오른쪽 및 부모의 순서대로 이동하는 것입니다.
중간 순서 트래버스를 모방함으로써, 당신은 포스트 주문 트래버스의 재귀적인 구현을 쉽게 쓸 수 있습니다.
공개 클래스 솔루션 {public list <integer> postorderTraversal (treenode root) {list <integer> result = new arraylist <integer> (); reburse (root, result); 반환 결과; } private void recurse (treenode root, list <integer> result) {if (root == null) return; reburse (root.left, result); reburse (root.right, result); result.add (root.val); }} 포스트 주문 트래버스의 반복은 또한 노드의 왼쪽 및 오른쪽 어린이가 액세스되었는지 여부를 구별하기 위해 식별해야합니다. 그렇지 않다면 좌파와 오른쪽 어린이가 차례로 접근 할 것입니다. 액세스 된 경우 노드에 액세스됩니다. 이를 위해, 우리는 사전 변수를 사용하여 방문한 노드를 나타냅니다. 우리가 방문한 노드가 현재 노드의 왼쪽 또는 오른쪽 자식이라면 현재 노드의 왼쪽 및 오른쪽 자식에 액세스 한 다음 노드에 액세스 할 수 있음을 의미합니다. 그렇지 않으면, 우리는 왼쪽과 오른쪽 어린이를 입력하여 차례로 접근해야합니다. 코드는 다음과 같습니다.
공개 클래스 솔루션 {public list <integer> postorderTraversal (treenode root) {list <integer> result = new LinkedList <integer> (); 스택 <treenode> stack = 새 스택 <treenode> (); if (root! = null) stack.push (root); Treenode pre = 루트; while (! stack.isempty ()) {treenode curr = stack.peek (); if (curr.left == pre || curr.right == pre || (curr.left == null && curr.right == null)) {result.add (curr.val); stack.pop (); pre = curr; } else {if (curr.right! = null) stack.push (curr.right); if (curr.left! = null) stack.push (curr.left); }} 반환 결과; }} 사후 순서의 반복에 대한 또 다른 간단한 구현이 있습니다. 우리는 선주문 순서의 순서가 부모, 왼쪽 및 오른쪽이라는 것을 알고 있으며, 우주 후 트래버스의 순서는 왼쪽, 오른쪽 및 부모임을 알고 있습니다. 따라서 선주문 트래버스를 약간 수정하여 부모의 순서, 오른쪽 및 왼쪽으로 변경하면, 이는 우편 순서의 순서와 반대입니다. 이 순서로 액세스 한 후에는 결국 액세스 결과를 반전시킬 수 있습니다. 선주문 트래버스의 반복 구현은 비교적 쉽습니다. 위의 작문 방법에 따라 다음과 같이 구현할 수 있습니다.
공개 클래스 솔루션 {public list <integer> postorderTraversal (treenode root) {list <integer> result = new LinkedList <integer> (); 스택 <treenode> stack = 새 스택 <treenode> (); if (root! = null) stack.push (root); while (! stack.isempty ()) {treenode curr = stack.pop (); result.add (curr.val); if (curr.left! = null) stack.push (curr.left); if (curr.right! = null) stack.push (curr.right); } collections.Reverse (결과); 반환 결과; }}
4. 요약
세 가지 트래버스의 재귀 구현은 쉽습니다. 선주문 트래버스의 반복 구현을 작성하는 것이 가장 좋습니다. 하나의 스택 만 필요합니다. 중간 순위가 가장 어렵습니다. 스택이 비어 있는지 여부를 결정하는 것 외에도 루프 조건은 왼쪽 하위 트리가 통과했는지 여부를 나타내는 전류 노드가 비어 있는지 결정해야합니다. 후속 트래버스의 반복이 선주문 트래버스 반복으로 변환되면 훨씬 쉽습니다. 그렇지 않으면, 현재 노드의 왼쪽 및 오른쪽 서브 트리에 액세스되었는지 여부를 나타 내기 위해 이전 액세스 노드를 기록해야합니다.