[자료구조&알고리즘] 트리, 이진 트리, 이진 검색 트리

728x90

1. 트리

비선형구조
그래프는 사이클이 있고, 트리는 사이클이 존재하지 않음
계층 관계를 나타내는 자료구조
트리는 저장위치를 찾아서 저장해야 하고, 삭제시 트리의 일부를 재구성해야하므로 링크드 리스트보다 추가/삭제 시간이 더 걸리는 대신 배열이나 링크드 리스트에 비해 검색과 정렬 기능이 더 뛰어남

1.1. 용어

노드(node)	마디	A, B, C, D, E, F, G
간선(edge)	가지, 링크
루트(root)	트리의 가장 윗부분에 위치하는 노드	A
리프(leaf) 단말 노드(terminal node) 바깥 노드(external node)	트리의 가장 아랫부분(가장 마지막)에 위치하는 노드	D, E, F, G
간 노드(non-terminal node) 안쪽 노드	루트 포함, 리프가 아닌 노드	A, B, C
자식(child) 부모(parent) 형제(sibling) 조상(ancestor) 자손(descendant)	리프는 자식을 가질 수 없음 루트는 부모를 가질 수 없음
레벨(level)	루트로부터 얼마나 떨어져 있는지에 대한 값 = 노드의 층 시작 레벨이 0일때는 level: 2	3
깊이(depth)	루트 노드부터 해당 노드까지의 경로에 있는 엣지(간선)의 수 = 몇 번 걸쳐서 내려오느냐	A의 depth: 0 D의 depth: 2
높이(length)	루트로부터 가장 멀리 떨어진 리프까지의 거리 (리프 레벨의 최댓값)	2
차수(degree)	노드가 갖는 자식의 수 차수가 0 = 단말 노드 트리의 차수 = 노드의 차수 중에서 가장 큰 차수	2
서브 트리(subtree)	루트가 사라질 때 생기는 트리	B, C 서브 트리
널 트리(null tree)	노드, 가지가 없는 트리

1.2. 순서 트리 탐색

1.2.1. 1. 너비 우선 탐색

낮은 레벨에서 시작해 왼 → 오 방향으로 검색 후 한개의 레벨이 끝나면 다음 레벨로 내려감
A → B → C → D → E → F → G

1.2.2. 2. 깊이 우선 탐색

리프까지 내려가면서 검색하는 것을 우선 순위로 탐색하며, 리프에 도달하면 부모에게 돌아감 이후 반복
A → B → D , B → E → B → A → C → F → C → G → C → A
대략 이런식으로 진행, 언제 노드를 방문할지는 3가지로 A노드를 총 3번 지나감

1.2.3. 3. 순회

전위 순회 (Preorder)

루트 → 왼 → 오
A → B → D → H → I → E → C → F → G
A를 기준으로 B, C 노드 트리가 되고, B가 루트가 될 때 D, E 노드 트리가 됨, D가 루트가 되면 H, I 트리가 되며 이것을 기준으로 전위 순회를 함

중위 순회 (Inorder)

왼 → 루트 → 오
H → D → I → B → E → A → F → C → G

후위 순회 (Postorder)

왼 → 오 → 루트
H → I → D → E → B → F → G → C → A

2. 이진 트리 & 완전 이진 트리

2.1. 이진 트리

binary tree
노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리

2.2. 완전 이진 트리

complete binary tree
루트부터 노드가 채워져 있으면서 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져있는 이진 트리
높이가 k인 완전 이진 트리가 가질 수 있는 노드의 최댓값: 2^k+1 - 1
n개의 노드를 저장할 수 있는 완전 이진 트리의 높이는 log n

3. 이진 검색 트리

binary search tree
이진 트리가 다음 조건을 만족하면 됨
treeSet 사용

2022.10.26 - [프로그래밍 언어/Java] - [Java] API_ Collection Framework (List, Set, Map)

1. 어떤 노드의 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작아야 함
2. 오른쪽 서브 트리 노드의 값은 노드 N의 키 값보다 커야 함
3. 같은 키 값을 갖는 노드는 없음

3.1. 생성

