Believe into

* 이진 탐색 트리

package algo.bstree;

import java.util.ArrayList;
import java.util.List;

public class BSTree {

	public enum DIR {
		LEFT, RIGHT
	}

	public class Node {

		public int data;
		public Node left;
		public Node right;

		public Node(int data) {
			this.data = data;
			left = null;
			right = null;
		}
	}

	public Node root;

	public void insert(int data) {

		Node newNode = new Node(data);

		if (root == null) {
			root = newNode;
			return;
		}

		Node current = root;
		Node parent = null;

		while (true) {

			parent = current;

			if (current.data == data) {

				System.out.println("이미 있는 데이터 입니다 : " + data);
				return;

			} else if (current.data < data) {

				current = current.right;
				if (current == null) {
					parent.right = newNode;
					System.out.println("노드 삽입 : " + data);
					return;
				}

			} else {

				current = current.left;
				if (current == null) {
					parent.left = newNode;
					System.out.println("노드 삽입 : " + data);
					return;
				}

			}

		}
	}

	public void find(int data) {

		find(root, data);

	}

	private Node find(Node node, int data) {

		if (node == null) {
			System.out.println("찾는 데이터가 없습니다 : " + data);
			return null;
		}

		if (node.data == data) {
			System.out.println("찾았습니다 : " + data);
			return node;
		}

		if (node.data < data)
			return find(node.right, data);
		else
			return find(node.left, data);

	}

	public void delete(int data) {

		Node current = root;
		Node parent = root;
		DIR dir = null;

		if (current == null) {
			System.out.println("삭제할 데이터가 없습니다 : " + data);
			return;
		}

		while (current.data != data) {

			parent = current;

			if (current.data < data) {

				current = current.right;
				dir = DIR.RIGHT;

			} else {

				current = current.left;
				dir = DIR.LEFT;
			}

			if (current == null) {
				System.out.println("삭제할 데이터가 없습니다 : " + data);
				return;
			}

		}

		if (current.left == null && current.right == null) {

			// 삭제할 노드가 자식을 갖지 않는 경우

			if (current == root) {
				// 루트 노드밖에 없는 경우
				current = null;
				root = null;
			} else {
				if (dir == DIR.LEFT)
					parent.left = null;
				else
					parent.right = null;
			}

		} else if (current.right == null || current.left == null) {

			// 삭제할 노드가 자식을 한개만 갖는경우

			if (current == root) {
				// 루트 노드 인 경우
				root = current.right == null ? current.left : current.right;
			} else {

				if (dir == DIR.LEFT) {
					parent.left = current.right == null ? current.left : current.right;
				} else {
					parent.right = current.right == null ? current.left : current.right;
				}
			}

		} else {
			// 자식 노드가 둘다 있는 경우
			// current 노드가 자식을 둘다 갖는경우, Successor를 current에 Set해줘야한다.
			Node successor = getSuccessor(current);
			if (current == root) {

				root = successor;

			} else {

				if (dir == DIR.LEFT)
					parent.left = successor;
				else
					parent.right = successor;

			}

			successor.left = current.left;
		}

		if (root == null || root == current)
			System.out.println("루트 노드 삭제 : " + data);
		else
			System.out.println("노드 삭제 : " + data);

	}

	public Node getSuccessor(Node delNode) {

		// successor는 Right Sub Tree 중에서 가장 작은 값이다.

		Node successor = delNode.right;
		Node successorParent = delNode;

		while (successor.left != null) {
			successorParent = successor;
			successor = successor.left;
		}

		// successor가 Del Node의 오른쪽 자식과 같다면
		// sucessor의 right 트리는 그대로 따라 올라간다.
		if (delNode.right != successor) {
			successorParent.left = successor.right;
			successor.right = delNode.right;
		}

		return successor;
	}

	public void inOrder(Node node) {
		if (node != null) {
			inOrder(node.left);
			System.out.print(" " + node.data);
			inOrder(node.right);
		}
	}

	public void printPreety() {
		List<Node> list = new ArrayList<Node>();
		list.add(root);
		printTree(list, getHeight(root));
	}

	private int getHeight(Node head) {

		if (head == null) {
			return 0;
		} else {
			return 1 + Math.max(getHeight(head.left), getHeight(head.right));
		}
	}

