TIL 정리_90

 

AVL 트리 

스스로 균형을 잡는 이진 트리 자료구조를 말한다.

왼쪽과 오른쪽의 높이 차이는 항상 1보다 작거나 같아야 한다
높이의 차이가 1보다 커지면 트리의 규칙을 어긴것이다

예시 1
  4 (노드)
2    8
      10
        12 
불안정 
-> 조부모 노드인 8을 좌측 회전을 해야 한다 

예시 1 회전 후 
  4
2   10
    8  12
트리의 균형을 되찾음 

 

예시 2 
  10
8   12
4
2
AVL 규칙에 어긋난다
-> 8에 대해서 우측 회전을 해야한다 

 

회전 후 
     10
  4     12
2   8

왼쪽 자식의 서브 트리에서 문제가 생긴 경우 조부모인 10이 좌측-우측회전을 해야한다
-> 문제 해결을 위해 회전을 해야한다

회전을 할 때는 루트로 올라가서 방금 한 회전이 트리 위쪽에 새로운 문제를 야기했는지 확인해야 한다
만약 문제가 발생시 고쳐야 한다 

 

AVL 트리의 코드 

class Node<T> {
T data;
Node<T> lt;
Node<T> rt;
Node<T> parent; //부모노드 포인터 

public Node(T obj) {
data = obj;
parent = lt = rt = null; //초기화 
}

 

AVL 트리와 add 

상수시간안에 트리의 크기를 알 수 있도록 크기를 저장한다 
클래스를 생성 후, 트리가 비어있으면 노드를 추가하고,

비어있지 않다면 add 메소드를 재귀로 호출한다 

 

public AVLTree() { //AVL 클래스의 생성자 
root = null;
currentSize = 0;
}
public void add(E obj) {
Node<E> node = new Node<E>(obj);
if(root == null) {
root = node;
currentSize++;
return;
} 
//트리에 노드가 있을 경우 재귀로 호출 
add(root, node);
}
//재귀 add 메서드
public void add(Node<E> parent, Node<E> newNode) {
//newNode의 data가 parent의 data보다 크면 트리의 오른쪽에 추가한다
If(((Comparable<E>)newNode.data.compareTo(parent.data)>0) {
If (parent.right == null) {
parent.right = newNode;
newNode.parent = parent;
currentSize++;
}
else {
add(parent.right, newNode);
} //newNode의 data가 parent의 data보다 작거나 같으면 트리의 왼쪽에 추가한다
else {
if(parent.left == null) {
parent.left = newNode;newNode.parent = parent;
currentSize++;
}
else {
add(parent.left, newNode);
}
checkBalance(newNode); //요소를 추가하고 균형을 확인한다 
}

 

 

균형확인 메서드 checkBalance() 
트리를 올라가면서 루트에 도달할 때까지 높이의 차이를 확인한다

public void checkBalance(Node<E> node) {
If( (height(node.left) - height(node.right)>1) ||
(height(node.left) - height(node.right)<-1)) {
rebalance(node);
}
If(node.parent == null) return; //부모노드가 null인지 확인
checkBalance(node.parent); //균형이 맞는지 확인 
}

 

rebalance 메서드 
왼쪽 자식와 오른쪽 자식을 비교하여 어느쪽에서 균형이 깨졌는지 확인하고,
회전을 통해 균형을 유지한다 

public void rebalance(Node<E> node) {
If(height(node.left)-height(node.right) > 1) {
if(height(node.left.left) > height(node.left.right)) //왼쪽 서브 트리 > 오른쪽 서브 트리
node = rightRotate(node); //우측 회전
else 
node = leftRightRotate(node); //좌 - 우 회전
}
else {
if(height(node.left.left) > height(node.left.right))
node = rightLeftRotate(node); //우 - 좌 회전 
else 
node = leftRotate(node); //좌측 회전
}
If(node.parent == null) //루트로 올때까지 반복 
root = node;
}