3.1.1. 노드 Node 클래스


      
      
      
    
    
      <java />
    
	//노드
	static class Node<K, V> {
		private K key;
		private V data;
		private Node<K, V> left; //왼쪽 자식 노드
		private Node<K, V> right; //오른쪽 자식 노드
		
		//생성자
		public Node(K key, V data, Node<K, V> left, Node<K, V> right) {
			super();
			this.key = key;
			this.data = data;
			this.left = left;
			this.right = right;
		}
		
		//키 값을 반환
		K getKey() {
			return key;
		}
		
		//데이터를 반환
		V getValue() {
			return data;
		}
		
		//데이터를 출력
		void print() {
			System.out.println(data);
		}
	} //end Node class

3.1.2. 이진검색트리 BinTree 클래스


      
      
      
    
    
      <java />
    
	private Node<K, V> root; //루트
	private Comparator<? super K> comparator = null; //비교자
	
    //생성자
	//노드 키 값의 대소 관계를 자연 순서에 따라 수행
	//비교자를 설정하지 않으므로 필드 comparator의 값 = null
	public BinTree() { //루트를 null로 설정하여 노드가 하나도 없는 이진 검색 트리 생성
		root = null;
	}
	
    //생성자
	//노드 키 값의 대소 관계를 판단할 때 비교자를 전달받아서 수행
	public BinTree(Comparator<? super K> c) {
		this(); //인수를 전달받지 않으면 위의 생성자 실행
		comparator = c;
	}
	
	//두 키 값을 비교하는 comp 메서드
	private int comp(K key1, K key2) {
		return (comparator == null) ? ((Comparable<K>)key1).compareTo(key2) //key1을 Comparable<K>로 형변환, compareTo로 key2와 비교
				: comparator.compare(key1, key2);
	}

3.2. 검색

노드 값: 유일한 값
왼쪽 자식 노드 값 < 부모 노드 값 < 오른쪽 자식 노드 값
K값을 찾는 과정, 루트는 가운데 노드
루트 == K : 찾음, 종료
루트 < K : 오른쪽 서브 트리
루트 > K : 왼쪽 서브 트리


      
      
      
    
    
      <java />
    
	//키에 의한 검색
	public V search(K key) {
		Node<K, V> p = root; //루트에 주목
		
		while(true) {
			if(p == null) //더이상 진행하지 않으면
				return null; //검색 실패
			
			int cond = comp(key, p.getKey()); //key와 노드 p의 키를 비교
			if(cond == 0)
				return p.getValue(); //검색 성공
			else if (cond < 0) //key쪽이 작으면
				p = p.left; //왼쪽 서브트리에서 검색
			else //key 쪽이 크면
				p = p.right; //오른쪽 서브트리에서 검색
		}
	}

위의 코드는 key와 노드 p를 비교한 변수 cond를 사용하므로
cond가 음수 = 루트가 더 크다
cond가 양수 = 찾는 K가 더 크다

3.3. 삽입

노드를 삽입한 다음 트리의 형태가 이진 검색 트리의 조건을 유지해야 함
삽입할 노드의 키와 같은 값을 가지는 노드가 이미 있다면 노드를 삽입해서는 안 됨

3.3.1. 삽입 알고리즘

1. 루트를 선택

2. key와 선택 노드의 키 값을 비교
- 값이 같으면 삽입 실패
- 값이 다르면

1. key < 삽입할 값

- 왼쪽 자식 노드가 없는 경우 노드 삽입

- 있는 경우 선택한 노드를 왼쪽 자식 노드로 옮김

2. key > 삽입할 값

- 오른쪽 자식 노드가 없는 경우 노드 삽입

- 있는 경우 선택한 노드를 오른쪽 자식 노드로 옮김

3. 2로 되돌아 감


      
      
      
    
    
      <java />
    
	//node를 루트로 하는 서브 트리에 노드<K, V>를 삽입
	private void addNode(Node<K, V> node, K key, V data) {
		int cond = comp(key, node.getKey()); //key와 노드 p를 비교
		if(cond == 0)
			return; //삽입 실패, 이미 있음
		else if(cond < 0) { //key값이 삽입할 값보다 작음
			if(node.left == null)
				node.left = new Node<K, V>(key, data, null, null);
			else
				addNode(node.left, key, data); //왼쪽 서브 트리에 주목
		} else { //key값이 삽입할 값보다 큼
			if(node.right == null)
				node.right = new Node<K, V>(key, data, null, null);
			else
				addNode(node.right, key, data); //오른쪽 서브 트리에 주목
		}
	}


      
      
      
    
    
      <java />
    
	//노드를 삽입
	public void add(K key, V data) {
		if(root == null) //트리가 비어있는 상태
			root = new Node<K, V>(key, data, null, null);
		else //addNode 메서드를 호출하여 노드를 삽입
			addNode(root, key, data);
	}

