균형 이진 탐색 트리 개념과 자바로 구현해보기

1. 균형 이진 트리

• 모든 노드의 좌우 서브 트리 높이가 1이상 차이 나지 않는 트리

균형 이진 트리 예시

균형 이진 트리가 아닌 예시

  2. 이진 탐색 트리의 편향 발생

• Case 1) 이진 탐색 트리에 삽입되는 순서 : 20 → 10 → 30 → 5

• Case 2) 이진 탐색 트리에 삽입되는 순서 : 5 → 10 → 20 → 30

3. 균형 이진 탐색 트리

• Balanced Binary Search Tree
• 노드의 삽입과 삭제가 일어날 때 균형을 유지하도록 하는 트리
  • 2번의 Case 2) 이 발생하지 않도록 한다.

균형이 1 이상 넘지 않도록 유지하는 예시

• AVL 트리
  • 노드가 삽입, 삭제될 때 트리의 균형을 체크하고 유지하는 트리
  • 각 노드의 BF를 [-1,0,1] 만 가지게 하여 균형을 유지
    • BF (Balance Factor) 란?
      • 왼쪽 서브 트리 높이 - 오른쪽 서브 트리 높이
  • 리밸런싱
    • 균형이 깨진 경우
      • BF가 '+' 이면 왼쪽 서브 트리에 이상이 있음
      • BF가 '-' 이면 오른쪽 서브 트리에 이상이 있음
    • 회전 연산
      • 단순 회전 - LL, RR
      • 이중 회전 - LR, RL
    • LL 트리란?
      • Left - Left
      • 회전 1회
      • 오른쪽 방향으로 회전
    • RR 트리란?
      • Right - Right
      • 회전 1회
      • 왼쪽 방향으로 회전
    • LR 이란?
      • Left - Right
      • 회전 2회
      • RR 회전 후 LL 회전
    • RL 이란?
      • Right - Left
      • 회전 2회
      • LL 회전 후 RR 회전

---

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 case
	public Node rightRotate(Node node) {
		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;
	}

	// RR case
	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;
	}

	// LR case
	public Node lrRotate(Node node) {
		node.left = leftRotate(node.left);
		return rightRotate(node);
	}

	// RL case
	public Node rlRotate(Node node) {
		node.right = rightRotate(node.right);
		return leftRotate(node);
	}

	public int getBalance(Node node) {
		if (node == null) {
			return 0;
		}

		return this.height(node.left) - this.height(node.right);
	}

	public void insert(int key) {
		this.head = this.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 = this.insert(node.left, key);
		} else {
			node.right = this.insert(node.right, key);
		}

		// 높이 갱신
		node.height = Math.max(this.height(node.left), this.height(node.right)) + 1;

		// 이상 여부 판단
		int balance = this.getBalance(node);

		// LL
		if (balance > 1 && key < node.left.key) {
			return this.rightRotate(node);
		}

		// RR
		if (balance < -1 && key > node.right.key) {
			return this.leftRotate(node);
		}

		// LR
		if (balance > 1 && key > node.left.key) {
			return this.lrRotate(node);
		}

		// RL
		if (balance < -1 && key < node.right.key) {
			return this.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) {
		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
*/

// 삭제

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(this.height(node.left), this.height(node.right)) + 1;

		int balance = this.getBalance(node);

		// LL
		if (balance > 1 && this.getBalance(node.left) > 0) {
			return this.rightRotate(node);
		}

		// RR
		if (balance < -1 && this.getBalance(node.right) < 0) {
			return this.leftRotate(node);
		}

		// LR
		if (balance > 1 && this.getBalance(node.left) < 0) {
			return this.lrRotate(node);
		}

		// RL
		if (balance < -1 && this.getBalance(node.right) > 0) {
			return this.rlRotate(node);
		}

		return node;
	}
}

public class Practice2 {

	public static void main(String[] args) {
		AVLTree2 avl = new AVLTree2();

		avl.insert(30);
		avl.insert(20);
		avl.insert(40);
		avl.insert(10);
		avl.levelOrder(avl.head);
		avl.delete(40);
		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 
	 */
}