[자바][자료구조] 이진탐색트리

 

1.개요

이진 탐색 트리에서 다음의 멤버 메소드를 재귀 함수로 구현한다. 필요 시 보조 메소드 사용한다.

2. 설명

public boolean insert(T data)

root가 비었을땐 root에 바로 insert하고 이외의 경우엔 크기 비교로 자리를 찾기위한 탐색을 시작합니다. insert가 성공하면 insertSuccess는 true가 됩니다. 틀리다면 false가 됩니다.

public BSTNode<T> insert(BSTNode<T> tree, T data)

tree는 현재의 BST Node이고 data는 insert 하기 위한 데이터 값입니다. tree의 item과 data의 크기를 비교합니다. compareTo를 사용해서 data가 크면 오른족, data가 더 작으면 왼쪽을 탐색하고 같으면 insert false입니다.

public boolean search(T data)

root가 null값이면 data에 상관없이 search fail이고 아니면 recursive search를 시작합니다.

private boolean search(BSTNode<T> tree, T data)

BST에 따라서 값이 크면 right탐색 작으면 left 탐색합니다. right값이 크면서,left 값이 작으면서 null이라면 search false입니다. 값이 같으면 찾고, search는 true입니다.

public boolean remove(T data)

트리가 비었다면 data상관없이 false입니다. 만약 있다면 search 후 제거하기 위한 함수를 호출합니다.

public BSTNode<T> remove(BSTNode<T> tree, T data)

자식이 없다면 그냥 제거합니다. 자식이 하나라면 아래 노드를 이어붙힙니다. 자석이 둘인 경우 왼쪽 자식의 가장 끝 오른쪽 자식을 가져옵니다. 제거를 위해선 부모노드에서 자식의 정보를 지워야하기에 부모를 찾아서 처리해주는 부분을 넣었습니다.

private BSTNode<T> FindParent(BSTNode<T> tree, BSTNode<T> child)

root부터 child의 부모노드를 탐색합니다.

private BSTNode<T> FindReplacement(BSTNode<T> tree, BSTNode<T> parent)

바꿀 곳을 찾는 메소드입니다.

public boolean isEmpty()

BST Tree가 비었는지 확인합니다.

public void print()

print 재귀호출합니다.

public void print(BSTNode<T> tree, int skip)

tree의 item을 출력합니다. 트리의 끝까지 탐색합니다. 트리의 왼쪽에 뭔가가 있다면 L을 출력합니다. 트리의 오른쪽이 뭔가가 있다면 R을 출력합니다. 트리의 왼족으로 skip의 10만큼 재귀를 실행합니다.

public void inorderTraverse()

inorderTraverse를 재귀로 호출합니다.

private void inorderTraverse(BSTNode<T> tree)

트리의 끝까지 탐색합니다. 트리의 왼쪽을 출력하고 오른쪽으로 이동하는 행동을 반복합니다.

public int height()

비었으면 -1을 반환하고 아니면 recursive call을 실행합니다. 0 count로 root부터 탐색합니다.

private int heightCount(BSTNode<T> tree, int I)

left, right가 각각 존재할 경우 탐색하면서 카운트를 증가시킵니다. 존재하지 않는다면 현재 count를 리턴하고 둘 중 큰 값을 반환합니다.

public int countNodes()

inorder하면서 count값을 증가시키는 역할을 CountInorder가 진행하고 countNodes()는 값을 반환합니다.

private void CountInorder(BSTNode<T> tree, int[] cn)

tree의 inorder를 탐색하며 count값을 증가시킵니다.

public int width()

비었다면 0을 출력하고 아니면 recursive call합니다. ArrayList를 만들어 depth값을 인덱스로갖는 width list를 만들어 max값을 구합니다.

private void widthCount(BSTNode<T> tree, int i, ArrayList<Integer> widthlist)

ArrayList에 depth를 index로 하는곳에 1을 더해줍니다. 현재노드 개수가 추가됩니다. 새로운 depth에 도달한 경우 새로운 index를 생성합니다.

public BSTNode<T> kthSmallestNode(int kth)

BST에서 순차적인서치는 inorder travel을 따릅니다. inorder4kth를 따르며 count 값을 구합니다.

private BSTNode<T> inorder4kth(BSTNode<T> tree, int k, int[] count)

kthSmallestNode의 recursive call을 수행합니다.

3. 코드