	private void printTree(List<Node> levelNodes, int level) {

		List<Node> nodes = new ArrayList<Node>();

		// indentation for first node in given level
		printIndentForLevel(level);

		for (Node Node : levelNodes) {

			// print node data
			System.out.print(Node == null ? " " : Node.data);

			// spacing between nodes
			printSpacingBetweenNodes(level);

			// if its not a leaf node
			if (level > 1) {
				nodes.add(Node == null ? null : Node.left);
				nodes.add(Node == null ? null : Node.right);
			}
		}
		System.out.println();

		if (level > 1) {
			printTree(nodes, level - 1);
		}
	}

	private void printIndentForLevel(int level) {
		for (int i = (int) (Math.pow(2, level - 1)); i > 0; i--) {
			System.out.print(" ");
		}
	}

	private void printSpacingBetweenNodes(int level) {
		// spacing between nodes
		for (int i = (int) ((Math.pow(2, level - 1)) * 2) - 1; i > 0; i--) {
			System.out.print(" ");
		}
	}

}

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import algo.binarytree.MyBinaryTree;
import algo.binarytree.MyBinaryTree.DIR;
import algo.binarytree.MyBinaryTree.MyBTNode;
import algo.bstree.BSTree;
import algo.radix.MyRadixSort;

public class Main {

	public static void main(String[] args) {

		BSTree tree = new BSTree();
		makeBinarySearchTree(tree);
		
		prettyPrintTree(tree);
		
		tree.find(4);
		
		tree.delete(2);
		prettyPrintTree(tree);
		
		tree.delete(4);
		prettyPrintTree(tree);
		
		tree.delete(10);
		prettyPrintTree(tree);
		
		tree.delete(1);
		prettyPrintTree(tree);
		
		tree.insert(9);
		prettyPrintTree(tree);
		
		tree.insert(1);
		prettyPrintTree(tree);
		
		tree.find(100);
		prettyPrintTree(tree);
		
		tree.insert(100);
		prettyPrintTree(tree);
		
		tree.delete(15);
		prettyPrintTree(tree);
		
		tree.delete(16);
		prettyPrintTree(tree);
		
		tree.delete(9);
		prettyPrintTree(tree);
		
		tree.delete(8);
		prettyPrintTree(tree);
		
		tree.delete(3);
		prettyPrintTree(tree);
		
	}
	
	public static void prettyPrintTree(BSTree tree) {
//		tree.inOrder(tree.root);
//		System.out.println("");
		System.out.println("---- 트리 출력 ----");
		tree.printPreety();
		System.out.println("");
	}
	
	public static void makeBinarySearchTree(BSTree tree) {
		
		tree.insert(3);
		tree.insert(8);
		tree.insert(1);
		tree.insert(4);
		tree.insert(6);
		tree.insert(2);
		tree.insert(10);
		tree.insert(9);
		tree.insert(20);
		tree.insert(25);
		tree.insert(15);
		tree.insert(16);
		
	}
	

}

**** 결과 ****


노드 삽입 : 8
노드 삽입 : 1
노드 삽입 : 4
노드 삽입 : 6
노드 삽입 : 2
노드 삽입 : 10
노드 삽입 : 9
노드 삽입 : 20
노드 삽입 : 25
노드 삽입 : 15
노드 삽입 : 16
---- 트리 출력 ----
                                3                                                               
                1                               8                               
                        2               4               10               
                                            6       9       20       
                                                          15   25   
                                                           16     

찾았습니다 : 4
노드 삭제 : 2
---- 트리 출력 ----
                                3                                                               
                1                               8                               
                                        4               10               
                                            6       9       20       
                                                          15   25   
                                                           16     

노드 삭제 : 4
---- 트리 출력 ----
                                3                                                               
                1                               8                               
                                        6               10               
                                                    9       20       
                                                          15   25   
                                                           16     

노드 삭제 : 10
---- 트리 출력 ----
                3                               
        1               8               
                    6       15       
                          9   20   
                             16 25 

노드 삭제 : 1
---- 트리 출력 ----
                3                               
                        8               
                    6       15       
                          9   20   
                             16 25 

이미 있는 데이터 입니다 : 9
---- 트리 출력 ----
                3                               
                        8               
                    6       15       
                          9   20   
                             16 25 

노드 삽입 : 1
---- 트리 출력 ----
                3                               
        1               8               
                    6       15       
                          9   20   
                             16 25 

찾는 데이터가 없습니다 : 100
---- 트리 출력 ----
                3                               
        1               8               
                    6       15       
                          9   20   
                             16 25 

노드 삽입 : 100
---- 트리 출력 ----
                                3                                                               
                1                               8                               
                                        6               15               
                                                    9       20       
                                                          16   25   
                                                               100 

