균형 이진 탐색 트리
영어로는 Balenced Binary Search Tree 라고 명명한다.
노드를 삽입하거나 삭제할 때 트리가 오른쪽과 왼쪽 길이의 균형을 이루도록 하는 것이다.
균형을 이룬다는 것은 양쪽의 길이 차이가 1을 초과하지 않는 것을 말한다.
기본적으로 이진 탐색 트리의 성질을 유지하고 있어야 한다. (이진탐색트리: https://imcoding.tistory.com/4 )
AVL트리와 Red-Black트리가 있으며, AVL트리에 대해 다뤄보겠다.
왼쪽 Case1은 30, 20, 40, 10 순서로 노드가 들어온 이진 탐색 트리이다. 그리고 왼쪽과 오른쪽의 길이 차이가 1을 초과하지 않기 때문에 균형 이진 탐색 트리로 볼 수 있다.
반면 Case2는 5, 10, 20, 30 순서로 노드가 들어와서 왼쪽에는 자식 노드가 없으며, 오른쪽에만 3개가 연결되어 양쪽의 길이차이가 0과 3으로 1을 초과하기 때문에 불균형으로 볼 수 있다.
AVL트리
트리에 노드가 삽입, 삭제될 때마다 균형을 체크하고 유지하는 트리를 말한다.
왼쪽 서브트리와 오른쪽 서브트리의 높이 차이는 BF(Balance Facor) 라고 한다.
따라서 BF가 -1, 0, 1 셋 중 하나일 경우 균형으로 볼 수 있으며, 균형이 깨졌을 경우 BF가 양수면 왼쪽, 음수면 오른쪽 서브트리가 비정상적으로 더 긴 것을 알 수 있다.
균형이 깨진 경우 회전연산을 통해 균형을 맞출 수가 있다. 회전연산에는 LL, RR, LR, RL 네가지가 있다.
노드가 삽입하면서 회전연산을 통해 불균형트리를 균형트리로 맞춰주는 코드를 구현해보곘다.
먼저 노드클래스를 만들고 기본 변수를 생성한다.
class Node {
int key;
int height;
Node left;
Node right;
public Node(int key, Node left, Node right) {
this.key = key; // 노드의 key값
this.height = 0; // 노드의 높이
this.left = left; // 노드의 left 자식값
this.right = right; // 노드의 right 자식값
}
}노드 삽입
아래는 노드 삽입과 관련된 코드이다.
노드가 삽입되고 LL, RR, LR, RL인 각각의 경우에 맞는 메서드를 구현하고 이진트리의 균형을 맞춰보겠다.
public void insert(int key) { // 노드삽입
this.head = insert(this.head, key);
}
public Node insert(Node node, int key) { // 노드삽입을 재귀적으로 돌면서 균형 맞춰줄 것
if (node == null) { // 맨 처음 key값이 들어왔을때 head노드는 null값일것
return new Node(key, null, null); // head노드가 null값일 때 처음 key값이 head가된다
}
if (key < node.key) { // 가장 맨 위의 node부터 차례로 key값과 비교하며 key값을 적당한 위치에 붙여준다.
node.left = insert(node.left, key);
} else {
node.right = insert(node.right, key);
}
node.height = Math.max(height(node.left), height(node.right)) + 1;
// insert 함수를 재귀적으로 돌면서 key값과 node.key을 비교하며 node는 계속 갱신된다.
// 그렇게 각각의 node의 height 정보를 저장해가며 아래 getBalance 함수에서 균형을 검사한다.
int balance = getBalance(node);
//LL
if (balance > 1 && key < node.left.key) { // 왼쪽의 height이 오른쪽보다 2이상 큰 경우
return rightRotate(node);
}
//RR
if (balance < -1 && key > node.right.key) { // 오른쪽의 height이 왼쪽보다 2이상 큰 경우
return leftRotate(node);
}
//LR
if (balance > 1 && key > node.left.key) {
return lrRotate(node);
}
//RL
if (balance < -1 && key < node.right.key) {
return rlRotate(node);
}
return node;
}
public int getBalance(Node node) { // 길이를 비교해 양쪽이 균형을 이루는지 검사
if (node == null) {
return 0;
}
return height(node.left) - height(node.right);
}
AVL트리 - LL
먼저 LL (Left-Left) 이다.
위 코드에서 노드의 삽입 순서는 30, 20, 10, 15이다.
이 경우에 BF가 1을 초과한 불균형 이진트리이다.
균형을 맞추기 위해서는 불균형이 시작된 노드부터 오른쪽으로 회전시키면 된다.
사진에서는 20에서 오른쪽으로 회전시키면 되겠다.
그리고 만약 해당 노드의 right 노드(15)가 있다면, 원래 자리에 있던 노드(30)의 left로 옮겨주면 되겠다.
코드를 통해 구현해보겠다.
class AVLTree {
Node head;
public int height(Node node) {
if (node == null) {
return -1;
}
return node.height;
}
public Node rightRotate(Node node) { // LL
Node lNode = node.left; //
node.left = lNode.right; //
lNode.right = node; // 30
node.height = Math.max(height(node.left), height(node.right)) + 1;
lNode.height = Math.max(height(lNode.left), height(lNode.right)) + 1;
// 더 높은 높이값 정보를 저장해간다.
return lNode; // 회전 후의 height
}
AVL트리 - RR
LL인 경우와 방향만 반대고 메커니즘은 동일하다.
불균형이 일어난 노드(20)을 중심으로 왼쪽으로 회전시키고, 만약 해당 노드의 left에 자식노드가 있다면 위치가 바뀐 노드의 right로 연결해주면 된다.
코드 역시 메커니즘은 동일하다.
public int height(Node node) {
if (node == null) {
return -1;
}
return node.height;
}
public Node leftRotate(Node node) { // RR
Node rNode = node.right;
node.right = rNode.left;
rNode.left = node;
node.height = Math.max(height(node.left), height(node.right)) + 1;
rNode.height = Math.max(height(rNode.left), height(rNode.right)) + 1;
return rNode;
}
AVL트리 - LR
Left, Right로 사진처럼 불균형이 일어난 경우이다.
총 회전을 두번 시켜줘야하는데, 먼저 불균형이 일어난 지점에서 RR과 마찬가지로 왼쪽으로 회전해준다.
그리고 회전한 중간지점을 기준으로 오른쪽 회전해준다.
코드는 위에서 RR인 경우에 구현한 코드를 가져와 사용하면 된다.
public Node leftRotate(Node node) { // RR
Node rNode = node.right;
node.right = rNode.left;
rNode.left = node;
node.height = Math.max(height(node.left), height(node.right)) + 1;
rNode.height = Math.max(height(rNode.left), height(rNode.right)) + 1;
return rNode;
}
public Node lrRotate(Node node) { // LR
node.left = leftRotate(node.left); // RR, node.left를 중심으로 왼쪽회전 (node = 30)
return rightRotate(node); // 왼쪽회전한 것을 다시 오른쪽 회전
AVL트리 - LR
RL과 방향만 다르고 동일한 메커니즘이다.
불균형이 일어난 지점에서 오른쪽회전, 이후 다시 왼쪽회전이다.
이것 역시 LL에서의 코드를 가져오면 된다.
public Node rightRotate(Node node) { // LL
Node lNode = node.left;
node.left = lNode.right;
lNode.right = node;
node.height = Math.max(height(node.left), height(node.right)) + 1;
lNode.height = Math.max(height(lNode.left), height(lNode.right)) + 1;
return lNode; // 회전 후의 height
}
public Node lrRotate(Node node) { // LR
node.left = leftRotate(node.left);
return rightRotate(node);
}
여기까지 균형 이진 탐색 트리의 개념과 코드를 설명했다.
코드가 길고, 여러 메서드로 나뉘어있어서 다소 헷갈릴 수 있다.
아래 전체 코드를 보면서 직접 그려보고 진득하게 이해하는 과정이 필요하다.
import java.util.LinkedList;
import java.util.Queue;
class Node {
int key;
int height;
Node left;
Node right;
public Node(int key, Node left, Node right) {
this.key = key; // 노드의 key값
this.height = 0; // 노드의 높이
this.left = left; // 노드의 left 자식값
this.right = right; // 노드의 right 자식값
}
}
class AVLTree {
Node head;
public int height(Node node) {
if (node == null) {
return -1;
}
return node.height;
}
public Node rightRotate(Node node) { // LL
Node lNode = node.left;
node.left = lNode.right;
lNode.right = node;
node.height = Math.max(height(node.left), height(node.right)) + 1;
lNode.height = Math.max(height(lNode.left), height(lNode.right)) + 1;
return lNode; // 회전 후의 height
}
public Node leftRotate(Node node) { // RR
Node rNode = node.right;
node.right = rNode.left;
rNode.left = node;
node.height = Math.max(height(node.left), height(node.right)) + 1;
rNode.height = Math.max(height(rNode.left), height(rNode.right)) + 1;
return rNode;
}
public Node lrRotate(Node node) { // LR
node.left = leftRotate(node.left); // 회전하는 대상에 주목
return rightRotate(node);
}
public Node rlRotate(Node node) { // RL
node.right = rightRotate(node.right);
return leftRotate(node);
}
public int getBalance(Node node) { // 균형정보계산
if (node == null) {
return 0;
}
return height(node.left) - height(node.right);
}
public void insert(int key) { // 노드삽입
this.head = insert(this.head, key);
}
public Node insert(Node node, int key) { // 노드삽입을 재귀적으로 돌면서 균형 맞춰줄 것
if (node == null) {
return new Node(key, null, null);
}
if (key < node.key) {
node.left = insert(node.left, key);
} else {
node.right = insert(node.right, key);
}
node.height = Math.max(height(node.left), height(node.right)) + 1;
int balance = getBalance(node);
//LL
if (balance > 1 && key < node.left.key) { // 왼쪽의 height이 오른쪽보다 2이상 큰 경우
return rightRotate(node);
}
//RR
if (balance < -1 && key > node.right.key) { // 오른쪽의 height이 왼쪽보다 2이상 큰 경우
return leftRotate(node);
}
//LR
if (balance > 1 && key > node.left.key) {
return lrRotate(node);
}
//RL
if (balance < -1 && key < node.right.key) {
return rlRotate(node);
}
return node;
}
public void printTree(Node node) {
Queue<Node> queue = new LinkedList();
queue.add(node);
while (!queue.isEmpty()) {
Node cur = queue.poll();
System.out.print(cur.key + " ");
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
System.out.println();
}
}
public class Practice1 {
public static void main(String[] args) {
// Test code
AVLTree avl = new AVLTree();
// Insert
avl.insert(30);
avl.insert(20);
avl.insert(10);
avl.printTree(avl.head);'자바' 카테고리의 다른 글
| [자바] 힙(Heap) - 최대힙 / 최소힙 개념과 구현. java (0) | 2022.06.22 |
|---|---|
| [자바] 업캐스팅과 다운캐스팅 (0) | 2022.06.21 |
| [자바] 이진 탐색 트리 (Binary Search Tree) (0) | 2022.06.18 |
| [자바] Tree의 개념, 종류, 재귀함수를 이용한 구현까지 (0) | 2022.06.17 |
| [자바] 1차원 배열과 2차원 배열, 가변배열의 오름차순, 내림차순 정렬 (0) | 2022.06.16 |