트리, 이진 탐색 트리, 레드-블랙 트리

1. 트리

  - 널리 이용되는 자료구조 중 하나

  - 나무의 "계층적" 구조를 표현한다.

 

  Def) 노트(node): 실제로 저장하는 데이터

  Def) 루트(root): 최상위에 위치한 데이터

  Def) 리프(leaf): 마지막에 위치한 데이터들 

 

  - 부모와 자식 관계(부모는 언제나 하나, 자식은 없거나 여러개 가능)

  - 높이: 어떤 노드->리프 경로의 최대 길이

    -> 부모 기준으로 아래 3개 있으면 높이가 3

  - 깊이: 어떤 노드->루트 경로의 길이

    -> 자식기준으로 위에 3개 있으면 깊이가 3

 

  - 하위 트리(subtree): 어떤 노드 아래의 모든 것을 포함하는 트리

 

2. 트리의 용도

  - 계층적 데이터를 표현

  - 검색트리를 통해 검색 알고리즘 구현 가능

  Ex) 트리의 저장법

public class Node{
	public int data;
	public ArrayList<Node> childeren;
}

 

 

3. 이진 탐색 트리 (BST, Binary Search Tree)

  - 보통 '트리'라고 부르기도 한다.

  - 부모보다 작으면 왼쪽 자식, 크면 오른쪽 자식

    -> "정렬된 트리" = 정렬된 자료구조

 

  Def) 중위 순회법(in-order travelsal)

  1) 왼쪽 하위 트리의 노드를 나열

  2) 내 노드를 나열

  3) 오른쪽 하위 트리의 노트 나열

 

 

4. BET 탐색

  - 정렬된 배열: 새로 추가된 데이터는 비정렬 상태, 간단한 구조

    -> 탐색시간: O(log n)

    -> 삽입 및 삭제: O(n)

 

  - 이진 탐색 트리(BST): 정렬 불필요, 데이터 추가 시 정렬된 위치에 추가, 복잡한 구조

    -> 탐색시간: O(log n)

    -> 삽입 및 삭제: O(log n)

 

  - 최악의 시간 복잡도: O(n)

   -> 자료 구조가 한쪽으로 쏠리는 경우

  Ex)

<hide/>
public static Node getNodeOrNull(Node node , int data) {
		if(node == null) {
			return null;
		}
		
		if(node.data == data) {
			return node;	
		}
		
		if(data < node.data) {
			return getNodeOrNull(node.left, data);
		}
        
		return getNodeOrNull(node.right, data);
}

 

5. BST 삽입

<hide/>
public class Node {
	
	private final int data;
	private Node left;
	private Node right;
	
	public Node(final int data) {		
		this.data = data;

	}
	public int getData() {
		return data;
	}
	
	public void setData(final int data) {
		this.data = data;
	}
	
	public Node getLeft() {
		return left;
	}
	
	public Node getRight() {
		return right;
	}

	public static Node insertRecursive(final Node node, int data ) {
		
		if(node == null) {
			
			return new Node(data);
		}
		if( data < node.data ) {
			
			node.left = insertRecursive(node.left, data);
		}
		else {
			node.right = insertRecursive( node.right, data);
		}
		
		return node;
	}
}

 

 

6. BST 삭제

  - 부모를 삭제하더라도 곧바로 자식을 연결하면 안 된다. 

  - 항상 리프부터 지워야 한다.

  - 삭제되는 값의 success를 먼저 찾는다.

    -> in-order successor: 오른쪽 하위트리에서 최솟값 (제일 왼쪽 리프)

    -> in-order predecessor: 왼쪽 하위 트리에서 최댓값 (제일 오른쪽 리프)

   - 삭제 전략

  1) 지울 값을 가지고 있는 노드를 찾는다.

  2) 그 바로 전 값을 가진 노드를 찾는다.

  3) 두 값을 교환

  4) 리프 노드를 삭제

 

  - BST 삭제 시간 복잡도

  1) 지울 값을 가지고 있는 노드를 찾고, 그 바로 전 값을 가진 노드를 찾는다. => O(log n)

  2) 두 값을 교환 => O(1)

  3) 리프 노드를 삭제 => O(1)

  결과: O(log n)

 

 

7. 중위 순회

  - 트리 순회(tree traversal)

 

  1) 중위(in-order) 순회

<hide/>
public static void traverseInOrder(Node node) {
		
		if(node == null) {
			return;
		}
		traverseInOrder(node.left);
		System.out.println(node.data);
		traverseInOrder(node.right);
		
}

 

  2) 전위 순회(preorder)

  - 루트노드부터 시작

  - 트리를 복사할 때 쓴다.

  - 뒤에서 부터 읽으면서 스택에 집어 넣는다.