3.4. 삭제


      
      
      
    
    
      <java />
    
//키 값이 key인 노드를 삭제
	public boolean remove(K key) {
		Node<K, V> p = root; //스캔 중인 노드 (맨 처음은 루트)
		Node<K, V> parent = null; //스캔 중인 노드의 부모 노드
		boolean isLeftChild = true; //p는 부모 노드의 왼쪽 자식인가?
		
		//key의 위치 찾기
		while(true) {
			if(p == null)  //키 값 없음 or 비어있음
				return false; //진행 안 함
			
			int cond = comp(key, p.getKey()); //key와 노드 p의 키 값을 비교
			if(cond == 0) //같으면 검색 성공
				break;
			else {
				parent = p; //가지로 내려가기 전 부모를 설정 (맨 처음은 루트를 부모로 설정)
				if(cond < 0) { //key값이 노드 p보다 작으면
					isLeftChild = true; //왼쪽 자식으로 내려감
					p = p.left; //왼쪽 서브 트리에서 검색
				} else {
					isLeftChild = false;
					p = p.right; //오른쪽 서브트리에서 검색
				}
			} //end else
		} //end while
		//여기까지 마치면 key의 위치를 찾음
		//p == key, parent == p의 부모 노드
        
        ... 삭제 코드 아래에서 추가 ...
        
	}

3.4.1. 삭제 노드가 단말 노드인 경우

1. 탐색 후 삭제
2. 삭제한 노드의 부모의 링크 값을
▶ NULL로 저장

3.4.2. 삭제할 노드에 자식 노드가 하나 있는 경우

1. 탐색 후 삭제
2. 삭제한 노드의 부모의 링크 값을
▶ 삭제한 노드의 자식 노드로 저장


      
      
      
    
    
      <java />
    
//1. 단말 노드인 경우, 자식 노드가 하나인 경우
	if(p.left == null) { //p에는 왼쪽 자식이 없음
		if(p == root)
			root = p.right;
		else if(isLeftChild)
			parent.left = p.right; //부모의 왼쪽 포인터가 오른쪽 자식을 가리킴
			//기존에 p.right 포인터를 parent.left에 연결
		else
			parent.right = p.right; //부모의 오른쪽 포인터가 오른쪽 자식을 가리킴
			//기존에 p.right 포인터를 parent.right에 연결
		
	} else if(p.right == null) { //p에는 오른쪽 자식이 없음
		if(p == root)
			root = p.left;
		else if(isLeftChild)
			parent.left = p.left; //부모의 왼쪽 포인터가 왼쪽 자식을 가리킴
		else 
			parent.right = p.left; //부모의 오른쪽 포인터가 오른쪽 자식을 가리킴
	} //end if

3.4.3. 삭제할 노드(왼쪽에 위치)에 자식 노드가 두 개 있는 경우

1. 탐색 후 삭제
2. 삭제한 노드의 왼쪽 자식 중 가장 큰 값
▶ 삭제한 노드에 위치 시킴
▶ 공백이 생긴 트리는 다시 정렬

3.4.4. 삭제할 노드(오른쪽에 위치)에 자식 노드가 두 개 있는 경우

1. 탐색 후 삭제
2. 삭제한 노드의 오른쪽 자식 중 가장 작은 값
▶삭제한 노드에 위치 시킴
▶공백이 생긴 트리는 다시 정렬


      
      
      
    
    
      <java />
    
//2. 자식 노드가 두 개인 경우
	else {
		parent = p;
		Node<K, V> left = p.left; //서브 트리 가운데 가장 큰 노드
		isLeftChild = true;
		while(left.right != null) { //가장 큰 노드 left를 검색
			parent = left;
			left = left.right;
			isLeftChild = false;
		}
		
		p.key = left.key; //left의 키 값을 p로 옮김
		p.data = left.data; //left의 데이터를 p로 옮김
		if(isLeftChild)
			parent.left = left.left; //left 삭제
		else
			parent.right = left.left; //left 삭제
	} //end else

