균형 이진 트리
- 모든 노드의 좌우 서브 트리 높이가 1이상 차이 나지 않는 트리
편향 발생
- 이진 탐색 트리에 삽입되는 순서에 따라 편향이 발생할 수 있다.
- 예시
1) 삽입 순서: 20 -> 10 -> 30 -> 5
2) 삽입 순서: 5 -> 10 -> 20 -> 30 (편항 발생)
이런 편향이 발생하는 노드의 삽입이나 삭제가 일어났을 때, 균형을 유지하도록 하는 트리가 균형 이진 탐색 트리이다.
그 종류에는 AVL트리, Red-Black트리가 있다.
AVL 트리
- 노드가 삽입, 삭제될 때 트리의 균형을 체크하고 유지하는 트리
- 각 노드의 BF를 [-1, 0 ,1]만 가지게 하여 균형을 유지
- BF(Balance Factor)
-> (왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이)
리밸런싱
- 균형이 깨진 경우
- BF가 '+'이면 왼쪽 서브 트리에 이상이 있음- BF가 '-'이면 오른쪽 서브 트리에 이상이 있음
- 회전 연산
- 단순 회전: LL, RR- 이중 회전: LR, RL
- 회전 연산의 이름은 현재 트리의 상태를 기준으로 지은 것
- LL: 왼쪽으로 두개의 자식 노드가 연속됨- RR: 오른쪽으로 두개의 자식 노드가 연속됨
- LR: 왼쪽으로 하나의 자식 노드, 그리고 그 자식 노드의 오른쪽으로 하나의 자식노드가 이어짐
- RL: 오른쪽으로 하나의 자식 노드, 그리고 그 자식 노드의 왼쪽으로 하나의 자식노드가 이어짐
LL
- 회전 1회
- 오른쪽 방향으로 회전
RR
- 회전 1회
- 왼쪽 방향으로 회전
LR
- 회전 2회
- RR회전 후 LL회전
RL
- 회전 2회
- LL회전 후 RR회전
AVL 구현 코드
// AVL 트리 - 삽입, 삭제
import sun.nio.cs.ext.MacHebrew;
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;
this.height = 0;
this.left = left;
this.right = right;
}
}
class AVLTree {
Node head;
//현재 노드의 높이를 반환해주는 메소드
public int height(Node node) {
if(node == null){
return -1;
}
return node.height;
}
//LL. 오른쪽 방향 회전. 매개변수는 균형이 깨진 서브트리를 넣어줘야하기 때문에, 그 서브트리의 가장 상위(헤드)인 node가 매개변수
public Node rightRotate(Node node) {
Node lNode = node.left; //node의 왼쪽 자식 노드를 lNode
node.left = lNode.right; //lNode에게 오른쪽 자식 노드가 있으면, 그 노드를 node의 왼쪽 자식으로 삽입(크기 비교 상), 업으면 null이 들어가게 됨
lNode.right = node; //node를 lNode의 오른쪽 자식 노드로 보냄
//높이 설정
//각각 자신의 자식 노드들의 높이 값 중 큰 것에 +1을 한다. +1을 하는 이유는 자기 자신을 포함해야하기 때문
node.height = Math.max(height(node.left), height(node.right)) + 1;
lNode.height = Math.max(height(lNode.left),height(lNode.right)) + 1;
return lNode; //lNode가 이 서브 트리에서 가장 상위 노드가 되었으므로 lNode 반환하면 그 서브트리가 반환되는 것
}
//RR. 왼쪽 방향 회전
public Node leftRotate(Node node) {
Node rNode = node.right; //node의 오른쪽 자식 노드 rNode
node.right = rNode.left; //rNode에게 왼쪽 자식 노드가 있으면, 그 노드를 node의 오른쪽 자식 노드로 삽입. 없으면 null
rNode.left = node; //node를 rNode의 왼쪽 자식노드로 보냄
//높이 설정
node.height = Math.max(height(node.left), height(node.right)) + 1;
rNode.height = Math.max(height(rNode.left),height(rNode.right)) + 1;
return rNode;
}
//LR, 왼쪽 방향 회전 후 오른쪽 방향 회전
public Node lrRotate(Node node) {
node.left = leftRotate(node.left); //1차 회전. node의 자식 노드를 헤드로 하는 서브 트리를 왼쪽 방향 회전
return rightRotate(node); //2차 회전. node를 헤드로 하는 서브 트리를 오른쪽 회전
}
//RL, 오른쪽 방향 회전 후 왼쪽 방향 회전
public Node rlRotate(Node node) {
node.right = rightRotate(node.right); //1차 회전. node의 자식 노드를 헤드로 하는 서브 트리를 왼쪽 방향 회전
return leftRotate(node); //2차 회전. node를 헤드로 하는 서브 트리를 오른쪽 회전
}
//BF(Balance Factor)를 구하는 메소드
public int getBalance(Node node) {
if(node == null){
return 0;
}
return height(node.left) - height(node.right);
}
//노드를 트리에 삽입하는 메소드. 키 값을 받으면 아래에 있는 insert 메소드를 호출해서 this.head에 넣어줄거임(트리를 넣어주는 것)
//재귀로 넣어주기 위해 메소드를 따로 만듬
public void insert(int key) {
this.head = insert(this.head, key);
}
//재귀로 동작하는 삽입 메소드
public Node insert(Node node, int key) {
if(node == null){ //null을 만나면, 즉 빈 곳을 만나면 새로운 Node 객체를 만들어서 그 자리에 넣어줌
return new Node(key, null, null);
}
if(key < node.key){ //새로운 값이 node의 값보다 작으면 왼쪽으로 보냄
node.left = insert(node.left, key);
}else{ //새로운 값이 node의 값보다 크면 오른쪽으로 보냄
node.right = insert(node.right, key);
}
//위에서의 재귀가 종료되면 각각의 노드들은 자신의 높이값을 업데이트 해준다
node.height = Math.max(height(node.left), height(node.right)) + 1;
//균형을 체크하기 위해 BF값을 구한다
int balance = getBalance(node);
//각각의 상황에 따른 회전을 적용
//LL
if(balance > 1 && key < node.left.key){
return rightRotate(node);
}
//RR
if(balance < -1 && key > node.right.key){
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;
}
//노드를 트리에서 삭제하는 메소드. 키 값을 받으면 아래에 있는 delete 메소드를 호출해서 this.head에 넣어줄거임(트리를 넣어주는 것)
//재귀로 처리하기 위해 메소드를 따로 만듬
public void delete(int key){
this.head = delete(this.head, key);
}
public Node delete(Node node, int key){
//지우려는 값을 만나지 못하고 null까지 오면 null을 반환해준다
if(node == null){
return null;
}
if(key < node.key){ //지우려는 값이 node.key보다 작으면 왼쪽 자식 노드로 보냄
node.left = delete(node.left, key);
}else if(key > node.key){ //지우려는 값이 node.key보다 크면 오른쪽 자식 노드로 보냄
node.right = delete(node.right, key);
}else{ //지우려는 값을 만났으면
if(node.left == null){ //자식 노드가 오른쪽에 있거나 or 자식 노드가 없으면
return node.right; //오른쪽 자식 노드를 반환해준다 = 지우려는 노드 자리에 반환하는 것이므로, 지우려는 노드는 사라진다. 자식이 없으면 null을 반환
}else if(node.right == null){ //자식 노드가 왼쪽에 있거나 or 자식 노드가 없으면
return node.left;
}else{ //자식 노드가 2개가 있으면, 왼쪽 서브 트리에서 가장 큰 값을 찾아서 올려주고 지우려는 값을 삭제해야함
Node predecessor = node; //부모 노드 역할로 계속 따라다님
Node successor = node.left; //왼쪽으로 들어감
while(successor.right != null){ //오른쪽 자식 노드가 없을때까지 = 더 큰 값이 없을때까지
predecessor = successor;
successor = successor.right;
}
predecessor.right = successor.left; //왼쪽 자식 노드가 있으면 올려보내고, 없으면 null
node.key = successor.key; //node의 값을 없애고, successor의 값을 올려보내는 거니깐 결국 값만 대입시켜주면 됨
}
}
node.height = Math.max(height(node.left), height(node.right)) + 1;
//균형을 체크하기 위해 BF값을 구한다
int balance = getBalance(node);
//각각의 상황에 따른 회전을 적용
//LL, 삭제이므로 삽입때와는 조금 다르게 검증.
//밸런스가 1보다 크므로 왼쪽으로 치우쳐있고,
//LL임을 확인하기 위해서는 헤드 바로 밑의자식 노드의 BF가 양수이면 왼쪽으로 더 붙어있는 것이기 때문에 LL
if(balance > 1 && getBalance(node.left) > 0){
return rightRotate(node);
}
//RR
if(balance < -1 && getBalance(node.right) < 0){
return leftRotate(node);
}
//LR
if(balance > 1 && getBalance(node.left) < 0){
return lrRotate(node);
}
//RL
if(balance < -1 && getBalance(node.right) > 0){
return rlRotate(node);
}
return node;
}
//출력을 위한 레벨 순회
public void levelOrder(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 Main {
public static void main(String[] args) {
// Test code
AVLTree avl = new AVLTree();
// Insert
System.out.println("AVL - Insert");
avl.insert(30);
avl.insert(20);
avl.insert(10); // LL
avl.levelOrder(avl.head);
avl.insert(40);
avl.insert(50); // RR
avl.levelOrder(avl.head);
avl.insert(5);
avl.insert(7); // LR
avl.levelOrder(avl.head);
avl.insert(60);
avl.insert(55); // RL
avl.levelOrder(avl.head);
// Delete
System.out.println("AVL2 - Delete");
AVLTree avl2 = new AVLTree();
avl2.insert(30);
avl2.insert(20);
avl2.insert(40);
avl2.insert(10);
avl2.levelOrder(avl2.head);
avl2.delete(40); // LL
avl2.levelOrder(avl2.head);
avl2.insert(40);
avl2.delete(10); // RR
avl2.levelOrder(avl2.head);
avl2.insert(25);
avl2.delete(40); // LR
avl2.levelOrder(avl2.head);
avl2.insert(27);
avl2.delete(20); // RL
avl2.levelOrder(avl2.head);
}
}