<hide/>
	public static void traversePreorderRecursive(final Node node) {
		
		if(node == null) {
			return;
		}
		System.out.println(node.data);
		traversePreorderRecursive(node.left);
		traversePreorderRecursive(node.right);
		
}

 

  Ex) 재귀함수 이용하지 않는 전위 순회

<hide/>

public static void traversePreorder(final Node root ) {
		
	if( root == null ){
		return;
	}
		Stack<Node> nodes = new Stack<>();
		
		nodes.push(root);  
		
		while(!nodes.empty()) {
			Node node = nodes.pop();
			
			System.out.println(node.data);
			
			if(node.right != null) {
				nodes.push(node.right);	
			}
			if(node.left != null) {		// 왼쪽 자신을 먼저 방문해야하므로 스택에 가장 나중에 넣는다.
				nodes.push(node.left);	
			}
		}
}

<hide/>

public class Program {
	public static void main(String[] args) {
		Node root = new Node(50);
		
		Node.insertRecursive(root, 24);
		Node.insertRecursive(root, 42);
		Node.insertRecursive(root, 33);
		Node.insertRecursive(root, 22);
	
		Node.insertRecursive(root, 55);
		Node.insertRecursive(root, 52);
		Node.insertRecursive(root, 57);
		
		Node.traversePreorder(root);
	}
}

  Note) 실행 결과

 

 

  3) 후위 순회(post order)

  - 앞에서 부터 읽으면서 스택에 집어 넣는다.

  - 후위 표기법(postfix notation) = 역폴란드 표기법(reverse Polish notation)

 

  - 전위/ 중위/ 후위 순회 선택법

    -> 루트를 먼저 봐야한다면 => 전위 순회

    -> 리프를 다 본 다음에 다른 노드를 봐야하면 => 후위 순회

    -> 순서대로 봐야하면 => 중위 순회

 

<hide/>
package D220317;

public class Program {
	public static void main(String[] args) {
		
		Node root = new Node(50);
	
		Node.insertRecursive(root, 24);
		Node.insertRecursive(root, 42);
		Node.insertRecursive(root, 33);
		Node.insertRecursive(root, 22);
	
		Node.insertRecursive(root, 55);
		Node.insertRecursive(root, 52);
		Node.insertRecursive(root, 57);
		
		int num = root.getData();
		System.out.print(num);
	
		num = root.getLeft().getData();
		System.out.print(num);
		
		System.out.print(" ");
		
		num = root.getRight().getData();
		System.out.print(num);
		
		System.out.println();
		
		num = root.getLeft().getLeft().getData();
		System.out.print(num);
		
		System.out.print(" ");
		
		num = root.getLeft().getRight().getData();
		System.out.print(num);
		
		System.out.print(" ");
		
		num = root.getRight().getLeft().getData();
		System.out.print(num);
		
		System.out.print(" ");
		
		num = root.getRight().getRight().getData();
		System.out.print(num);
		
		System.out.println();
		
		Node.insertRecursive(root, 53);
		num = root.getRight().getLeft().getRight().getData();
		System.out.print(num);

	}
}

 

8. 깊은 트리 복사

  - 트리를 복사할 때 깊은 복사를 한다는 걸 보여주기 위해 사용한다. 

  Ex)

<hide/>
	public static Node copyRecursive(final Node node) {
		
		if(node == null) {
			return null;
		}
	
		Node newNode = new Node(node.data);
		newNode.left = copyRecursive(node.left);
		newNode.right = copyRecursive(node.left);
				
		return newNode;
	}

 

9. 레드블랙트리(red-black tree)

 

  - 각 노드가 레드 혹을 블랙

    -> 노드에 저장하는 데이터가 아니라 1비트 짜리 추가 정보

  - 스스로 균형잡는(self-balancing) 트리

 

  - 특성

  1) 루트는 항상 블랙

  2) 모든 리프 노드(NIL)는 블랙이다.

    -> 널포인터도 리프 노드에 포함. < -> 널이 아닌 리프노드

    -> 리프노드는 데이터를 담지 않는다.

 

  3) 레드의 자식은 언제나 블랙

  4) 어떤 노드와 리프 사이에 있는 블랙 노드 수는 동일하다. (블랙 높이)

 

  Def) 블랙 깊이(black depth): 루트와 어떤 노드 사이에 있는 블랙 노드 수

  Def) 블랙 높이(black height): 어떤 노드와 리프 사이에 있는 블랙 수