3.5. 출력

오름차순으로 출력하기 위해 중위순회 사용
root를 매개변수로 하여 printSubTree 메서드 호출

3.5.1. 오름차순


      
      
      
    
    
      <java />
    
	//node를 루트로 하는 서브 트리의 노드를 키 값의 오름차순으로 출력
	private void printSubTree(Node node) {
		if(node != null) {
			printSubTree(node.left);
			System.out.println(node.key + " " + node.data);
			printSubTree(node.right);
		}
	}
	
	//모든 노드를 키 값의 오름차순으로 출력
	public void print() {
		printSubTree(root);
	}

3.5.2. 내림차순


      
      
      
    
    
      <java />
    
	//node를 루트로 하는 서브 트리의 노드를 키 값의 내림차순으로 출력
	private void printSubTreeReverse(Node node) {
		if(node != null) {
			printSubTreeReverse(node.right); //오른쪽 서브트리를 키값의 오름차순으로
			System.err.println(node.key + " " + node.data);
			printSubTreeReverse(node.left); //왼쪽 서브트리를 키값의 오름차순으로
		}
	}
	
	//모든 노드를 키 값의 내림차순으로 출력
	public void printReverse() {
		printSubTreeReverse(root);
	}

3.5.3. 최소, 최대 key 값을 갖는 노드


      
      
      
    
    
      <java />
    
	//최소 key값을 갖는 노드 반환
	private Node<K, V> getMinNode() {
		if(root == null)
			return null;
		else {
			Node<K, V> p = root; //뿌리에 주목
			while(p.left != null) //p의 왼쪽에 값이 없으면 p가 가장 작은 것
				p = p.left;
			return p;
		}
	}
	
	//최대 key값을 갖는 노드 반환
	private Node<K, V> getMaxNode() {
		if(root == null)
			return null;
		else {
			Node<K, V> p = root; //뿌리에 주목
			while(p.right != null) //p의 오른쪽에 값이 없으면 p가 가장 큰 것
				p = p.right;
			return p;
		}
	}


      
      
      
    
    
      <java />
    
//가장 작은 키 값 반환
	public K getMinKey() {
		Node<K, V> minNode = getMinNode();
		return minNode == null ? null : minNode.getKey();
	}
	
	//가장 작은 키 값을 갖는 노드의 데이터를 반환
	public V getDataWithMinKey() {
		Node<K, V> minNode = getMinNode();
		return minNode == null ? null : minNode.getValue();
	}
	
	
	//가장 큰 키 값을 반환
	public K getMaxKey() {
		Node<K, V> maxNode = getMaxNode();
		return maxNode == null ? null : maxNode.getKey();
	}
	
	//가장 큰 키 값을 갖는 노드의 데이터를 반환
	public V getDataWithMaxKey() {
		Node<K, V> maxNode = getMaxNode();
		return maxNode == null ? null : maxNode.getValue();
	}

3.6. 전체 코드

3.6.1. BinTree.java


      
      
      
    
    
      <java />
    
package chap10_1;

import java.util.Comparator;

//이진 검색 트리
public class BinTree<K, V> {
		
	//노드
	static class Node<K, V> {
		private K key;
		private V data;
		private Node<K, V> left; //왼쪽 자식 노드
		private Node<K, V> right; //오른쪽 자식 노드
		
		//생성자
		public Node(K key, V data, Node<K, V> left, Node<K, V> right) {
			super();
			this.key = key;
			this.data = data;
			this.left = left;
			this.right = right;
		}
		
		//키 값을 반환
		K getKey() {
			return key;
		}
		
		//데이터를 반환
		V getValue() {
			return data;
		}
		
		//데이터를 출력
		void print() {
			System.out.println(data);
		}
	} //end Node class
	
	private Node<K, V> root; //루트
	private Comparator<? super K> comparator = null; //비교자
	
	//생성자
	//노드 키 값의 대소 관계를 자연 순서에 따라 수행
	//비교자를 설정하지 않으므로 필드 comparator의 값 = null
	public BinTree() { //루트를 null로 설정하여 노드가 하나도 없는 이진 검색 트리 생성
		root = null;
	}
	
