아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 정렬 (sort) 컴퓨터 분야에서는 데이터를 정렬해야 하는 경우가 많이 발생하는데, 이를 효과적으로 해결하기 위한 알고리즘과 이 알고리즘을 비교하는 다양한 기준이 있다. (*강의에서는 숫자를 정렬하는 경우만을 다룬다.) out-of-place 정렬 모든 데이터를 자료 구조의 복사본에 옮긴 후(저장공간) 순서대로 배열하여 정렬하는 방법이다. 책을 정리할 때 모든 책을 다 꺼내어 바닥에 두고 다시 순서대로 꽂아 정리하는 방법에 비유할 수 있다. in-place 정렬 out-of-place와 달리 자료 구조를 그대로 둔 채 그 안에서 요소의 위치만 shuffle하여 정렬하는 방법이다. 책꽂이에서 책을 하나 꺼내어 원하는 위치에 다시 꽂는 작업을 순서대로 ..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 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; } // 부모 노드가 오른쪽 자..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. RB의 규칙 레드 블랙 트리는 자가 균형 이진 탐색 트리로서, AVL 트리처럼 스스로 균형을 잡는 트리이다. Boolean으로 노드를 빨간색 혹은 검은색으로 설정한다. 규칙 1. 모든 노드는 빨간색이나 검은색 2. 루트는 항상 검은색 3. 새로 추가되는 노드는 항상 빨간색 4. 루트에서 잎 노드로 가는 모든 경로에는 같은 수의 검은색 노드가 있어야 함 (빨간 노드 개수는 다를 수 있음) 5. 어떤 경로에서도 빨간색 노드 2개가 연속으로 있어서는 안 됨 (연속된 두 블랙 노드는 가능) 6. 모든 null 노드는 검은색이라고 가정 균형을 맞추는 방법 1) 이모 노드가 검은색일 경우 회전한다. 회전을 하고 나면 부모 노드는 검은색, 두 자식 노드는 빨간색..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. checkBalance 메소드 AVL 트리에서는 왼쪽과 오른쪽의 높이 차이가 항상 1보다 작거나 같아야 하므로, 노드를 추가하였을 때 높이의 차이가 1보다 커지면 회전으로 트리의 균형을 맞춰줘야 한다. checkBalance 메소드를 통해 트리의 높이 차이를 확인하고 균형을 맞춘다. 1보다 크지 않으면 계속해서 올라가서 루트까지 확인한다. public void checkBalance(Node node){ // 높이 차이가 1 초과 혹은 -1 미만 (AVL 트리 규칙 위반) if ((height(node.left) - height(node.right)>1) || (height(node.left) - height(node.right) 오른쪽 자식 if ..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. AVL 트리 AVL 트리는 스스로 균형을 잡는 이진 탐색 트리이다. 왼쪽과 오른쪽의 높이 (자식의 수) 차이 = 균형인수(Balance factor, BF)가 항상 1보다 작거나 같아야 한다. 즉, 왼쪽과 오른쪽의 높이 차이가 0, -1, 1 외의 다른 수가 나와서는 안된다. 예제 1) 예제 2) AVL 트리 : 노드 왼, 오른쪽 포인터 + 부모 노드 포인터를 선언한다. class Node{ T data;// 노드에 저장할 데이터 Node left; Node right; Node parent; // 생성자 public Node(T obj){ data = obj; parent = left = right = null; } add 메소드, 재귀 add 트..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 회전 균형(balance) 잡힌 트리를 만들기 위해 트리의 노드 위치를 바꾸는 과정이다. 위처럼 마치 연결리스트와 같이 한 방향으로 나열된 트리는 구조 자체는 문제없이 가능하나 탐색에 걸리는 시간 복잡도가 O(n)이 되어버린다. 본래 일반적으로 균형이 잡힌 이진트리에서 요소를 탐색하는 시간 복잡도가 O(log n)인 것과 대조하여 위와 같은 트리는 매우 비효율적이다. 따라서 회전을 통해 트리를 균형 있게 만들 수 있다. 트리에서 부모 노드보다 작은 데이터가 왼쪽 자식 노드에 와야 하고, 더 큰 데이터가 오른쪽 자식 노드에 와야하므로 트리가 한 쪽으로 치우친 경우 다음과 같이 조부모 노드, 부모 노드, 자식 노드의 크기 관계에 따라 우측 회전, 혹은 ..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 노드 클래스 트리에서는 부모 노드보다 작은 데이터가 왼쪽 자식 노드에 위치하고 부모보다 큰 데이터가 오른쪽 자식노드에 위치해야 한다. 어떤 수를 찾으려고 하면 부모보다 작으면 왼쪽으로, 크면 오른쪽으로 이동하면 된다. 전체 데이터의 반은 무시하고 log n의 복잡도를 가진다. 연결리스트에서 next 포인터를 가졌듯, 트리에서는 left, right 포인터를 갖도록 만든다. class Node { E data; Node left, right; public Node(E obj){ this.data = obj; left=right=null; } } 재귀 함수: add 트리에 새로운 데이터를 add로 추가하기 (재귀: 함수에서 자기 자신을 다시 호출해 작업..
