[자료구조] 09 과제

[BST]

public class BST<Key extends Comparable<Key>, Value> {
	
	private Node<Key, Value> root;
	
	public BST() {
		this.root = null;
	}

	public Key max() {
		if (root == null) return null;
		return max(root).getKey();
	}
	
	private Node<Key, Value> max(Node<Key, Value> node) {
		if (node.getRight() == null) return node;
		return max(node.getRight());
	}
	
	public void deleteMax() {
		if (root == null) {
			System.out.println("empty 트리");
			return;
		}
		root = deleteMax(root);
	}
	
	private Node<Key, Value> deleteMax(Node<Key, Value> node) {
		if (node.getRight() == null) return node.getLeft();
		node.setRight(deleteMax(node.getRight()));
		return node;	
	}
	
	public void delete_mod(Key k) {
		root = delete_mod(root, k);
	}
	
	private Node<Key, Value> delete_mod(Node<Key, Value> node, Key k) {
		if (node == null) return null;
		int t = node.getKey().compareTo(k);
		if (t > 0) {
			node.setLeft(delete_mod(node.getLeft(), k));
		} else if (t < 0) {
			node.setRight(delete_mod(node.getRight(), k));
		} else {
			if (node.getRight() == null) return node.getLeft();
			if (node.getLeft() == null) return node.getRight();
			Node<Key, Value> target = node;
			node = max(target.getLeft());
			node.setLeft(deleteMax(target.getLeft()));
			node.setRight(target.getRight());
		}
		return node;
	}
	
	public void put_mod(Key k, Value value) { 
		Node<Key, Value> newNode = new Node<>(k, value);
		if (root == null) {
			root = newNode;
			return;
		}
		Node<Key, Value> node = root;
		while (true) {
			int t = node.getKey().compareTo(k);
			if (t > 0) {
				if (node.getLeft() == null) {
					node.setLeft(newNode);
					return;
				}
				node = node.getLeft();
			} else if (t < 0) {
				if (node.getRight() == null) {
					node.setRight(newNode);
					return;
				}
				node = node.getRight();
			} else {
				node.setValue(value);
			}
		}
	}
	
	public void inorder() {
		inorder(root);
		System.out.println();
	}
	
	private void inorder(Node<Key, Value> node) {
		if (node == null) return;
		inorder(node.getLeft());
		System.out.print(node.getKey() + " ");
		inorder(node.getRight());
	}
}

[Assignment]

public class Assignment {
	
	private final int[] puts;
	private final int[] deletes;
	
	public Assignment(int[] puts, int[] deletes) {
		this.puts = puts;
		this.deletes = deletes;
	}
	
	public void assignment() {
		BST<Integer, Integer> bst = new BST<>();
		for (int i=0; i<puts.length; i++) {
			bst.put_mod(puts[i], puts[i]);
		}
		bst.inorder();
		bst.deleteMax();
		bst.inorder();
		for (int i=0; i<deletes.length; i++) {
			bst.delete_mod(deletes[i]);
		}
		bst.inorder();
	}
}