	//생성자
	//노드 키 값의 대소 관계를 판단할 때 비교자를 전달받아서 수행
	public BinTree(Comparator<? super K> c) {
		this(); //인수를 전달받지 않으면 위의 생성자 실행
		comparator = c;
	}
	
	//두 키 값을 비교하는 comp 메서드
	private int comp(K key1, K key2) {
		return (comparator == null) ? ((Comparable<K>)key1).compareTo(key2) //key1을 Comparable<K>로 형변환, compareTo로 key2와 비교
				: comparator.compare(key1, key2);
	}
	
	//키에 의한 검색
	public V search(K key) {
		Node<K, V> p = root; //루트에 주목
		
		while(true) {
			if(p == null) //더이상 진행하지 않으면
				return null; //검색 실패
			
			int cond = comp(key, p.getKey()); //key와 노드 p의 키를 비교
			if(cond == 0)
				return p.getValue(); //검색 성공
			else if (cond < 0) //key쪽이 작으면
				p = p.left; //왼쪽 서브트리에서 검색
			else //key 쪽이 크면
				p = p.right; //오른쪽 서브트리에서 검색
		}
	}
	
	//node를 루트로 하는 서브 트리에 노드<K, V>를 삽입
	private void addNode(Node<K, V> node, K key, V data) {
		int cond = comp(key, node.getKey()); //key와 노드 p를 비교
		if(cond == 0)
			return; //삽입 실패, 이미 있음
		else if(cond < 0) { //key값이 삽입할 값보다 작음
			if(node.left == null)
				node.left = new Node<K, V>(key, data, null, null);
			else
				addNode(node.left, key, data); //왼쪽 서브 트리에 주목
		} else { //key값이 삽입할 값보다 큼
			if(node.right == null)
				node.right = new Node<K, V>(key, data, null, null);
			else
				addNode(node.right, key, data); //오른쪽 서브 트리에 주목
		}
	}
	
	//노드를 삽입
	public void add(K key, V data) {
		if(root == null) //트리가 비어있는 상태
			root = new Node<K, V>(key, data, null, null);
		else //addNode 메서드를 호출하여 노드를 삽입
			addNode(root, key, data);
	}
	
	//키 값이 key인 노드를 삭제
	public boolean remove(K key) {
		Node<K, V> p = root; //스캔 중인 노드 (맨 처음은 루트)
		Node<K, V> parent = null; //스캔 중인 노드의 부모 노드
		boolean isLeftChild = true; //p는 부모 노드의 왼쪽 자식인가?
		
		//key의 위치 찾기
		while(true) {
			if(p == null)  //키 값 없음 or 비어있음
				return false; //진행 안 함
			
			int cond = comp(key, p.getKey()); //key와 노드 p의 키 값을 비교
			if(cond == 0) //같으면 검색 성공
				break;
			else {
				parent = p; //가지로 내려가기 전 부모를 설정 (맨 처음은 루트를 부모로 설정)
				if(cond < 0) { //key값이 노드 p보다 작으면
					isLeftChild = true; //왼쪽 자식으로 내려감
					p = p.left; //왼쪽 서브 트리에서 검색
				} else {
					isLeftChild = false;
					p = p.right; //오른쪽 서브트리에서 검색
				}
			} //end else
		} //end while
		//여기까지 마치면 key의 위치를 찾음
		//p == key, parent == p의 부모 노드
		
		
		//1. 단말 노드인 경우, 자식 노드가 하나인 경우
		if(p.left == null) { //p에는 왼쪽 자식이 없음
			if(p == root)
				root = p.right;
			else if(isLeftChild)
				parent.left = p.right; //부모의 왼쪽 포인터가 오른쪽 자식을 가리킴
				//기존에 p.right 포인터를 parent.left에 연결
			else
				parent.right = p.right; //부모의 오른쪽 포인터가 오른쪽 자식을 가리킴
				//기존에 p.right 포인터를 parent.right에 연결
			
		} else if(p.right == null) { //p에는 오른쪽 자식이 없음
			if(p == root)
				root = p.left;
			else if(isLeftChild)
				parent.left = p.left; //부모의 왼쪽 포인터가 왼쪽 자식을 가리킴
			else 
				parent.right = p.left; //부모의 오른쪽 포인터가 오른쪽 자식을 가리킴
		} //end if
		
		//2. 자식 노드가 두 개인 경우
		else {
			parent = p;
			Node<K, V> left = p.left; //서브 트리 가운데 가장 큰 노드
			isLeftChild = true;
			while(left.right != null) { //가장 큰 노드 left를 검색
				parent = left;
				left = left.right;
				isLeftChild = false;
			}
			
			p.key = left.key; //left의 키 값을 p로 옮김
			p.data = left.data; //left의 데이터를 p로 옮김
			if(isLeftChild)
				parent.left = left.left; //left 삭제
			else
				parent.right = left.left; //left 삭제
		} //end else
		
		return true;
	} //end remove

