방앗간

※ 좌측-우측 회전 - 레드 블랙 트리에서 좌측-우측 회전을 하는 코드는 다음과 같다. public void leftRightRotate(Node node){ leftRotate(node.left); rightRotate(node); }

※ 좌측 회전 - 레드 블랙 트리에서는 좌측 회전을 하는 코드가 다음 예시와 같지만 parent 노드를 가리키는 포인터와 isLeftChild 변수를 추가로 사용해야 하기 때문에 이러한 부분들을 고려해야 한다 public void leftRotate (Node node){ Node temp = node.right; node.right = temp.left; if(node.right != null) { node.right.parent = null; node.right.isLeftChild = false; } if(node.parent == null) { root = temp; temp.parent = null; } else { temp.parent = node.parent; if(node.isLeftChi..

※ Rotate 메소드 - 현재 노드와 부모 노드가 각각 우측 자식인지 좌측 자식인지에 따라 필요한 회전이 달라지는데 각각의 경우는 다음 코드 예시와 같다 public void rotate(Node node){ // 현재 노드가 좌측 자식 if(node.isLeftChild){ // 부모 노드가 좌측 자식 if(node.parent.isLeftChild) // 조부모 노드를 우측회전 rightRotate(node.parent.parent); node.black = false; node.parent.black = true; if(node.parent.right != null) node.parent.right.black = false; return; } // 부모 노드 우측 자식 // 조부모 노드 우측-좌측..

※ 색상 확인 메소드 - 노드를 트리의 규칙에 맞게 추가한 뒤, 레드 블랙 트리의 6가지 규칙을 만족하는지를 확인해야 한다 public void checkColor(Node node){ // 루트는 항상 검은색이므로 색을 확인할 필요가 없다 if (node == root) return; // 빨간 노드 2개가 연속으로 나오는 경우 if (!node.black && !node.parent.black){ correctTree(node); // 부모 노드를 계속 확인한다 checkColor(node.parent); } public void correctTree(Node node){ // node의 부모 노드가 왼쪽 자식이면 이모 노드는 조부모 노드의 오른쪽 자식이다 if (node.parent.isLeftCh..

※ add 메소드 - add 메소드의 동작 방식은 AVL 트리와 유사하지만 isLeftChild가 추가가 되기 때문에 이 부분을 고려해 주어야 한다. add 메소드 코드의 예시는 다음과 같으며 트리가 비어있으면 노드를 추가하고 비어있지 않다면 재귀 add 메소드를 호출한다. public void add(K key, V value){ Node node = new Node(key, value); // 트리가 비어있을 경우 if (root == null) { root = node; root.black = true; size++; return; } // 트리에 노드가 있을 경우 재귀 메소드 사용 add(root, node); size++; } // add 재귀함수, 내부클래스 private void add (N..

※ 클래스 - 레드 블랙 트리 클래스는 불리언 값을 가진 black이 참이면 검은색, 거짓이면 빨간색으로 표현하고 이모 노드를 알아내기 위해 left, right, parent 노드를 가리키는 포인터 뿐만 아니라 불리언 값을 가진 isLeftChild 를 사용하기도 한다. public class RedBlackTree implements RedBlackI { Node root; int size; class Node { K key; V value; Node left, right, parent; boolean isLeftChild, black; public Node (K key, V value) { this.key = key; this.value = value; left = right = parent = n..

※ 레드 블랙 트리 - 1~10 까지의 숫자들을 레드 블랙 트리 규칙에 따라 배열하게 되면 다음과 같이 나타나게 된다. 1부터 숫자들을 하나씩 추가하며 규칙에 적합한지 확인하고 규칙을 위반할 시 회전과 색상 전환으로 규칙에 맞게 바꾸어 주면 된다. 해당하는 규칙은 이전 포스팅 글을 참고하여 연습해보는 것도 좋을 것임 레드 블랙 트리 규칙

※ Red Black Tree 규칙 - 레드 블랙 트리는 자가 균형 이진 탐색 트리로, AVL 트리처럼 스스로 균형을 잡는 트리이다. 레드 블랙 트리에서는 다음과 같은 규칙으로 정렬해 균형을 맞춘다. 규칙 1. 모든 노드는 빨간색이나 검은색이다 2. 루트는 항상 검은색이다 3. 새로 추가되는 노드는 항상 빨간색이다 4. 루트에서 잎 노드로 가는 모든 경로는 같은 수의 검은 노드가 있어야 한다 5. 어떤 경로에서도 빨간색 노드 2개가 연속으로 있어서는 안된다 6. 모든 빈 노드는 검은색이라 가정한다 균형 맞추기 1) 이모 노드가 검은색인 경우 - 회전을 하고 나면 부모 노드는 검은색, 두 자식노드는 빨간색이 되어야 한다 2) 이모 노드가 빨간색인 경우 - 색상 전환을 하고 나면 부모 노드는 빨간색, 두 자..

※ Rebalance 메소드 - Rebalance 메소드는 어느 쪽에서 균형이 깨졌는지 확인 후 회전을 하여 균형을 유지한다 public void rebalance(Node node){ if(height(node.left) - height(node.right)>1){ if(height(node.left.left) > height(node.left.right)) node = rightRotate(node); else node = leftRighttoRotate(node); } else{ if(height(node.left.left)>height(node.left.right)) node = rightLeftRotate(node); else node = leftRotate(node); } if(node.par..

※ 균형 확인 메소드 - AVL 트리에서 좌측과 우측의 높이 차가 항상 1보다 작거나 같아야 한다. 따라서, 노드를 추가했을 때 높이 차이가 1보다 커지면 회전을 해 트리의 균형을 맞춰주어야 한다. 트리의 높이 차이를 확인하고 균형을 맞추는 checkBalance 코드는 다음과 같다. public void checkBalance(Node node){ if((height(node.left) - height(node.right)>1) || (height(node.left) - height(node.right)