노드 삭제 : 15
---- 트리 출력 ----
                                3                                                               
                1                               8                               
                                        6               16               
                                                    9       20       
                                                              25   
                                                               100 

노드 삭제 : 16
---- 트리 출력 ----
                3                               
        1               8               
                    6       20       
                          9   25   
                               100 

노드 삭제 : 9
---- 트리 출력 ----
                3                               
        1               8               
                    6       20       
                              25   
                               100 

노드 삭제 : 8
---- 트리 출력 ----
        3               
    1       20       
          6   25   
               100 

노드 삭제 : 3
---- 트리 출력 ----
        6               
    1       20       
              25   
               100 

* 이진 트리

알고리즘

package algo.binarytree;

import algo.queue.MyQueue;

public class MyBinaryTree {

	public enum DIR{
		LEFT, RIGHT
	}

	public class MyBTNode{
		
		public int info;
		public MyBTNode left;
		public MyBTNode parent;
		public MyBTNode right;
		
		public MyBTNode(int info) {
			this.info = info;
		}
		
	}
	
	private MyBTNode root;
	private MyQueue<MyBTNode> queue;
	
	public MyBinaryTree() {
		queue = new MyQueue<>();
	}
	
	public MyBTNode getRoot() {
		return root;
	}
	
	public MyBTNode addRoot(int info) {
		root = new MyBTNode(info);
		return root;
	}
	
	public MyBTNode addNode(MyBTNode parent, int info, DIR dir) {
		
		MyBTNode newNode = new MyBTNode(info);
		newNode.parent = parent;
		
		if(dir == DIR.LEFT)
			parent.left = newNode;
		else
			parent.right = newNode;
		
		return newNode;
		
	}
	
	public void print(MyBTNode node) {
		System.out.println("방문 : " + node.info);
	}
	
	public void inOrder(MyBTNode node) {
		
		// TL -> ROOT -> TR
		if(node == null)
			return;
		
		inOrder(node.left);
		print(node);
		inOrder(node.right);
		
	}
	
	public void preOrder(MyBTNode node) {
		
		// ROOT -> TL - > TR
		
		if(node == null)
			return;
		
		print(node);
		preOrder(node.left);
		preOrder(node.right);
		
	}
	
	public void postOrder(MyBTNode node) {
		
		// TL - > TR -> ROOT
		
		if(node == null)
			return;
		
		postOrder(node.left);
		postOrder(node.right);
		print(node);
		
	}
	
	public void levelOrder() {
		
		queue.enqueue(root);
		print(root);
		
		MyBTNode node = null;
		while(!queue.isEmpty()) {
			
			node = queue.dequeue();
			
			if(node.left != null) {
				print(node.left);
				queue.enqueue(node.left);
			}
			
			if(node.right != null) {
				print(node.right);
				queue.enqueue(node.right);
			}
			
		}
		
	}
	
}

테스트

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import algo.binarytree.MyBinaryTree;
import algo.binarytree.MyBinaryTree.DIR;
import algo.binarytree.MyBinaryTree.MyBTNode;
import algo.radix.MyRadixSort;

public class Main {

	public static void main(String[] args) {

		MyBinaryTree tree = new MyBinaryTree();
		makeBinaryTree(tree);
		printBinaryTree(tree);
		
	}
	
	public static void makeBinaryTree(MyBinaryTree tree) {
		MyBTNode root = tree.addRoot(1);
			MyBTNode node3 = tree.addNode(root, 3, DIR.LEFT);
				tree.addNode(node3, 2, DIR.LEFT);
				tree.addNode(node3, 5, DIR.RIGHT);
			MyBTNode node7 = tree.addNode(root, 7, DIR.RIGHT);
				tree.addNode(node7, 8, DIR.RIGHT);
	}
	
	public static void makeBinaryTreeForLevelOrder(MyBinaryTree tree) {
		
		MyBTNode root = tree.addRoot(3);
			MyBTNode node1 = tree.addNode(root, 1, DIR.LEFT);
				MyBTNode node0 = tree.addNode(node1, 0, DIR.LEFT);
				MyBTNode node2 = tree.addNode(node1, 2, DIR.RIGHT);
					MyBTNode node7 = tree.addNode(node2, 7, DIR.LEFT);
					MyBTNode node8 = tree.addNode(node2, 8, DIR.RIGHT);
			MyBTNode node5 = tree.addNode(root, 5, DIR.RIGHT);
				MyBTNode node4 = tree.addNode(node5, 4, DIR.LEFT);
				MyBTNode node6 = tree.addNode(node5, 6, DIR.RIGHT);
		
	}
	