	//node를 루트로 하는 서브 트리의 노드를 키 값의 오름차순으로 출력
	private void printSubTree(Node node) {
		if(node != null) {
			printSubTree(node.left);
			System.out.println(node.key + " " + node.data);
			printSubTree(node.right);
		}
	}
	
	//모든 노드를 키 값의 오름차순으로 출력
	public void print() {
		printSubTree(root);
	}
	
	//node를 루트로 하는 서브 트리의 노드를 키 값의 내림차순으로 출력
	private void printSubTreeReverse(Node node) {
		if(node != null) {
			printSubTreeReverse(node.right); //오른쪽 서브트리를 키값의 오름차순으로
			System.err.println(node.key + " " + node.data);
			printSubTreeReverse(node.left); //왼쪽 서브트리를 키값의 오름차순으로
		}
	}
	
	//모든 노드를 키 값의 내림차순으로 출력
	public void printReverse() {
		printSubTreeReverse(root);
	}
	
	
	//최소 key값을 갖는 노드 반환
	private Node<K, V> getMinNode() {
		if(root == null)
			return null;
		else {
			Node<K, V> p = root; //뿌리에 주목
			while(p.left != null) //p의 왼쪽에 값이 없으면 p가 가장 작은 것
				p = p.left;
			return p;
		}
	}
	
	//최대 key값을 갖는 노드 반환
	private Node<K, V> getMaxNode() {
		if(root == null)
			return null;
		else {
			Node<K, V> p = root; //뿌리에 주목
			while(p.right != null) //p의 오른쪽에 값이 없으면 p가 가장 큰 것
				p = p.right;
			return p;
		}
	}
	
	
	//가장 작은 키 값 반환
	public K getMinKey() {
		Node<K, V> minNode = getMinNode();
		return minNode == null ? null : minNode.getKey();
	}
	
	//가장 작은 키 값을 갖는 노드의 데이터를 반환
	public V getDataWithMinKey() {
		Node<K, V> minNode = getMinNode();
		return minNode == null ? null : minNode.getValue();
	}
	
	
	//가장 큰 키 값을 반환
	public K getMaxKey() {
		Node<K, V> maxNode = getMaxNode();
		return maxNode == null ? null : maxNode.getKey();
	}
	
	//가장 큰 키 값을 갖는 노드의 데이터를 반환
	public V getDataWithMaxKey() {
		Node<K, V> maxNode = getMaxNode();
		return maxNode == null ? null : maxNode.getValue();
	}
	
}

3.6.2. BinTreeTester.java


      
      
      
    
    
      <java />
    
package chap10_1;

import java.util.Scanner;

//이진 검색 트리 클래스 BinTree<K, V>의 이용 예
public class BinTreeTester {

	static Scanner scan = new Scanner(System.in);

	//데이터(회원번호 + 이름)
	static class Data {
		static final int NO = 1; //번호를 입력 받습니까?
		static final int NAME = 2; //이름을 입력 받습니까?

		private int no; //회원번호
		private String name; //이름

		//키 값
		Integer keyCode() {
			return no;
		}
		
		//문자열을 반환
		public String toString() {
			return "(" + no + ") " + name;
		}

		//데이터를 입력
		void scanData(String guide, int sw) {
			System.out.println(guide + "할 데이터를 입력하세요.");

			if((sw & NO) == NO) {
				System.out.print("번호: ");
				no = scan.nextInt();
			}
			if((sw & NAME) == NAME) {
				System.out.print("이름: ");
				name = scan.next();
			}
		}
	} //end Data class