import java.util.ArrayList;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.Scanner;

 

public class BStree {

public static void main(String[] args) {

BSTree<Integer> tree = new BSTree<Integer>();

String command;

int data;

 

Scanner input = new Scanner(System.in);

System.out.println("Enter a command: i(insert), r(emove), s(earch), inorder, p(rint), h(eight), nc(node count), w(idth), k(th smallest node), c(count trees),or q(uit)");

 

while (true) {

System.out.print("> ");

command = input.next();

if (command.equals("i")) {

data = input.nextInt();

if (tree.insert(data))

System.out.println(data + " inserted.");

else

System.out.println(data + " is in the tree.");

} else if (command.equals("r")) {

data = input.nextInt();

if (tree.remove(data))

System.out.println(data + " removed.");

else

System.out.println("No such " + data + "!");

} else if (command.equals("s")) {

data = input.nextInt();

if (tree.search(data))

System.out.println(data + " is in the tree.");

else

System.out.println("No such " + data + "!");

} else if (command.equals("inorder"))

tree.inorderTraverse();

else if (command.equals("h"))

System.out.println("Tree height: " + tree.height());

 

else if (command.equals("nc"))

System.out.println("Node count: " + tree.countNodes());

else if (command.equals("w"))

System.out.println("Max number of nodes: " + tree.width());

else if (command.equals("k")) {

data = input.nextInt();

BSTNode<Integer> node = tree.kthSmallestNode(data);

if (node != null)

System.out.println(node.item);

else

System.out.println("Out of range!");

} else if (command.equals("c")) {

int numKeys = input.nextInt();

System.out.println("Number of trees: " + tree.countTrees(numKeys));

} else if (command.equals("p"))

tree.print();

else if (command.equals("q")) {

System.out.println("Commands terminated.");

break;

}

}

input.close();

}

}

 

class BSTNode<T> {

public T item;

public BSTNode<T> left;

public BSTNode<T> right;

 

public BSTNode(T item) {

this.item = item;

left = null;

right = null;

}

 

public BSTNode(T item, BSTNode<T> left, BSTNode<T> right) {

this.item = item;

this.left = left;

this.right = right;

}

}

 

class BSTree<T extends Comparable<T>> {

public BSTNode<T> root;

private boolean insertSuccess;

private boolean removeSuccess;

 

public BSTree() {

root = null;

}

 

public boolean insert(T data) {

if (isEmpty()) {

root = new BSTNode<T>(data);

insertSuccess = true;

} else root = insert(root, data);

return insertSuccess;

}

 

public BSTNode<T> insert(BSTNode<T> tree, T data) {

if (data.compareTo(tree.item) > 0) {

if (tree.right == null) {

tree.right = new BSTNode<T>(data);

insertSuccess = true;

return root;

} else insert(tree.right, data);

} else if (data.compareTo(tree.item) < 0) {

if (tree.left == null) {

tree.left = new BSTNode<T>(data);

insertSuccess = true;

return root;

} else insert(tree.left, data);

} else {

insertSuccess = false;

return root;

}

return root;

}

 

public boolean search(T data) {

if (isEmpty()) return false;

else return search(root, data);

}

 

private boolean search(BSTNode<T> tree, T data) {

if (data.compareTo(tree.item) > 0) {

if (tree.right != null)

return search(tree.right, data);

else return false;

} else if (data.compareTo(tree.item) < 0) {

if (tree.left != null)

return search(tree.left, data);

else return false;

} else {

return true;

}

}

public boolean remove(T data) {

if (isEmpty()) return false;

else root = remove(root, data);

return removeSuccess;

}

 

public BSTNode<T> remove(BSTNode<T> tree, T data) {

if (data.compareTo(tree.item) > 0) {

if (tree.right != null)

return remove(tree.right, data);

else {

removeSuccess = false;

return root;

}

} else if (data.compareTo(tree.item) < 0) {

if (tree.left != null)

return remove(tree.left, data);

else {

removeSuccess = false;

return root;

}

} else {

BSTNode<T> parent = FindParent(root, tree);

if (parent != null) {

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

if (parent.left == tree) parent.left = null;

else if (parent.right == tree) parent.right = null;

} else if (tree.right == null) {

if (parent.left == tree) parent.left = tree.left;

else if (parent.right == tree) parent.right = tree.left;

} else if (tree.left == null) {

if (parent.left == tree) parent.left = tree.right;

else if (parent.right == tree) parent.right = tree.right;

} else {

BSTNode<T> temp = FindReplacement(tree.left, tree);

temp.left = tree.left;

temp.right = tree.right;

if (parent.left == tree) parent.left = temp;

else if (parent.right == tree) parent.right = temp;

}

removeSuccess = true;

} else {

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

root = null;

} else if (tree.right == null) {

root = tree.left;

} else if (tree.left == null) {

root = tree.right;

} else {

BSTNode<T> temp = FindReplacement(tree.left, tree);

temp.left = tree.left;

temp.right = tree.right;

root = temp;

}

removeSuccess = true;

}

return root;

}

}

