๐ŸŒป JAVA/์•Œ๊ณ ๋ฆฌ์ฆ˜, ์ž๋ฃŒ๊ตฌ์กฐ

์ž๋ฃŒ๊ตฌ์กฐ - ์ด์ง„ํƒ์ƒ‰ ํŠธ๋ฆฌ (Binary-Search-Tree)

iseunghan 2020. 12. 21. 11:41
๋ฐ˜์‘ํ˜•

์ด์ง„ํƒ์ƒ‰ ํŠธ๋ฆฌ ๊ตฌ์กฐ


์ด์ง„ํƒ์ƒ‰ ํŠธ๋ฆฌ์˜ ์กฐ๊ฑด (์ด์ง„ ํŠธ๋ฆฌ์™€ ๋‹ค๋ฅด๋‹ค)

  • ๋ชจ๋“  ์›์†Œ๋Š” ์ค‘๋ณต๋œ ๊ฐ’์„ ๊ฐ€์ง€๋ฉด ์•ˆ๋œ๋‹ค.
  • ํŠธ๋ฆฌ์˜ ๋ฃจํŠธ๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์™ผ์ชฝ์— ์กด์žฌํ•˜๋Š” ๋…ธ๋“œ๋“ค์˜ ๊ฐ’์€ ๋ฃจํŠธ์˜ ๊ฐ’๋ณด๋‹ค ์ž‘์•„์•ผ ํ•œ๋‹ค.
  • ๋ฐ˜๋Œ€๋กœ ์˜ค๋ฅธ์ชฝ์— ์กด์žฌํ•˜๋Š” ๋…ธ๋“œ๋“ค์˜ ๊ฐ’์€ ๋ฃจํŠธ์˜ ๊ฐ’๋ณด๋‹ค ์ปค์•ผ ํ•œ๋‹ค.

 

์ด์ง„ํƒ์ƒ‰ ํŠธ๋ฆฌ์˜ ์‚ฝ์ž…

์œ„์— ์ด์ง„ํŠธ๋ฆฌ์˜ ์กฐ๊ฑด์„ ์ด์šฉํ•ด์„œ ์‚ฝ์ž…์„ ์œ„ ๊ทธ๋ฆผ ์ฒ˜๋Ÿผ ํ•ด์ฃผ๋ฉด ๋œ๋‹ค.

์‚ฝ์ž… ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ•ด ๋ณด๋ฉด,

public class BinaryTree {
    Node root;

    public void insertNode(int value) {
        /* root๊ฐ€ ๋น„์—ˆ์„ ๊ฒฝ์šฐ */
        if(root == null){
            root = new Node(value);
        }else {
            Node temp = this.root;

            while(true) {
                /* ์™ผ์ชฝ์œผ๋กœ ๊ฐ€์•ผ ํ•˜๋Š” ๊ฒฝ์šฐ */
                if(temp.value > value){
                    if(temp.left != null){
                        temp.left = new Node(value);
                        break;
                        }
                    temp = temp.left;
                }
                /* ์˜ค๋ฅธ์ชฝ์œผ๋กœ ๊ฐ€์•ผ ํ•˜๋Š” ๊ฒฝ์šฐ */
                else {
                    if(temp.right != null){
                        temp.right = new Node(value);
                        break;
                    }
                    temp = temp.right;
                }
            }
        }
    }
}

์ด์ง„ํƒ์ƒ‰ ํŠธ๋ฆฌ์˜ ์ˆœํšŒ ๋ฐฉ๋ฒ•

  • ์ „์œ„์ˆœํšŒ (Pre-order)
    • ๋ฃจํŠธ -> ์™ผ์ชฝ - > ์˜ค๋ฅธ์ชฝ
/* Pre-order (root - left - right) */
public void preOrderSearch(Node node) {
    if(node != null) {
        System.out.println(node.value + " -> ");
        preOrderSearch(node.left);
        preOrderSearch(node.right);
    }
}

 

A -> B -> D -> E -> C -> F -> G

 

  • ์ค‘์œ„์ˆœํšŒ (In-order)
    • ์™ผ์ชฝ -> ๋ฃจํŠธ -> ์˜ค๋ฅธ์ชฝ
/* In-order (left - root - right) */
public void inOrderSearch(Node node) {
    if(node != null) {
        inOrderSearch(node.left);
        System.out.println(node.value + " -> ");
        inOrderSearch(node.right);
    }
}

 

D -> B -> E -> A -> F -> C -> G

 

  • ํ›„์œ„์ˆœํšŒ (Post-order)
    • ์™ผ์ชฝ -> ์˜ค๋ฅธ์ชฝ - > ๋ฃจํŠธ
/* Post-order (left - right - root) */
public void postOrderSearch(Node node) {
    if(node != null) {
        postOrderSearch(node.left);
        postOrderSearch(node.right);
        System.out.println(node.value + " -> ");
    }
}

 

D -> E -> B -> F -> G -> C -> A

 

BFS - ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰, DFS - ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํ•ด๋‹น ํฌ์ŠคํŠธ๋ฅผ ์ฐธ๊ณ  ํ•˜์‹œ๊ธธ ๋ฐ”๋ž๋‹ˆ๋‹ค.

 

References


blog.naver.com/swoh1227/222175350122

k3068.tistory.com/30

๋ฐ˜์‘ํ˜•