	//메뉴 열거형
	enum Menu {
		ADD("삽입"),
		REMOVE("삭제"),
		SEARCH("검색"),
		PRINT("표시"),
		TERMINATE("종료");

		private final String message; //출력할 문자열

		static Menu MenuAt(int idx) { //서수가 idx인 열거를 반환
			for(Menu m : Menu.values())
				if(m.ordinal() == idx)
					return m;
			return null;
		}

		Menu(String string) { //생성자
			message = string;
		}

		String getMessage() { //출력할 문자열을 반환
			return message;
		}
	} //end enum

	//메뉴 선택
	static Menu SelectMenu() {
		int key;

		do {
			for(Menu m : Menu.values()) {
				System.out.printf("(%d) %9s   ", m.ordinal(), m.message);
				if((m.ordinal() % 3) == 2 &&
						m.ordinal() != Menu.TERMINATE.ordinal()	)
					System.out.println();
			}
			System.out.print("  : ");
			key = scan.nextInt();
		} while (key < Menu.ADD.ordinal() || key > Menu.TERMINATE.ordinal());
		return Menu.MenuAt(key);
	} //end SelectMenu

	public static void main(String[] args) {
		Menu menu;
		Data data;
		Data ptr;
		Data temp = new Data(); //입력용 데이터
		
		BinTree<Integer, Data> tree = new BinTree<Integer, Data>();
		
		do {
			switch (menu = SelectMenu()) {
				case ADD :
					data = new Data();
					data.scanData("삽입", Data.NO | Data.NAME);
					tree.add(data.keyCode(), data);
					break;
					
				case REMOVE :
					temp.scanData("삭제", Data.NO);
					tree.remove(temp.keyCode());
					break;
					
				case SEARCH :
					temp.scanData("검색", Data.NO);
					ptr = tree.search(temp.keyCode());
					if(ptr != null) {
						System.out.println("그 번호의 이름은 " + ptr + "입니다.");
					} else {
						System.out.println("해당 데이터가 없습니다.");
					} break;
					
				case PRINT :
					tree.print();
					break;
			}
		} while (menu != Menu.TERMINATE);
	} //end main
}

3.6.3. Quiz3.java - 비교자 사용


      
      
      
    
    
      <java />
    
package chap10_1;

import java.util.Scanner;
import java.util.Comparator;
// 이진검색트리 클래스 BinTree<K,V>의 사용 예 (comparator를 사용)

class Quiz3 {
	static Scanner stdIn = new Scanner(System.in);

	// 데이터(회원번호+이름)
	static class Data {
		public static final int NO = 1; // 번호를 입력 받습니까?
		public static final int NAME = 2; // 이름을 입력 받습니까?

		private Integer no; // 회원번호 (키 값)
		private String name; // 이름

		// 키 값
		Integer keyCode() {
			return no;
		}

		// 문자열을 반환합니다.
		public String toString() {
			return name;
		}

		// 데이터를 입력 받음
		void scanData(String guide, int sw) {
			System.out.println(guide + "하는 데이터를 입력하세요.");

			if ((sw & NO) == NO) {
				System.out.print("번호：");
				no = stdIn.nextInt();
			}
			if ((sw & NAME) == NAME) {
				System.out.print("이름：");
				name = stdIn.next();
			}
		}
	}

	// 메뉴열거형
	enum Menu {
		ADD("삽입 "), REMOVE("삭제"), SEARCH("검색"), PRINT("출력"), TERMINATE("종료");

		private final String message; // 표시용 문자열

		static Menu MenuAt(int idx) { // 서수가 idx인 열거를 반환
			for (Menu m : Menu.values())
				if (m.ordinal() == idx)
					return m;
			return null;
		}

		Menu(String string) { // 생성자
			message = string;
		}

		String getMessage() { // 출력용 문자열 반환
			return message;
		}
	}

	// 메뉴선택
	static Menu SelectMenu() {
		int key;
		do {
			for (Menu m : Menu.values()) {
				System.out.printf("(%d) %s  ", m.ordinal(), m.getMessage());
				if ((m.ordinal() % 3) == 2 && m.ordinal() != Menu.TERMINATE.ordinal())
					System.out.println();
			}
			System.out.print("：");
			key = stdIn.nextInt();
		} while (key < Menu.ADD.ordinal() || key > Menu.TERMINATE.ordinal());

		return Menu.MenuAt(key);
	}