	public static void printBinaryTree(MyBinaryTree tree) {
		
		System.out.println("* IN ORDER");
		tree.inOrder(tree.getRoot());

		System.out.println("* PRE ORDER");
		tree.preOrder(tree.getRoot());
		
		System.out.println("* POST ORDER");
		tree.postOrder(tree.getRoot());
		
		makeBinaryTreeForLevelOrder(tree);
		
		System.out.println("* LEVEL ORDER");
		tree.levelOrder();
		
	}

}

<결과>
* IN ORDER
방문 : 2
방문 : 3
방문 : 5
방문 : 1
방문 : 7
방문 : 8
* PRE ORDER
방문 : 1
방문 : 3
방문 : 2
방문 : 5
방문 : 7
방문 : 8
* POST ORDER
방문 : 2
방문 : 5
방문 : 3
방문 : 8
방문 : 7
방문 : 1
* LEVEL ORDER
방문 : 3
방문 : 1
방문 : 5
방문 : 0
방문 : 2
방문 : 4
방문 : 6
방문 : 7
방문 : 8

* Radix Sort

* Counting Sort를 활용

package algo.radix;

import java.util.Arrays;

public class MyRadixSort {

	private int[] itemArr;
	private Integer[] sortedItemArr;
	private int[] countingArr;
	
	public void sort(int[] arr) {
		
		this.itemArr = arr;
		this.sortedItemArr = new Integer[itemArr.length];
		this.countingArr = new int[10];
		
		int maxItem = getMax();
		
		for(int i = 1 ; maxItem / i > 0 ; i*=10) {
			countSort(i);
		}
	}
	
	private void countSort(int div) {
		
		Arrays.fill(sortedItemArr, 0);
		Arrays.fill(countingArr, 0);
		
		printArr(itemArr, "시작 배열           -> ");
		
		//자릴수에 따라 카운팅 및 정렬
		int item = 0;
		for(int i = 0 ; i < itemArr.length ; i++) {
			item = itemArr[i] / div % 10;
			countingArr[item] = countingArr[item] + 1;
		}
		
		printArr(countingArr, "카운팅 배열        -> ");
		
		int sum = 0;
		for(int i = 0 ; i < countingArr.length ; i++) {
			sum += countingArr[i];
			countingArr[i] = sum;
		}
		
		System.out.println("* 정렬 시작");
		
		int targetIdx = 0;
		for(int i = itemArr.length - 1 ; i >= 0 ; i--) {
			
			item = itemArr[i] / div % 10;
			targetIdx = countingArr[item];
			sortedItemArr[targetIdx-1] = itemArr[i];
			countingArr[item] = countingArr[item] - 1;
			
			printArr(countingArr, "\t카운팅 누적 배열 \t-> ");
			printIntegerArr(sortedItemArr, "\t정렬된 배열1\t-> ");
			
		}
		
		for(int i = 0 ; i < sortedItemArr.length ; i++) {
			itemArr[i] = sortedItemArr[i];
		}
		
		printArr(itemArr, "\t정렬된 배열2\t-> ");

	}
	
	private int getMax() {
		
		int max = itemArr[0];
		for (int i = 0; i < itemArr.length; i++) {

			if (itemArr[i] > max)
				max = itemArr[i];

		}
		
		return max;
	}
	
	private void printArr(int[] targetArr, String msg) {

		System.out.print(msg);
		for (int i = 0; i < targetArr.length ; i++)
			System.out.print(targetArr[i] + " ");
		System.out.println();

	}
	
	private void printIntegerArr(Object[] targetArr, String msg) {

		System.out.print(msg);
		for (int i = 0; i < targetArr.length ; i++)
			System.out.print(targetArr[i] + " ");
		System.out.println();

	}
	
}

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import algo.countingsort.MyCountingSort;
import algo.radix.MyRadixSort;

public class Main {

	public static void main(String[] args) {

		MyRadixSort algo = new MyRadixSort();
		algo.sort(new int[] {170, 45, 75, 90, 802, 24, 2, 66});
		
	}

}

