균형 이진 탐색 트리
균형 이진 트리
모든 노드의 좌우 서브 트리 높이가 1이상 차이 나지 않는 트리
이진 탐색 트리의 편향 발생
Case 1) 이진 탐색 트리에 삽입되는 순서: 20 → 10 → 30 → 5
Case 2) 이진 탐색 트리에 삽입되는 순서: 5 → 10 → 20 → 30
균형 이진 탐색 트리
Balanced Binary Search Tree
노드의 삽입과 삭제가 일어날 때 균형을 유지하도록 하는 트리
AVL 트리, Red-Black 트리
AVL 트리
노드가 삽입, 삭제될 때 트리의 균형을 체크하고 유지하는 트리
각 노드의 BF를 [-1, 0, 1] 만 가지게 하여 균형을 유지
BF (Balance Factor)
왼쪽 서브 트리 높이 - 오른쪽 서브 트리 높이
AVL 트리 - 리밸런싱
균형이 깨진 경우,
BF가 ‘+’ 이면 왼쪽 서브 트리에 이상이 있음
BF가 ‘-’ 이면 오른쪽 서브 트리에 이상이 있음
회전 연산
단순 회전 - LL, RR
이중 회전 - LR, RL
AVL 트리 – LL
LL (Left-Left)
회전 1회
오른쪽 방향으로 회전
AVL 트리 – RR
RR (Right-Right)
회전 1회
왼쪽 방향으로 회전
AVL 트리 – LR
LR (Left-Right)
회전 2회
RR 회전 후 LL 회전
AVL 트리 – RL
RL (Right-Left)
회전 2회
LL 회전 후 RR 회전
AVL 트리 - 삽입
// 비선형 자료구조 - 이진 탐색 트리_2
// AVL 트리 - 삽입
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;
}
public Node rightRotate(Node node) {
Node lNode = node.left;
node.left = lNode.right;
lNode.right = node;
//노드의 높이 업데이트, 자식노드의 높이중 큰걸 가져와 + 1 해줘야 본인의 높이가 되니까.
node.height = Math.max(height(node.left), height(node.right)) + 1;
lNode.height = Math.max(height(lNode.left), height(lNode.right)) + 1;
//lNode가 루트 노드가 되니 이걸 리턴해줘서 연결 시킬 수 있게하려고 lNode를 리턴.
return lNode;
}
public Node leftRotate(Node node) {
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) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
public Node rlRotate(Node node) {
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){
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;
}
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 Practice1 {
public static void main(String[] args) {
// Test code
AVLTree avl = new AVLTree();
// 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);
}
}
20 10 30
20 10 40 30 50
20 7 40 5 10 30 50
20 7 40 5 10 30 55 50 60
AVL 트리 - 삭제
// AVL 트리 - 삭제
class AVLTree2 extends AVLTree{
public void delete(int key) {
this.head = delete(this.head, key);
}
public Node delete(Node node, int key) {
if (node == null) {
return null;
}
if (key < node.key) {
node.left = delete(node.left, key);
} else if (key > node.key) {
node.right = delete(node.right, key);
} else {
//자식이 하나인 경우나 없는 경우의 케이스.
if (node.left == null) {
return node.right;
} else if (node.right == null) {
return node.left;
} else {
//자식이 둘인 경우의 케이스
Node predecessor = node;
Node successor = node.left;
while (successor.right != null) {
predecessor = successor;
successor = successor.right;
}
predecessor.right = successor.left;
node.key = successor.key;
}
}
node.height = Math.max(height(node.left), height(node.right)) + 1;
int balance = getBalance(node);
//getBalance(node.left) 이걸로 LL인지, LR인지 구분
// 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 class Practice2 {
public static void main(String[] args) {
// Test code
AVLTree2 avl = new AVLTree2();
avl.insert(30);
avl.insert(20);
avl.insert(40);
avl.insert(10);
avl.levelOrder(avl.head);
avl.delete(40); // LL
avl.levelOrder(avl.head);
avl.insert(40);
avl.delete(10); // RR
avl.levelOrder(avl.head);
avl.insert(25);
avl.delete(40); // LR
avl.levelOrder(avl.head);
avl.insert(27);
avl.delete(20); // RL
avl.levelOrder(avl.head);
}
}
30 20 40 10
20 10 30
30 20 40
25 20 30
27 25 30
공부인증
출처 : 제로베이스
Leave a comment