	public static void main(String[] args) {
		Menu menu; // 메뉴
		Data data; // 추가용 데이터 참조
		Data ptr; // 검색용 데이터 참조
		Data temp = new Data(); // 입력 받기용 데이터

		//기존에는 자연 순서로 판단해서 아래처럼 BinTree 객체 생성 후 사용
		//BinTree<Integer, Data> tree = new BinTree<Integer, Data>();
		
		//compare 메서드를 구현한 클래스 작성 - 내림차순
		class IntegerDecComparator implements Comparator<Integer> {
			public int compare(Integer n1, Integer n2) {
				return (n1 > n2) ? 1 : (n1 < n2) ? -1 : 0;
			}
		}

		//IntegerDecComparator 인스턴스 생성
		// 정수의 내림차순으로 순서매기기를 수행하는 comparator
		final IntegerDecComparator INT_DEC_COMP = new IntegerDecComparator();
		BinTree<Integer, Data> tree = new BinTree<Integer, Data>(INT_DEC_COMP);

		do {
			switch (menu = SelectMenu()) {
			case ADD: // 노드의 삽입
				data = new Data();
				data.scanData("삽입 ", Data.NO | Data.NAME);
				tree.add(data.keyCode(), data);
				break;

			case REMOVE: // 노드의 삭제
				temp.scanData("삭제", Data.NO);
				tree.remove(temp.keyCode());
				break;

			case SEARCH: // 노드의 검색
				temp.scanData("검색", Data.NO);
				ptr = tree.search(temp.keyCode());
				if (ptr != null)
					System.out.println("그 번호의 이름은 " + ptr + "입니다.");
				else
					System.out.println("해당 데이터가 없습니다.");
				break;

			case PRINT : // 노드의 출력
				tree.print();
				break;
			}
		} while (menu != Menu.TERMINATE);
	}
}

728x90

'Study > Data Structure&Algorithm' 카테고리의 다른 글

[코딩테스트] two pointer technique / 투 포인터 기법 (0)	2024.05.10
[자료구조&알고리즘] 해시, 해시법(체인법, 오픈주소법) (0)	2023.07.01
[자료구조&알고리즘] 리스트 (선형, 연결(포인터, 커서), 원형, 이중 연결) (0)	2023.06.07
[자료구조&알고리즘] 셸, 퀵, 병합, 힙, 도수(계수) 정렬 (0)	2023.06.02
[자료구조&알고리즘] 재귀 알고리즘(팩토리얼, 유클리드 호제법), 하노이의 탑, N퀸 문제 / 백트래킹 (0)	2023.05.08

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

1. 트리

1.1. 용어

1.2. 순서 트리 탐색

1.2.1. 1. 너비 우선 탐색

1.2.2. 2. 깊이 우선 탐색

1.2.3. 3. 순회

2. 이진 트리 & 완전 이진 트리

2.1. 이진 트리

2.2. 완전 이진 트리

3. 이진 검색 트리

3.1. 생성

3.1.1. 노드 Node 클래스

3.1.2. 이진검색트리 BinTree 클래스

3.2. 검색

3.3. 삽입

3.3.1. 삽입 알고리즘

3.4. 삭제

3.4.1. 삭제 노드가 단말 노드인 경우

3.4.2. 삭제할 노드에 자식 노드가 하나 있는 경우

3.4.3. 삭제할 노드(왼쪽에 위치)에 자식 노드가 두 개 있는 경우

3.4.4. 삭제할 노드(오른쪽에 위치)에 자식 노드가 두 개 있는 경우

3.5. 출력

3.5.1. 오름차순

3.5.2. 내림차순

3.5.3. 최소, 최대 key 값을 갖는 노드

3.6. 전체 코드

3.6.1. BinTree.java

3.6.2. BinTreeTester.java

3.6.3. Quiz3.java - 비교자 사용

'Study > Data Structure&Algorithm' 카테고리의 다른 글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

'Study > Data Structure&Algorithm' 카테고리의 다른 글

검색 태그

최근 댓글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역