[결과]
시작 배열           -> 170 45 75 90 802 24 2 66 
카운팅 배열        -> 2 0 2 0 1 2 1 0 0 0 
* 정렬 시작
	카운팅 누적 배열 	-> 2 2 4 4 5 7 7 8 8 8 
	정렬된 배열1	-> 0 0 0 0 0 0 0 66 
	카운팅 누적 배열 	-> 2 2 3 4 5 7 7 8 8 8 
	정렬된 배열1	-> 0 0 0 2 0 0 0 66 
	카운팅 누적 배열 	-> 2 2 3 4 4 7 7 8 8 8 
	정렬된 배열1	-> 0 0 0 2 24 0 0 66 
	카운팅 누적 배열 	-> 2 2 2 4 4 7 7 8 8 8 
	정렬된 배열1	-> 0 0 802 2 24 0 0 66 
	카운팅 누적 배열 	-> 1 2 2 4 4 7 7 8 8 8 
	정렬된 배열1	-> 0 90 802 2 24 0 0 66 
	카운팅 누적 배열 	-> 1 2 2 4 4 6 7 8 8 8 
	정렬된 배열1	-> 0 90 802 2 24 0 75 66 
	카운팅 누적 배열 	-> 1 2 2 4 4 5 7 8 8 8 
	정렬된 배열1	-> 0 90 802 2 24 45 75 66 
	카운팅 누적 배열 	-> 0 2 2 4 4 5 7 8 8 8 
	정렬된 배열1	-> 170 90 802 2 24 45 75 66 
	정렬된 배열2	-> 170 90 802 2 24 45 75 66 
시작 배열           -> 170 90 802 2 24 45 75 66 
카운팅 배열        -> 2 0 1 0 1 0 1 2 0 1 
* 정렬 시작
	카운팅 누적 배열 	-> 2 2 3 3 4 4 4 7 7 8 
	정렬된 배열1	-> 0 0 0 0 66 0 0 0 
	카운팅 누적 배열 	-> 2 2 3 3 4 4 4 6 7 8 
	정렬된 배열1	-> 0 0 0 0 66 0 75 0 
	카운팅 누적 배열 	-> 2 2 3 3 3 4 4 6 7 8 
	정렬된 배열1	-> 0 0 0 45 66 0 75 0 
	카운팅 누적 배열 	-> 2 2 2 3 3 4 4 6 7 8 
	정렬된 배열1	-> 0 0 24 45 66 0 75 0 
	카운팅 누적 배열 	-> 1 2 2 3 3 4 4 6 7 8 
	정렬된 배열1	-> 0 2 24 45 66 0 75 0 
	카운팅 누적 배열 	-> 0 2 2 3 3 4 4 6 7 8 
	정렬된 배열1	-> 802 2 24 45 66 0 75 0 
	카운팅 누적 배열 	-> 0 2 2 3 3 4 4 6 7 7 
	정렬된 배열1	-> 802 2 24 45 66 0 75 90 
	카운팅 누적 배열 	-> 0 2 2 3 3 4 4 5 7 7 
	정렬된 배열1	-> 802 2 24 45 66 170 75 90 
	정렬된 배열2	-> 802 2 24 45 66 170 75 90 
시작 배열           -> 802 2 24 45 66 170 75 90 
카운팅 배열        -> 6 1 0 0 0 0 0 0 1 0 
* 정렬 시작
	카운팅 누적 배열 	-> 5 7 7 7 7 7 7 7 8 8 
	정렬된 배열1	-> 0 0 0 0 0 90 0 0 
	카운팅 누적 배열 	-> 4 7 7 7 7 7 7 7 8 8 
	정렬된 배열1	-> 0 0 0 0 75 90 0 0 
	카운팅 누적 배열 	-> 4 6 7 7 7 7 7 7 8 8 
	정렬된 배열1	-> 0 0 0 0 75 90 170 0 
	카운팅 누적 배열 	-> 3 6 7 7 7 7 7 7 8 8 
	정렬된 배열1	-> 0 0 0 66 75 90 170 0 
	카운팅 누적 배열 	-> 2 6 7 7 7 7 7 7 8 8 
	정렬된 배열1	-> 0 0 45 66 75 90 170 0 
	카운팅 누적 배열 	-> 1 6 7 7 7 7 7 7 8 8 
	정렬된 배열1	-> 0 24 45 66 75 90 170 0 
	카운팅 누적 배열 	-> 0 6 7 7 7 7 7 7 8 8 
	정렬된 배열1	-> 2 24 45 66 75 90 170 0 
	카운팅 누적 배열 	-> 0 6 7 7 7 7 7 7 7 8 
	정렬된 배열1	-> 2 24 45 66 75 90 170 802 
	정렬된 배열2	-> 2 24 45 66 75 90 170 802