Java-자료구조 5주차 Tree 5 - 1 ~ 4

5주차. AVL Tree & Red Black Tree
5-1. AVL 트리 소개

• AVL 트리
  스스로 균형을 잡는 이진 탐색 트리로, 모든 루트에서 left와 right의 높이 차이가 항상 1 or 0
  
• left와 right의 차이가 2 이상이면 균형이 깨졌다고 판단하여 좌측/우측 회전을 실시

+) 균형 인수
left와 right의 균형을 알아볼 때 균형 인수(left의 높이-right의 높이)를 기준으로 판단

위 트리는 균형 인수가 {-1, 0, +1} 이외의 값을 가지므로 균형이 깨져 한 방향으로 치우친 비AVL 트리가 되는 것이다

• 균형 인수가
  +이면 왼쪽 서브 트리에 문제가 있는 것이고,
  -이면 오른쪽 서브 트리에 문제가 있는 것이다

ex1) 좌측 회전 실시

ex2) 심화 버전

:균형이 깨진 노드를 발견하면 노드의 조부모-부모-자식 노드 간의 모양을 확인하고서
좌측/우측 회전인 모양인 경우, 조부모 노드를 회전시키고
좌측-우측/우측-좌측 회전인 모양인 경우, 부모 노드를 회전시킨다
:임시포인터를 사용할 때, 임시포인터는 원래 parent를 대신한다

5-2. 노드

• AVL 트리를 위한 노드 제작
  left, right에 AVL를 위해 parent라는 포인터까지 총 3개의 포인터를 사용
  <코드>

class Node<T>{ // 내부 클래스
	// T: Java 내에서 겹치지 않기 위해 재네릭 사용
	T data;
	Node<T> left;
	Node<T> right;
	Node<T> parent;
	// 생성자
	public Node(T obj){
		data = obj;
		parent = null;
        left = null;
        right = null;
}

포인터를 통해 left, right, parent로 이동한다
생성할 때 left, right, parent는 초기화된 상태로 생성되어 필요할 때 추가하는 방식(처음에는 모두 null을 가리킨다)

• 포인터가 null을 가리키면 아무데도 향하지 않는 걸 의미!

5-3. add 메소드

• AVL 트리의 클래스 생성자-add
  클래스 생성 후,
  -root == null: 노드 추가
  -root != null: add 메소드 재귀로 호출
  <코드>

// AVL 클래스의 생성자
public AVLTree(){
	root = null;
	currentSize = 0;
}

// add 메소드
public void add(E obj){
	Node<E> node = new Node<E>(obj); // E타입의 obj가 있는 노드를 새로 형성
    
	// 트리가 비어있을 경우
	if (root == null){
		root = node; // 노드 추가
		currentSize++;
		return;
	}
	// 트리에 노드가 있을 경우 add 메소드를 재귀로 호출
	add(root, node); // 오버 로딩된 재귀 add 메소드
}

add 메소드를 재귀 호출하여 노드의 left나 right로 향하며 알맞는 위치에 추가한다

5-4. 재귀 add 메소드

• 이제 root != null일 때, 재귀로 호출되는 add 메소드 생성!
  -'add(현재 위치한 노드, 새롭게 추가할 노드)'를 입력하여 실행
  <코드>

public void add(Node<E> parent, Node<E> new Node){
	// newNode의 data와 parent의 data를 비교하여 left, right 결정
	if (((Comparable<E>)newNode.data.compareTo(parent.data)>0{ newNode > parent
		if (parent.right == null){
			parent.right = newNode;
			newNode.parent = parent;
			currentSize++;
		}
		else
			add(parent.right, newNode);
	else{ newNode < parent
		if (parent.left == null){
			parent.left = newNode;
			newNode.parent = parent; 
			currentSize++;
		}
		else
			add(parent.left, newNode);
    
	// AVL트리가 규칙에 맞게 잘 되어있는지 확인
	checkBalance(newNode);
}

+) 오버로딩: 메소드 명은 같지만, 매개변수 타입이 달라 서로 다른 취급을 하는 메소드. 자바는 매개변수가 다르면 메소드 명이 같아도 다른 취급을 한다