private BSTNode<T> FindParent(BSTNode<T> tree, BSTNode<T> child) {

if (child.item.compareTo(tree.item) > 0) {

if (tree.right == child)

return tree;

else return FindParent(tree.right, child);

} else if (child.item.compareTo(tree.item) < 0) {

if (tree.left == child)

return tree;

else return FindParent(tree.left, child);

} else {

return null;

}

}

 

private BSTNode<T> FindReplacement(BSTNode<T> tree, BSTNode<T> parent) {

if (tree.right == null) {

if (tree.left == null) {

if(parent.right == tree) parent.right = null;

else if(parent.left == tree) parent.left = null;

return tree;

} else {

if(parent.right == tree) parent.right = tree.left;

else if(parent.left == tree) parent.left = tree.left;

tree.left = null;

return tree;

}

} else {

return FindReplacement(tree.right, tree);

}

}

 

public boolean isEmpty() {

return root == null;

}

 

public void print() {

print(root, 0);

}

 

public void print(BSTNode<T> tree, int skip) {

if (tree != null) {

print(tree.right, skip + 10);

for (int i = 0; i < skip; i++)

System.out.print(" ");

System.out.print(tree.item);

if (tree.left != null)

System.out.print(",L");

if (tree.right != null)

System.out.print(",R");

System.out.println();

print(tree.left, skip + 10);

}

}

 

public void inorderTraverse() {

inorderTraverse(root);

System.out.println();

}

 

private void inorderTraverse(BSTNode<T> tree) {

if (tree != null) {

inorderTraverse(tree.left);

System.out.print(tree.item + " ");

inorderTraverse(tree.right);

}

}

 

public int height() {

if (isEmpty()) return -1;

else return heightCount(root, 0);

}

 

private int heightCount(BSTNode<T> tree, int i) {

int left = -1, right = -1;

if (tree.left != null) left = heightCount(tree.left, i + 1);

if (tree.right != null) right = heightCount(tree.right, i + 1);

if (tree.left == null && tree.right == null) return i;

else if (left >= right) return left;

else return right;

}

 

public int countNodes() {

int cn[] = new int[1];

CountInorder(root, cn);

return cn[0];

}

 

private void CountInorder(BSTNode<T> tree, int[] cn) {

if (tree != null) {

CountInorder(tree.left, cn);

cn[0]++;

CountInorder(tree.right, cn);

}

}

 

public int width() {

if (isEmpty()) return 0;

else {

ArrayList<Integer> widthlist = new ArrayList<Integer>();

widthCount(root, 0, widthlist);

int max = 0;

Iterator<Integer> itr = widthlist.iterator();

while (itr.hasNext()) {

int tmp = itr.next();

if (tmp > max)

max = tmp;

}

return max;

}

}

 

private void widthCount(BSTNode<T> tree, int i, ArrayList<Integer> widthlist) {

if (widthlist.size() <= i) widthlist.add(1);

else widthlist.set(i, widthlist.get(i) + 1);

if (tree.left != null) widthCount(tree.left, i + 1, widthlist);

if (tree.right != null) widthCount(tree.right, i + 1, widthlist);

}

 

 

public BSTNode<T> kthSmallestNode(int kth) {

int count[] = new int[1];

count[0] = 0;

if (isEmpty()) return null;

else return inorder4kth(root, kth, count);

}

 

private BSTNode<T> inorder4kth(BSTNode<T> tree, int k, int[] count) {

if (tree != null) {

BSTNode<T> tempNode = inorder4kth(tree.left, k, count);

if (tempNode != null) return tempNode;

count[0]++;

if (count[0] == k) return tree;

tempNode = inorder4kth(tree.right, k, count);

if (tempNode != null) return tempNode;

}

return null;

}

}