[자료구조/JAVA] 트리 (3) : AVL 균형 트리 (AVL Tree)
2024. 3. 25. 21:36
반응형
AVL 트리
AVL 트리는 이진 탐색 트리(BST)의 한 종류로, 연산 수행 시 최악의 경우에도 시간 복잡도를 O(log n)으로 유지하기 위해 고안되었다. 이진 탐색 트리의 단점 중 하나는 트리가 한 쪽으로 치우쳐져 편향되는 현상이 발생할 수 있다는 것이 있다.
기존 이진 탐색 트리에서 트리가 최악으로 편향될 경우, 연산의 시간 복잡도가 O(N)으로 악화될 수 있다. AVL 트리는 이러한 문제를 해결하는 데에 초점을 맞추었다.
해당 트리는 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1을 유지하도록 한다. 따라서 트리가 편향되는 것을 방지하고, 모든 연산의 시간 복잡도를 O(log N)으로 유지할 수 있다.
이를 위해 아래 애니메이션처럼 삽입 및 삭제 시 트리의 균형을 조절하는 알고리즘을 사용하게 된다.
만약 Node가 100 -> 200 -> 300 -> 400 -> 500의 순서로 삽입된다고 가정한다면 이진 탐색 트리의 경우 삽입의 순서에 따라 노드가 들어가게 되므로 다음과 같이 편향된 형태의 트리가 생겨나게 될 것이다.
100
\
200
\
300
\
400
\
500
(이진 탐색 트리)
반면 AVL 트리는 삽입 및 삭제 시 트리의 높이의 편향성을 고려하여 노드들을 재배치하므로 다음과 같은 형태의 트리가 만들어지게 된다.
300
/ \
200 400
/ / \
100 500
(AVL 트리)
높이가 h인 AVL트리를 구성하는 최소 노드 수 A(h) : A(h-1) + A(h-2)
- 단 A(0) = 0, A(1) = 1, A(2) = 2
트리의 회전연산 : 기본 연산
AVL 트리는 삭제 시 트리의 균형을 체크하고, 균형이 깨졌을 때 이를 회전연산을 통해서 균형을 유지하는 알고리즘을 사용된다.
트리의 회전 연산 내부에서 사용될 기본 연산으로는 두가지의 연산이 있다.
트리의 어느 노드를 기준으로 오른쪽으로 회전과 왼쪽으로 회전시키는 연산이다.
Rotate Left : 왼쪽 회전 연산
오른쪽 방향의 서브트리가 높아서 불균형이 발생했을 때, 왼쪽 방향으로 회전하기 위한 연산
- 노드 N(17)의 오른쪽 자식노드 X(50)를 노드 N의 자리로 옮긴다.
- 노드 N(17)을 노드 X(50)의 왼쪽 자식노드로 만든다.
- 기존의 노드 X(50)의 왼쪽 서브트리가 노드 N의 오른쪽 서브트리로 이동한다.
Rotate Right : 오른쪽 회전 연산
왼쪽 방향의 서브트리가 높아서 불균형이 발생했을 때, 오른쪽 방향으로 회전하기 위한 연산
- 노드 N(50)의 왼쪽 자식노드 X(17)를 노드 N의 자리로 옮긴다.
- 노드 N(50)을 노드 X(17)의 오른쪽 자식노드로 만든다.
- 기존의 노드 X(17)의 오른쪽 서브트리가 노드 N의 왼쪽 서브트리로 이동한다.
트리의 회전연산 : 회전 연산
트리의 회전 연산의 유형은 크게 네 가지로 분류된다.
XX-회전이라고 표현하지만, 설명에서 사용되는 회전 개념과 혼동될 수 있으므로 XX-유형이라고 표현하도록 하겠다.
- ex) LL-회전은 이름과 달리 오른쪽 회전 연산을 사용한다.
1. LL-회전 : t.left.left가 가장 깊음 : Rotate Right 연산
2. RR-회전 : t.right.right가 가장 깊음 : Rotate Left 연산
3. LR-회전 : t.left.right가 가장 깊음 : Rotate Left -> Rotate Right 연산
4. RL 회전 : t.right.left가 가장 깊음 : Rotate Right -> Rotate Left 연산
1. LL-회전 : t.left.left가 가장 깊음 : Rotate Right 연산
2. RR-회전 : t.right.right가 가장 깊음 : Rotate Left 연산
3. LR-회전 : t.left.right가 가장 깊음 : Rotate Left -> Rotate Right 연산
4. RL 회전 : t.right.left가 가장 깊음 : Rotate Right -> Rotate Left 연산
AVL 트리 구현
아래는 우선 앞선 포스팅에서 작성했던 Binary Search Tree를 구현한 것이다. 우리는 해당 BST를 AVL 트리로 바꾸는 과정을 살펴보려고 한다.
class AVLNode<Key extends Comparable<Key>, Value> {
Key key;
Value value;
AVLNode<Key, Value> left;
AVLNode<Key, Value> right;
public AVLNode(Key key, Value value){
this.key = key;
this.value = value;
this.left = this.right = null;
}
public Key getKey() {
return key;
}
public void setKey(Key key) {
this.key = key;
}
public Value getValue() {
return value;
}
public void setValue(Value value) {
this.value = value;
}
public AVLNode<Key, Value> getLeft() {
return left;
}
public void setLeft(AVLNode<Key, Value> left) {
this.left = left;
}
public AVLNode<Key, Value> getRight() {
return right;
}
public void setRight(AVLNode<Key, Value> right) {
this.right = right;
}
}
class AVLTree<Key extends Comparable<Key>, Value>{
AVLNode<Key, Value> root;
// 전위 순회
public void preorder(){
this.preorder(this.root);
}
private void preorder(AVLNode<Key, Value> n){
if(n != null){
System.out.print(n.key + " ");
preorder(n.left);
preorder(n.right);
}
}
// 중위 순회
public void inorder(){
this.inorder(this.root);
}
private void inorder(AVLNode<Key, Value> n){
if(n != null){
inorder(n.left);
System.out.print(n.key + " ");
inorder(n.right);
}
}
// 후위 순회
public void postorder(){
this.postorder(this.root);
}
private void postorder(AVLNode<Key, Value> n){
if(n != null){
postorder(n.left);
postorder(n.right);
System.out.print(n.key + " ");
}
}
// 레벨 순회
public void levelorder(){
this.levelorder(this.root);
}
private void levelorder(AVLNode<Key, Value> n){
Queue queue = new LinkedList<AVLNode<Key, Value>>();
queue.add(n);
while(!queue.isEmpty()){
AVLNode<Key, Value> current = (AVLNode<Key, Value>) queue.poll();
System.out.print(current.key + " ");
if(current.left != null){
queue.add(current.left);
}
if(current.right != null){
queue.add(current.right);
}
}
}
public int getHeight(){
return this.getHeight(this.root);
}
private int getHeight(AVLNode<Key, Value> n){
if(n == null){
return 0;
}
else{
return 1 + Math.max(getHeight(n.left), getHeight(n.right));
}
}
public int getSize(){
return this.getSize(this.root);
}
private int getSize(AVLNode<Key, Value> root){
if(root == null){
return 0;
}
else{
return 1 + getSize(root.left) + getSize(root.right);
}
}
public boolean isEqual(AVLTree<Key, Value> compare){
return this.isEqual(this.root, compare.root);
}
private boolean isEqual(AVLNode<Key, Value> n, AVLNode<Key, Value> m){
if(n == null || m == null){
return n == m; //둘 다 null일 경우 True, 아니면 False(XOR)
}
if (n.key.compareTo(m.key) != 0){
return false;
}
return isEqual(n.left, m.left) && isEqual(n.right, m.right);
}
public AVLNode search(Key k){
return search(k, this.root);
}
private AVLNode search(Key k, AVLNode n){
if(n == null){
return null;
}
int comp = n.getKey().compareTo(k);
if(comp == 0){
return n;
}
else if(comp > 0){ // 현재 노드보다 키값이 작은 경우
return search(k, n.getLeft());
}
else{
return search(k, n.getRight());
}
}
public void insert(Key k, Value v){
this.root = insert(k, v, root);
}
private AVLNode insert(Key k, Value v, AVLNode n){
if(n == null){
return new AVLNode(k, v);
}
int comp = n.getKey().compareTo(k);
if(comp == 0){ // 같은 키값의 노드 -> Value만 갱신(Key 중복 허용 X)
n.setValue(v);
return n;
}
else if(comp > 0){ // 현재 노드보다 키값이 작은 경우
n.setLeft(insert(k, v, n.getLeft()));
}
else{ // 현재 노드보다 키값이 큰 경우 -> 오른쪽 서브트리에 삽입
n.setRight(insert(k, v, n.getRight()));
}
return n;
}
public AVLNode getMin(){
if(this.root == null){
return null;
}
return getMin(this.root);
}
private AVLNode getMin(AVLNode n){
if(n.getLeft() == null){
return n; //Left 존재하지 않으면 최소값
}
return getMin(n.getLeft()); //최소값 나올때까지 left로 이동하며 재귀호출
}
public AVLNode getMax(){
if(this.root == null){
return null;
}
return getMax(this.root);
}
private AVLNode getMax(AVLNode n){
if(n.getRight() == null){
return n; //Right가 존재하지 않으면 최대값
}
return getMax(n.getRight()); //최대값 나올때까지 right로 이동하며 재귀호출
}
public void deleteMin(){
this.root = deleteMin(this.root);
}
private AVLNode deleteMin(AVLNode n){
if(n.getLeft() == null){
return n.getRight(); //Left 존재하지 않으면 최소값
}
n.setLeft(deleteMin(n.getLeft())); //최소값 나올 때 까지 Left로 이동
return n;
}
public void delete(Key k){
this.root = delete(k, this.root);
}
private AVLNode delete(Key k, AVLNode n){
if(n == null){
return null;
}
int comp = n.getKey().compareTo(k);
if(comp > 0){ // 현재 노드보다 키값이 작은 경우 -> 왼쪽 서브트리로 이동하며 delete() 재귀호출
n.setLeft(delete(k, n.getLeft()));
}
else if(comp < 0){ // 현재 노드보다 키값이 큰 경우 -> 오른쪽 서브트리로 이동하며 delete() 재귀호출
n.setRight(delete(k, n.getRight()));
}
else{ // 삭제할 노드 발견
if(n.getRight() == null){ //오른쪽 서브트리가 없는 경우 : 왼쪽 서브트리를 현재 노드의 위치로 연결
return n.getLeft();
}
else if(n.getLeft() == null){ //왼쪽 서브트리가 없는 경우 : 오른쪽 서브트리를 현재 노드의 위치로 연결
return n.getRight();
}
else{
AVLNode targetNode = n; // 삭제 대상 노드를 targetNode로 설정
n = getMin(targetNode.getRight()); // 대체 : 삭제 대상의 오른쪽 서브트리의 최소값 노드를 삭제 위치로 이동
n.setRight(deleteMin(targetNode.getRight())); // 대체 노드의 right : 삭제 대상의 right 서브트리로 설정 + 이동된 노드는 제거
n.setLeft(targetNode.getLeft()); // 대체 노드의 left : 삭제 대상의 left 서브트리로 설정
}
}
return n;
}
}
AVL 트리가 기존 Binary Search Tree(BST)에서 달라지는 점은 아래의 사항과 같다.
1. Node에 높이(height) 추가 : 균형을 판단하기 위해서
2. 불균형 감지와 회전 연산 구현
3. 삽입과 삭제 시 트리의 불균형 판단 및 회전 연산
이 외의 사항들은 Binary Search Tree와 동일하다. 만약 BST에 대해서 자세히 모른다면 아래의 포스팅을 먼저 보고 오는 것을 추천한다.
https://sjh9708.tistory.com/204
[자료구조/JAVA] 트리 (2) : 이진 탐색 트리(Binary Search Tree, BST)
이진 탐색 트리(Binary Search Tree, BST) 앞의 포스팅에서는 이진 트리에 대해서 알아 보았었다. 그런데 이진 트리는 정렬되지 않은 형태이므로 탐색을 수행하기 적절하지 않았다. 이를 위해서 이진
sjh9708.tistory.com
Node : 높이(height) 추가
class AVLNode<Key extends Comparable<Key>, Value> {
Key key;
Value value;
AVLNode<Key, Value> left;
AVLNode<Key, Value> right;
int height;
public AVLNode(Key key, Value value){
this.key = key;
this.value = value;
this.height = 1;
this.left = this.right = null;
}
public int getHeight() {
return height;
}
public void setHeight(int height) {
this.height = height;
}
// Getter & Setter
}
균형을 판단하기 위해서 각각의 노드들의 Height를 계산해야 할 필요성이 생겼다.
따라서 노드 필트에 Height를 추가해 주었다.
AVL 트리 : Height 관련 메서드 추가
class AVLTree<Key extends Comparable<Key>, Value>{
AVLNode<Key, Value> root;
// 전위 순회
// 중위 순회
// 레벨 순회
public int getHeight(){
return this.getHeight(this.root);
}
private int getHeight(AVLNode<Key, Value> n){
if(n == null){
return 0;
}
else{
return n.getHeight();
// return 1 + getSize(root.left) + getSize(root.right);
}
}
//getSize
//isEqual
//search
//insert
//getMin
//getMax
//deleteMin
//delete
//왼쪽 서브트리와 오른쪽 서브트리의 높이 차이 반환
private int bf(AVLNode n){
return getHeight(n.left) - getHeight(n.right);
}
}
이제 Node에 Height 속성이 추가되었으므로 기존의 getHeight() 로직을 변경해준다.
원래는 root에서 재귀 호출 알고리즘을 사용하여 해당 노드의 Height를 계산했는데 삽입할 때 Node의 Height를 함께 계산하여 필드에 넣을 것이므로 그럴 필요가 없어졌다.
그리고 해당 노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이를 계산하기 위해서 bf() 메서드를 추가해준다.
이를 기반으로 아래 두 가지 기능을 수행하려고 한다.
1. 트리의 불균형 판단
2. LL, LR, RR, RL 중 어느 회전 연산을 사용할 지 판단
AVL 트리 : 회전 기본 연산 작성
class AVLTree<Key extends Comparable<Key>, Value>{
//...
// 왼쪽으로 회전하는 함수
private AVLNode<Key, Value> rotateLeft(AVLNode<Key, Value> n) {
AVLNode<Key, Value> pivot = n.right; // 오른쪽 자식노드 X : 노드 N의 위치로 변경
n.right = pivot.left; // 노드 X의 왼쪽 서브트리 : 노드 N의 오른쪽 서브트리로 위치 변경
pivot.left = n; // 노드 N : 노드 X의 왼쪽 자식노드로 변경
// 높이 업데이트
n.height = Math.max(getHeight(n.left), getHeight(n.right)) + 1;
pivot.height = Math.max(getHeight(pivot.left), getHeight(pivot.right)) + 1;
return pivot;
}
// 오른쪽으로 회전하는 함수
private AVLNode<Key, Value> rotateRight(AVLNode<Key, Value> n) {
AVLNode<Key, Value> pivot = n.left; // 왼쪽 자식노드 X : 노드 N의 위치로 변경
n.left = pivot.right; // 노드 X의 오른쪽 서브트리 : 노드 N의 왼쪽 서브트리로 위치 변경
pivot.right = n; // 노드 N : 노드 X의 오른쪽 자식노드로 변경
// 높이 업데이트
n.height = Math.max(getHeight(n.left), getHeight(n.right)) + 1;
pivot.height = Math.max(getHeight(pivot.left), getHeight(pivot.right)) + 1;
return pivot;
}
}AVL 트리는 노드를 회전시켜 균형을 유지하는 데 사용된다고 하였고, 기본 연산으로는 Rotate Left, Rotate Right가 있다고 하였다.
해당 메서드들은 각각 노드를 왼쪽으로 회전하거나 오른쪽으로 회전시키는 것을 담당한다.
- rotateLeft: 해당 노드를 기준으로 오른쪽으로 노드를 회전. 노드의 오른쪽 서브트리가 더 높아진 경우에 균형을 맞춤
- rotateRight: 노드를 기준으로 왼쪽으로 노드를 회전. 왼쪽 서브트리가 더 높아진 경우에 균형을 맞춤
AVL 트리 : 회전 연산 작성
private AVLNode balance(AVLNode n){
//노드 N의 왼쪽 서브트리의 높이가 높음
if(bf(n) > 1){
//노드 N의 왼쪽 자식노드 -> 오른쪽 서브트리의 높이가 높음
if(bf(n.left) < 0){
n.left = rotateLeft(n.left); //LR유형(Left-Right Rotate)
}
n = rotateRight(n); //LL유형(Right Rotate) / LR유형(Left-Right Rotate)
}
//노드 N의 오른쪽 서브트리의 높이가 높음
else if(bf(n) < -1){
//노드 N의 오른쪽 자식노드 -> 왼쪽 서브트리의 높이가 높음
if(bf(n.right) > 0){
n.right = rotateRight(n.right); //RL유형(Right-Left Rotate)
}
n = rotateLeft(n); //RR유형(Left Rotate) / RL유형(Right-Left Rotate)
}
return n;
}
회전 연산의 케이스는 아래와 같았다.
1. LL-회전 : t.left.left가 가장 깊음 : Rotate Right 연산
2. RR-회전 : t.right.right가 가장 깊음 : Rotate Left 연산
3. LR-회전 : t.left.right가 가장 깊음 : Rotate Left -> Rotate Right 연산
4. RL 회전 : t.right.left가 가장 깊음 : Rotate Right -> Rotate Left 연산
이에 맞추어 4가지 케이스의 나누어 회전 연산을 수행하므로서 균형을 맞추는 메서드를 추가해주었다.
AVL 트리 : 삽입 / 삭제 연산 수정
private AVLNode insert(Key k, Value v, AVLNode n){
if(n == null){
return new AVLNode(k, v);
}
int comp = n.getKey().compareTo(k);
if(comp == 0){ // 같은 키값의 노드 -> Value만 갱신(Key 중복 허용 X)
n.setValue(v);
return n;
}
else if(comp > 0){ // 현재 노드보다 키값이 작은 경우
n.setLeft(insert(k, v, n.getLeft()));
}
else{ // 현재 노드보다 키값이 큰 경우 -> 오른쪽 서브트리에 삽입
n.setRight(insert(k, v, n.getRight()));
}
// AVL 트리 : 불균형 판단 및 균형을 위해 회전연산
n.height = Math.max(getHeight(n.left), getHeight(n.right)) + 1;
return balance(n);
}
이제 삽입 시에 두 가지의 행동을 추가적으로 한다.
1. Node를 추가할 때 Height를 계산한다.
2. insert() 메서드는 재귀적으로 호출되었었다. 따라서 삽입된 위치로부터 Root 노드까지 올라오면서 balance(n)에 의해서 트리의 균형을 판단하고, 해당 노드의 서브트리들의 균형이 깨졌다면 재배치하게 된다.
public void deleteMin(){
this.root = deleteMin(this.root);
}
private AVLNode deleteMin(AVLNode n){
if(n.getLeft() == null){
return n.getRight(); //Left 존재하지 않으면 최소값
}
n.setLeft(deleteMin(n.getLeft())); //최소값 나올 때 까지 Left로 이동
// AVL 트리 : 불균형 판단 및 균형을 위해 회전연산
n.height = Math.max(getHeight(n.left), getHeight(n.right)) + 1;
return balance(n);
}
public void delete(Key k){
this.root = delete(k, this.root);
}
private AVLNode delete(Key k, AVLNode n){
if(n == null){
return null;
}
int comp = n.getKey().compareTo(k);
if(comp > 0){ // 현재 노드보다 키값이 작은 경우 -> 왼쪽 서브트리로 이동하며 delete() 재귀호출
n.setLeft(delete(k, n.getLeft()));
}
else if(comp < 0){ // 현재 노드보다 키값이 큰 경우 -> 오른쪽 서브트리로 이동하며 delete() 재귀호출
n.setRight(delete(k, n.getRight()));
}
else{ // 삭제할 노드 발견
if(n.getRight() == null){ //오른쪽 서브트리가 없는 경우 : 왼쪽 서브트리를 현재 노드의 위치로 연결
return n.getLeft();
}
else if(n.getLeft() == null){ //왼쪽 서브트리가 없는 경우 : 오른쪽 서브트리를 현재 노드의 위치로 연결
return n.getRight();
}
else{
AVLNode targetNode = n; // 삭제 대상 노드를 targetNode로 설정
n = getMin(targetNode.getRight()); // 대체 : 삭제 대상의 오른쪽 서브트리의 최소값 노드를 삭제 위치로 이동
n.setRight(deleteMin(targetNode.getRight())); // 대체 노드의 right : 삭제 대상의 right 서브트리로 설정 + 이동된 노드는 제거
n.setLeft(targetNode.getLeft()); // 대체 노드의 left : 삭제 대상의 left 서브트리로 설정
}
}
// AVL 트리 : 불균형 판단 및 균형을 위해 회전연산
n.height = Math.max(getHeight(n.left), getHeight(n.right)) + 1;
return balance(n);
}
삭제 시에도 마찬가지이다.
1. Node를 삭제된 이후의 Height를 계산하여 갱신한다.
2. delete() 메서드 및, deleteMin() 메서드 또한 트리의 불균형을 판단하고 균형이 깨졌다면 회전연산을 수행하도록 알고리즘을 추가해주어야 한다. 이에 따라서 마찬가지로 balance(n)을 통해 이를 수행한다.
전체 코드
class AVLNode<Key extends Comparable<Key>, Value> {
Key key;
Value value;
AVLNode<Key, Value> left;
AVLNode<Key, Value> right;
int height;
public AVLNode(Key key, Value value){
this.key = key;
this.value = value;
this.height = 1;
this.left = this.right = null;
}
public int getHeight() {
return height;
}
public void setHeight(int height) {
this.height = height;
}
public Key getKey() {
return key;
}
public void setKey(Key key) {
this.key = key;
}
public Value getValue() {
return value;
}
public void setValue(Value value) {
this.value = value;
}
public AVLNode<Key, Value> getLeft() {
return left;
}
public void setLeft(AVLNode<Key, Value> left) {
this.left = left;
}
public AVLNode<Key, Value> getRight() {
return right;
}
public void setRight(AVLNode<Key, Value> right) {
this.right = right;
}
}
class AVLTree<Key extends Comparable<Key>, Value>{
AVLNode<Key, Value> root;
// 전위 순회
public void preorder(){
this.preorder(this.root);
}
private void preorder(AVLNode<Key, Value> n){
if(n != null){
System.out.print(n.key + " ");
preorder(n.left);
preorder(n.right);
}
}
// 중위 순회
public void inorder(){
this.inorder(this.root);
}
private void inorder(AVLNode<Key, Value> n){
if(n != null){
inorder(n.left);
System.out.print(n.key + " ");
inorder(n.right);
}
}
// 후위 순회
public void postorder(){
this.postorder(this.root);
}
private void postorder(AVLNode<Key, Value> n){
if(n != null){
postorder(n.left);
postorder(n.right);
System.out.print(n.key + " ");
}
}
// 레벨 순회
public void levelorder(){
this.levelorder(this.root);
}
private void levelorder(AVLNode<Key, Value> n){
Queue queue = new LinkedList<AVLNode<Key, Value>>();
queue.add(n);
while(!queue.isEmpty()){
AVLNode<Key, Value> current = (AVLNode<Key, Value>) queue.poll();
System.out.print(current.key + " ");
if(current.left != null){
queue.add(current.left);
}
if(current.right != null){
queue.add(current.right);
}
}
}
public int getHeight(){
return this.getHeight(this.root);
}
private int getHeight(AVLNode<Key, Value> n){
if(n == null){
return 0;
}
else{
return n.getHeight();
}
}
public int getSize(){
return this.getSize(this.root);
}
private int getSize(AVLNode<Key, Value> root){
if(root == null){
return 0;
}
else{
return 1 + getSize(root.left) + getSize(root.right);
}
}
public boolean isEqual(AVLTree<Key, Value> compare){
return this.isEqual(this.root, compare.root);
}
private boolean isEqual(AVLNode<Key, Value> n, AVLNode<Key, Value> m){
if(n == null || m == null){
return n == m; //둘 다 null일 경우 True, 아니면 False(XOR)
}
if (n.key.compareTo(m.key) != 0){
return false;
}
return isEqual(n.left, m.left) && isEqual(n.right, m.right);
}
public AVLNode search(Key k){
return search(k, this.root);
}
private AVLNode search(Key k, AVLNode n){
if(n == null){
return null;
}
int comp = n.getKey().compareTo(k);
if(comp == 0){
return n;
}
else if(comp > 0){ // 현재 노드보다 키값이 작은 경우
return search(k, n.getLeft());
}
else{
return search(k, n.getRight());
}
}
public void insert(Key k, Value v){
this.root = insert(k, v, root);
}
private AVLNode insert(Key k, Value v, AVLNode n){
if(n == null){
return new AVLNode(k, v);
}
int comp = n.getKey().compareTo(k);
if(comp == 0){ // 같은 키값의 노드 -> Value만 갱신(Key 중복 허용 X)
n.setValue(v);
return n;
}
else if(comp > 0){ // 현재 노드보다 키값이 작은 경우
n.setLeft(insert(k, v, n.getLeft()));
}
else{ // 현재 노드보다 키값이 큰 경우 -> 오른쪽 서브트리에 삽입
n.setRight(insert(k, v, n.getRight()));
}
n.height = Math.max(getHeight(n.left), getHeight(n.right)) + 1;
return balance(n);
}
public AVLNode getMin(){
if(this.root == null){
return null;
}
return getMin(this.root);
}
private AVLNode getMin(AVLNode n){
if(n.getLeft() == null){
return n; //Left 존재하지 않으면 최소값
}
return getMin(n.getLeft()); //최소값 나올때까지 left로 이동하며 재귀호출
}
public AVLNode getMax(){
if(this.root == null){
return null;
}
return getMax(this.root);
}
private AVLNode getMax(AVLNode n){
if(n.getRight() == null){
return n; //Right가 존재하지 않으면 최대값
}
return getMax(n.getRight()); //최대값 나올때까지 right로 이동하며 재귀호출
}
public void deleteMin(){
this.root = deleteMin(this.root);
}
private AVLNode deleteMin(AVLNode n){
if(n.getLeft() == null){
return n.getRight(); //Left 존재하지 않으면 최소값
}
n.setLeft(deleteMin(n.getLeft())); //최소값 나올 때 까지 Left로 이동
n.height = Math.max(getHeight(n.left), getHeight(n.right)) + 1;
return balance(n);
}
public void delete(Key k){
this.root = delete(k, this.root);
}
private AVLNode delete(Key k, AVLNode n){
if(n == null){
return null;
}
int comp = n.getKey().compareTo(k);
if(comp > 0){ // 현재 노드보다 키값이 작은 경우 -> 왼쪽 서브트리로 이동하며 delete() 재귀호출
n.setLeft(delete(k, n.getLeft()));
}
else if(comp < 0){ // 현재 노드보다 키값이 큰 경우 -> 오른쪽 서브트리로 이동하며 delete() 재귀호출
n.setRight(delete(k, n.getRight()));
}
else{ // 삭제할 노드 발견
if(n.getRight() == null){ //오른쪽 서브트리가 없는 경우 : 왼쪽 서브트리를 현재 노드의 위치로 연결
return n.getLeft();
}
else if(n.getLeft() == null){ //왼쪽 서브트리가 없는 경우 : 오른쪽 서브트리를 현재 노드의 위치로 연결
return n.getRight();
}
else{
AVLNode targetNode = n; // 삭제 대상 노드를 targetNode로 설정
n = getMin(targetNode.getRight()); // 대체 : 삭제 대상의 오른쪽 서브트리의 최소값 노드를 삭제 위치로 이동
n.setRight(deleteMin(targetNode.getRight())); // 대체 노드의 right : 삭제 대상의 right 서브트리로 설정 + 이동된 노드는 제거
n.setLeft(targetNode.getLeft()); // 대체 노드의 left : 삭제 대상의 left 서브트리로 설정
}
}
n.height = Math.max(getHeight(n.left), getHeight(n.right)) + 1;
return balance(n);
}
//왼쪽 서브트리와 오른쪽 서브트리의 높이 차이 반환
private int bf(AVLNode n){
return getHeight(n.left) - getHeight(n.right);
}
private AVLNode balance(AVLNode n){
//노드 N의 왼쪽 서브트리의 높이가 높음
if(bf(n) > 1){
//노드 N의 왼쪽 자식노드 -> 오른쪽 서브트리의 높이가 높음
if(bf(n.left) < 0){
n.left = rotateLeft(n.left); //LR유형(Left-Right Rotate)
}
n = rotateRight(n); //LL유형(Right Rotate) / LR유형(Left-Right Rotate)
}
//노드 N의 오른쪽 서브트리의 높이가 높음
else if(bf(n) < -1){
//노드 N의 오른쪽 자식노드 -> 왼쪽 서브트리의 높이가 높음
if(bf(n.right) > 0){
n.right = rotateRight(n.right); //RL유형(Right-Left Rotate)
}
n = rotateLeft(n); //RR유형(Left Rotate) / RL유형(Right-Left Rotate)
}
return n;
}
// 왼쪽으로 회전하는 함수
private AVLNode<Key, Value> rotateLeft(AVLNode<Key, Value> n) {
AVLNode<Key, Value> pivot = n.right; // 오른쪽 자식노드 X : 노드 N의 위치로 변경
n.right = pivot.left; // 노드 X의 왼쪽 서브트리 : 노드 N의 오른쪽 서브트리로 위치 변경
pivot.left = n; // 노드 N : 노드 X의 왼쪽 자식노드로 변경
// 높이 업데이트
n.height = Math.max(getHeight(n.left), getHeight(n.right)) + 1;
pivot.height = Math.max(getHeight(pivot.left), getHeight(pivot.right)) + 1;
return pivot;
}
// 오른쪽으로 회전하는 함수
private AVLNode<Key, Value> rotateRight(AVLNode<Key, Value> n) {
AVLNode<Key, Value> pivot = n.left; // 왼쪽 자식노드 X : 노드 N의 위치로 변경
n.left = pivot.right; // 노드 X의 오른쪽 서브트리 : 노드 N의 왼쪽 서브트리로 위치 변경
pivot.right = n; // 노드 N : 노드 X의 오른쪽 자식노드로 변경
// 높이 업데이트
n.height = Math.max(getHeight(n.left), getHeight(n.right)) + 1;
pivot.height = Math.max(getHeight(pivot.left), getHeight(pivot.right)) + 1;
return pivot;
}
}
public class C03_AVLTree {
static AVLTree makeAVLTree(Integer lastKey){
AVLTree<Integer, String> t = new AVLTree<>();
t.insert(100, "Apple");
t.insert(200, "Banana");
t.insert(300, "Carrot");
t.insert(400, "Dog");
t.insert(500, "Elephant");
t.insert(600, "Frog");
t.insert(700, "Grape");
t.insert(lastKey, "Lemon");
return t;
}
public static void main(String[] args) {
AVLTree t = makeAVLTree(800);
System.out.print("Preorder : ");
t.preorder();
System.out.println();
System.out.print("Inorder : ");
t.inorder();
System.out.println();
System.out.print("Postorder : ");
t.postorder();
System.out.println();
System.out.print("Levelorder : ");
t.levelorder();
System.out.println();
System.out.println("Height : " + t.getHeight());
System.out.println("Size : " + t.getSize());
AVLTree t2 = makeAVLTree(800);
System.out.println("isEqual : " + t.isEqual(t2));
AVLTree t3 = makeAVLTree(700);
System.out.println("isEqual : " + t.isEqual(t3));
System.out.println("Search 300 : " + t.search(300).getValue());
System.out.println("Search 900 : " + t.search(900));
System.out.println("Search getMin : " + t.getMin().getKey());
System.out.println("Search getMax : " + t.getMax().getKey());
System.out.println("Delete 400");
t.delete(400);
System.out.print("Inorder : ");
t.inorder();
System.out.println();
System.out.print("Inorder : ");
t.inorder();
System.out.println();
System.out.println("Delete min");
t.deleteMin();
System.out.print("Inorder : ");
t.inorder();
System.out.println();
}
}
Preorder : 400 200 100 300 600 500 700 800
Inorder : 100 200 300 400 500 600 700 800
Postorder : 100 300 200 500 800 700 600 400
Levelorder : 400 200 600 100 300 500 700 800
Height : 4
Size : 8
isEqual : true
isEqual : false
Search 300 : Carrot
Search 900 : null
Search getMin : 100
Search getMax : 800
Delete 400
Inorder : 100 200 300 500 600 700 800
Inorder : 100 200 300 500 600 700 800
Delete min
Inorder : 200 300 500 600 700 800
100부터 900의 순서대로 노드가 삽입되었을 때의 Level Order와 Height의 결과를 주목해보자.
그리고 Binary Search Tree의 Level Order와 Height와 Height과 함께 비교하자.
<AVL 트리의 결과>
Levelorder : 400 200 600 100 300 500 700 800
Height : 4
400
/ \
200 600
/ \ / \
100 300 500 700
\
800
<BST의 결과>
Levelorder : 100 200 300 400 500 600 700 800
Height : 8
100
\
200
\
300
\
400
\
500
\
600
\
700
\
800
BST는 완전히 편향된 이진 트리임을 확인할 수 있고 AVL 트리는 균형을 이루는 트리의 형태임을 확인할 수 있다.
시간 복잡도
탐색
BST: 최악의 경우, 트리의 높이에 비례하여 O(n)입니다. 하지만 평균적으로는 O(log n)입니다.
AVL 트리: 항상 균형을 유지하므로 최악의 경우에도 O(log n). BST보다 항상 효율적인 탐색을 제공한다..
삽입과 삭제
BST: 평균적으로는 O(log n), 최악의 경우(삽입 또는 삭제하려는 값이 트리의 가장 깊은 레벨에 위치하는 경우), 트리의 높이에 비례하여 O(n)
AVL 트리: 노드를 삽입 및 삭제한 후에도 균형을 유지하기 위해 회전 연산을 수행하기 때문에 시간 복잡도는 O(log n)으로 보장된다.
그렇지만 회전 연산 때문에 BST보다는 추가적인 연산이 필요하여 오버헤드가 발생한다.
따라서 AVL 트리는 데이터의 삽입과 삭제가 빈번하지 않고, 탐색 연산이 주로 발생하는 경우 사용하면 좋은 성능을 발휘할 수 있다.
반응형
'PS > 자료구조 & 알고리즘' 카테고리의 다른 글
| [자료구조/JAVA] 허프만 코딩 (Huffman Coding) (0) | 2024.03.31 |
|---|---|
| [자료구조/JAVA] 우선순위 큐 : 힙(Heap) (0) | 2024.03.28 |
| [자료구조/JAVA] 트리 (2) : 이진 탐색 트리(Binary Search Tree, BST) (0) | 2024.03.21 |
| [자료구조/JAVA] 트리 (1) : 이진 트리(Binary Tree) : 순회 및 연산 (0) | 2024.03.19 |
| [자료구조/JAVA] 연결 리스트(Linked List) (0) | 2024.03.13 |
