2진 탐색 트리 알고리즘 (Binary Search Tree)

- 용어 정리

노드(node) : 네트워크에서 연결 포인트 혹은 데이터 전송의 종점, 재분배점 등을 의미한다.

루트(Root) : 2진트리를 구성하는 최상위 노드

브랜치(Branch) : 노드와 노드를 연결 하는 선

레벨(Level) : 트리의 깊이를 의미한다.

서브 트리(SubTree) : 트리를 구성하는 트리(트리안에 있는 다른 트리)

- 2진 탐색 트리

• 자식 노드가 최대 2개를 가질 수 있다.
• 왼쪽 자식 노드는 부모 노드보다 값이 작다.
• 외른쪽 자식 노드는 부모 노드보다 값이 크다.

<2진 탐색 트리 입력>

입력 : 35 -> 18 -> 68 -> 7 -> 3 -> 12 ...

1. 35입력 비교할 부모 Node 값 없으무로 Root Node입니다.

2. 18 이 들어오고 부모노드인 35 와 비교 합니다. 작으면 왼쪽 크면 오른 쪽에 위치 시킵니다.

   18이 35보다 작으므로 왼쪽에 위치 시킵니다.

3. 68이 들어오면 가장 위에부터 35와 비교합니다. 35보다 크므로 오른쪽에 위치 시킵니다.

4. 7이 들어오면 35와 비교하고 작으므로 왼쪽으로 이동합니다 이미 그 위치에 18이 존제하므로 18이(부모노드)과 비교합니다. 7이 18보다 작으므로 18 왼쪽에 위치 시킵니다. 

 

위에 방법으로 입력 받은 값들을 위치 시킵니다. 

<2진 탐색 트리 검색>

최대값 : 트리의 오른쪽 노드의 최하단 값이 최대값이다. 재귀함수 수를 통해 구현 할 수 있다. Java 의 경우 함수를 실행 할때 Stack 구조로 로직을 처리하기때문에 아래 searchBST(), inorder() 함수 처럼 재귀함수를 사용하면 트리의 최하단 까지 검색이 가능하다.

 

탐색: 99

1. root node data 값을 비교한다. 99보다 작으(35)므로 오른쪽 노드로이동

2. 오른쪽 자식 노드 값을 비교한다. 99보다 작으(68)므로 오른쪽 노드로이동

3 오른쪽 자식 노드 값을 비교한다. 찾는값이므로 해당 node를 반환한다.

 

탐색: 22

1. root node data 값을 비교한다. 22보다 커서(35) 왼쪽 노드로이동

2. 왼쪽 자식 노드 값을(18) 비교한다. 22보다 작으(18)므로 오른쪽 노드로이동

3. 오른쪽 자식 노드 값을(26) 비교한다. 22보다 커서(26) 왼쪽 노드로이동

4. 찾는값이므로 해당 node를 반환한다.

<2진 트리 검색 Code>

Node 객체

public class TreeNode {
    char data;
    String nodeName;
    TreeNode left;
    TreeNode right;
    
    public TreeNode(){
        this.left = null;
        this.right = null;
    }
    
    public TreeNode(char data){
        this.data = data;
        this.left = null;
        this.right = null;
        setNodeName(data);
    }
    
    public Object getData(){
        return data;
    }
    
    public void setNodeName (char data) {
    	this.nodeName = data + " Node";
    }
    
    public String getNodeName () {
    	return this.nodeName;
    }
}

node 삽입, 검색

public class BinarySearchTree {
	int count = 0;
    private TreeNode root = null;
    
    public TreeNode getRootNode () {
    	return root;
    }
    
    public TreeNode insertKey(TreeNode root, char x) {
        TreeNode p = root;
        TreeNode newNode = new TreeNode(x);
        
        if(p==null){
        	System.out.println("test == : " + x);
            return newNode;
        }else if(p.data>newNode.data){
        	System.out.println("test << : " + p.getNodeName() + " : " + x);
            p.left = insertKey(p.left, x);
            return p;
        }else if(p.data<newNode.data){
        	System.out.println("test >> : " + p.getNodeName() + " : " + x);
            p.right = insertKey(p.right, x);
            return p;
        }else{ 
        	System.out.println("test3 : " + p.getNodeName() + " : " + x);
            return p;
        }
    }
    
    public void insertBST(char x){
        root = insertKey(root, x);
    }
    
    public TreeNode searchBST(char x){
        TreeNode p = root;
        while(p!=null){
            if(x<p.data) {
            	p = p.left;
            } else if(x>p.data) {
            	p = p.right;
            } else {
            	return p;
            }
        }
        return p;
    }
    
    public void inorder(TreeNode root){
    	count++;
        if(root!=null){
            inorder(root.left);
            System.out.print(root.data + " ");
            inorder(root.right);
        }
    }
    
    public void printBST(){
        inorder(root);
        System.out.println();
    }
    
    public static void main(String[] args) {
    	System.out.println("--------처리 동직----------");
    	BinarySearchTree bst = new BinarySearchTree();
    	bst.insertBST('A');
        bst.insertBST('D');
	    bst.insertBST('B');
	    bst.insertBST('C');
	    bst.insertBST('F');
        
	    System.out.println("-------------------------");
        bst.printBST();
        System.out.println("--------Root Node--------");
        System.out.println(bst.getRootNode().getNodeName());
        System.out.println("-----------검색-----------");	
        TreeNode p1 = bst.searchBST('F');
        if(p1!=null){
            System.out.println(p1.getNodeName() + " : " + p1.data + " 탐색 성공");
        }else{
            System.out.println("탐색 실패");
        }

    }
}

결과

--------처리 동직----------
test == : A
test >> : A Node : D
test == : D
test >> : A Node : B
test << : D Node : B
test == : B
test >> : A Node : C
test << : D Node : C
test >> : B Node : C
test == : C
test >> : A Node : F
test >> : D Node : F
test == : F
-------------------------
A B C D F 
--------Root Node--------
A Node
-----------검색-----------
F Node : F 탐색 성공

 

https://github.com/jkkim09/JAVA-BASE/tree/master/src/main/java/java_test/algorithm

jkkim09/JAVA-BASE