CS/자료구조(Data Structure)
[자료구조] 트리, AVL 트리
ysk(0soo)
2022. 8. 14. 18:43
AVL Tree (AVL은 발명자 세명의 이름에서 따왔다)
자가 균형 이진 탐색 트리.
이진 탐색 트리에서, 노드들이 삽입시 한쪽으로 편향되면 결국 탐색에서 O(N)의 시간이 걸리게 된다.
* 그림 : 편향트리.
이진 탐색 트리의 편향트리를 극복하기 위해 재구성(회전, Rotate)을 통해 트리를 균형있게 만든다.
AVL 트리는 다음과 같은 특징을 가진다.
- 이진 탐색 트리(BST)의 속성을 가진다.
- 왼쪽, 오른쪽 서브 트리의
높이차이가 최대 1이다. - 삽입, 삭제 등 어떤 시점에서 높이 차이가 1보다 커지면 회전(Ratation)을 통해 균형을 맞춰 높이를 1로 맞춘다.
- AVL 트리는 높이를 logN으로 유지하기 떄문에 삽입, 검색 ,삭제의 시간 복잡도는 O(log N) 이다.
AVL 트리는 균형이 무너졌는지에 대해 판단할 떄 Balance Factor (BF) 라는 것을 이용합니다.
- AVL 트리는 모든 노드의 BF가 -1, 0, 1중 하나여야 합니다. 이를 벗어나면 균형이 깨진것이고, 회전이 필요합니다.
Banlace Factor(BF)
균형이 무너졌는지 확인하는것.
> BF(K) = height(left(k)) - height(right(k))k의 왼쪽 서브트리 높이 - k의 오른쪽 서브트리 높이
> BF가 1이면 왼쪽 서브트리가 오른쪽 서브트리보다 높이가 한 단계 높은것. > BF가 0이면 왼쪽 서브트리와 오른쪽 서브트리의 높이가 같은것. > BF가 -1이면 왼쪽 서브트리가 오른쪽 서브트리보다 높이가 한 단계 낮은것.즉 BF값이 범위를 벗어났을 떄 양수이면 왼쪽 서브트리가 더 높이가 높은것
음수이면 오른쪽 서브트리가 더 높이가 높은것
- ex ) -2, -3 이면 음수이므로 오른쪽 서브트리의 높이가 더높은것
- ex) 2, 3 이면 양수이므로 왼쪽 서브트리의 높이가 더 높은것
그림 : 트리의 높이
그림 : 각 트리의 높이에 따른 BF(K) 값
- 10 : 왼쪽 서브트리 높이 1, 오른쪽 서브트리 높이 1 .
1-1 = 0 - 30 : 자식이 없으므로 높이 0
- 20 : 왼쪽 서브트리 높이 2 오른쪽 서브트리 높이 1.
2-1 = 1 - 50 : 왼쪽 서브트리 높이 3 오른쪽 서브트리 높이 2.
3-2 = 1 - 70 : 왼쪽 서브트 리 높이 0 오른쪽 서브트리 높이 1.
0 - 1 = -1
- 10 : 왼쪽 서브트리 높이 1, 오른쪽 서브트리 높이 1 .
회전(Rotation)
AVL 트리는 균형이 무너지면(BF(K)값이 0, -1, 1 이 아니면 ) 회전을 하여 균형을 맞춘다.
이때 사용하는것이 회전이다.
검색 및 순회 연산은 BF를 변경하지 않지만 삽입 및 삭제 연산에서는 BF가 변경될 수 있다.
불균형 노드를 기준으로 서브트리의 위치를 변경하는 작업이 Rotation이다
삽입 삭제 시 노드들의 배열에 따라 4가지 (LL, LR, RR, RL) 불균형이 발생할 수 있으며,
각 상황마다 회전하는 방향이 다르다
- 좌회전과 우회전을 먼저 봅시다.
좌회전
- 균형이 깨진 노드 z
- z노드를 오른쪽 자식노드의 왼쪽으로 이동 -
- z 노드의 오른쪽 자식노드 y가 새 부모 노드가 됨.
우회전
- 균형이 깨진 노드 z
- z노드를 z의 왼쪽 자식노드인 y노드의 오른쪽 자식으로 이동
- z노드의 왼쪽 자식노드인 y가 새 부모 노드가 됨.
LL, RR ,LR , RR 을 보기전에 다시한번 기억해둬야 하는 내용
BF가
1이면 왼쪽 서브트리가 오른쪽 서브트리보다 높이가 한 단계 높은것.
BF가0이면 왼쪽 서브트리와 오른쪽 서브트리의 높이가 같은것.
BF가-1이면 왼쪽 서브트리가 오른쪽 서브트리보다 높이가 한 단계 낮은것.
- 즉 BF값이 범위를 벗어났을 떄 양수이면 왼쪽 서브트리가 더 높이가 높은것
- 음수이면 오른쪽 서브트리가 더 높이가 높은것
- ex ) -2, -3 이면 음수이므로 오른쪽 서브트리의 높이가 더높은것
- ex) 2, 3 이면 양수이므로 왼쪽 서브트리의 높이가 더 높은것
LL 회전 (Left Left) -> 우회전한다.
- BF값이 양수로 범위를 벗어난 경우 (2)
- 왼쪽 서브트리의 높이가 오른쪽 서브트리의 높이보다 더 높은경우
- BF값을 벗어난 노드를 z,
- z의 아들을 y
- y의 아들을 x (x는 z의 손자)
LL 회전은 y가 왼쪽 자식노드이고, x가 왼쪽 자식노드일 경우 회전한다
Right Rotation (우회전)
- 해당 노드인 z를 기준으로 우회전 하면 불균형이 해소된다.
- y노드의 오른쪽 자식 노드를 z로 변경
- z노드 왼쪽 자식 노드를 y 노드의 오른쪽 서브트리로 변경
- y가 새로운 루트 노드
RR 회전(Right Right) -> 좌회전한다
- BF값이 음수로 범위를 벗어난 경우( -2)
- 오른쪽 서브트리의 높이가 왼쪽 서브트리의 높이보다 더 높은 경우
- BF 값을 벗어난 노드를 z
- z의 아들을 y
- y의 아들을 x (x는 z의 손자)
RR 회전은 y가 z의 오른쪽 자식이고, x가 오른쪽 자식 노드일경우 회전한다
- Left Rotation(좌회전)
- 해당 노드인 z를 기준으로 좌회전하면 불균형이 해소된다
- y노드의 왼쪽 자식 노드를 z 노드로 변경
- z노드 오른쪽 자식 노드를 y노드 왼쪽 서브트리로 변경
- y가 새로운 루트노드
LR (Left Right) - 2번의 Rotation. left -> right 순으로 두번 수행한다
- BF 값이 양수로 범위를 벗어남
- BF의 왼쪽 자식노드가 오른쪽 자식 노드를 갖고 있는 경우
- BF 값을 벗어난 노드를 z
- z의 아들을 y
- y의 아들을 x (x는 z의 손자)
LR 회전은 y가 z의 왼쪽 자식이고 x가 y의 오른쪽 자식 노드일경우 left -> right 순으로 2번 회전한다
- 왼쪽 자식 노드인 y를 기준으로 좌회전
- 본인인 z 기준으로 우회전
y = z.left;
y = rotateLeft(y);
z = rotateRight(z);RL(RIght Left )- 2번의 Rotation. right left 순으로 두번 수행한다
- BF 값이 음수로 범위를 벗어남
- BF의 오른쪽 자식 노드가 왼쪽 자식 노드를 갖고 있는 경우
- BF 값을 벗어난 노드를 z
- z의 아들을 y
- y의 아들을 x (x는 z의 손자)
RL 회전은 y가 z의 오른쪽 자식이고 x가 의 왼쪽 자식일떄 right -> left 순으로 두번 회전한다.
- 오른쪽 자식 노드인 y를 기준으로 우회전
- 본인인 z 기준으로 좌회전
y = z.right;
y = rotateRight(y);
z = rotateLeft(z);자바 소스코드 구현 - 접기/펼치기
@Getter @Setter
@NoArgsConstructor @AllArgsConstructor
public class Node {
private int key;
private int height;
private Node left;
private Node right;
public Node(int key) {
this.key = key;
}
}
package tree;
/**
* @author : ysk
*/
public class AVLTree {
private Node root;
private void updateHeight(Node n) {
n.setHeight(1 + Math.max(height(n.getLeft()), height(n.getRight())));
}
private int height(Node n) {
return n == null ? -1 : n.getHeight();
}
private int getBalanceFactor(Node n) {
return n == null ? 0 : height(n.getRight()) - height(n.getLeft());
}
private Node rotateLeft(Node z) { // z 본인, 할아버지. y 본인의 오른쪽노드. x 손주 y의 왼쪽 노드
Node y = z.getRight();
Node x = y.getLeft();
// y의 왼쪽 자식 노드를 z로 지정
y.setLeft(z);
// z의 오른쪽 자식 노드를 x로 지정
z.setRight(x);
updateHeight(z);
updateHeight(y);
return y; // 새로운 루트 노드 반환
}
private Node rotateRight(Node z) { // z 본인, 할아버지. y 본인의 왼쪽노드 . x 손주 y의 왼쪽 노드
Node y = z.getLeft();
Node x = y.getRight();
y.setRight(z);
z.setLeft(x);
updateHeight(z);
updateHeight(y);
return y; // 새로운 루트노드
}
private Node insert(int key) {
Node newNode = new Node(key);
if (root == null) {
root = newNode;
return newNode;
}
Node rootNode = root;
while (true) {
if (key < rootNode.getKey()) {
if (rootNode.getLeft() != null) {
rootNode = rootNode.getLeft();
} else {
rootNode.setLeft(newNode);
return newNode;
}
} else if(key > rootNode.getKey()) {
if (rootNode.getRight() != null) {
rootNode = rootNode.getRight();
} else {
rootNode.setRight(newNode);
return newNode;
}
} else {
throw new IllegalArgumentException("has Contain, value : " + key);
}
}
}
public void insertNode(Integer... values) {
for (Integer value : values) {
insertNode(value);
}
}
public Node insertNode(int key) {
Node insertNode = insert(key);
updateHeight(insertNode);
return rebalance(insertNode);
}
private Node rebalance(Node node) {
int balanceFactor = this.getBalanceFactor(node);
if (balanceFactor < -1) { // RR : 현재 노드 기준으로 오른쪽 서브트리가 더 커서 발란스가 작아진경우
if (getBalanceFactor(node.getLeft()) <= 0) {
node = rotateRight(node);
} else { // LR
node.setLeft(rotateLeft(node.getLeft()));
node = rotateRight(node);
}
}
if (balanceFactor > 1) { // LL
if (getBalanceFactor(node.getRight()) > 0) { // LL
node = rotateLeft(node);
} else { // RL
node.setRight(rotateRight(node.getRight()));
node = rotateLeft(node);
}
}
return node;
}
public Node searchNode(int key) {
Node node = root;
while(node != null) {
if (key == node.getKey()) {
return node;
} else if (key < node.getKey()) {
node = node.getLeft();
} else {
node = node.getRight();
}
}
return null;
}
public Node getRoot() {
return this.root;
}
public void inOrder(Node node) {
if (node != null) {
if (node.getLeft() != null) {
inOrder(node.getLeft());
}
System.out.print(node.getKey() + ", ");
if (node.getRight() != null) {
inOrder(node.getRight());
}
}
}
public static void main(String[] args) {
AVLTree avlTree = new AVLTree();
avlTree.insertNode(3, 5, 4, 7, 9, 11, 15, 14, 10, 2, 99, 98, 94, 90, 18, 19, 23, 25, 53, 70, 88, 46, 64, 72);
Node root = avlTree.getRoot();
avlTree.inOrder(root);
}
}참고
https://yoongrammer.tistory.com/72
https://galid1.tistory.com/176
https://www.happycoders.eu/algorithms/avl-tree-java/
https://www.baeldung.com/java-avl-trees
https://www.zerocho.com/category/Algorithm/post/583cacb648a7340018ac73f1