[자료구조] 이진 탐색 트리 구현 | Java

📍이진 탐색 트리란?

이진 트리의 속성은 다음과 같다. 

 

1. 중복된 노드가 없어야한다. 

2. 모든 노드의 왼쪽 서브 트리에는 해당 노드보다 작은 값을 지닌 노드들로 이루어져 있다. 

3. 모든 노드의 오른쪽 서브 트리에는 해당 노드보다 큰 값을 지닌 노드들로 이루어져 있다. 

4. 중복된 노드가 없어야한다. 

5. 왼쪽 서브트리와 오른쪽 서브트리 또한 이진탐색트리이다. 

 

이진탐색트리의 단점

이진탐색트리의 삽입과 삭제 연산은 탐색이후 이루어지기 때문에

탐색에 필요한 O(h)이 소요되며 연결리스트를 사용하므로 입력과 삭제에는 O(1)이 사용된다.

따라서 총 소요되는 시간 복잡도는 O(h)이며 최악의 경우 탐색과 동일하게 O(N)이 소요된다.

다음과 같이 이진 탐색 트리는 한쪽 방향으로 노드가 집중된 편향트리에서는 효율적이지 않다.

 

이러한 단점을 보완하기 위해 Balance Tree를 이용하는데, B-Tree, AVL, Red-Black Tree 등이 있다.

 

 

Binary Search Tree visualization

https://www.cs.usfca.edu/~galles/visualization/BST.html

 

참고

https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/

---

📍코드 

 

Node.java

package tree;

public class Node implements TreePrinter.PrintableNode{
    Integer data;
    Node left;
    Node right;

    @Override
    public TreePrinter.PrintableNode getLeft() {
        return this.left;
    }

    @Override
    public TreePrinter.PrintableNode getRight() {
        return this.right;
    }

    @Override
    public String getText() {
        return "["+data+"]";
    }

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

 

BinarySearchTree.java

package tree;

public class BinarySearchTree {
    static final int COUNT = 10;
    Node root;
	
    //삽입 메소드 
    void add(Integer x){
        Node newNode = new Node(x);
		
        if(root == null) {
            root = newNode;
        }

        else{
            Node node = root;
            while(true){
                if(x > node.data) {
                    if(node.right == null) break;
                    node = node.right;
                }
                else if ( x < node.data) {
                    if(node.left == null) break;
                    node = node.left;
                }
            }
            if(x > node.data) node.right = newNode;
            else node.left = newNode;
        }
    }
    
	//삭제 메소드
	void remove(int x){
        Node current = root;
        Node node = root;
        while(current.data != x){
            if(x > current.data) {
                if(x == current.right.data) {
                    node = current.right;
                    break;
                }
                current = current.right;
            }
            else {
                if(x == current.left.data) {
                    node = current.left;
                    break;
                }
                current = current.left;
            }
        }
        System.out.println(current.data);
        System.out.println(node.data);

        if(node.left == null && node.right == null) {
            System.out.println("이 노드는 자식이 없음");
//            if(x > current.data)
        }
        else if (node.left != null && node.right != null){
            System.out.println("이 노드는 자식이 둘다 있음");
        }
        else {
            System.out.println("이 노드는 자식이 하나만 있음");
        }
    }
    
    //전위 순회 : 위-왼-오
    void preOrder(Node node){
        System.out.print(node.data + " ");
        if(node.left != null) {
            preOrder(node.left);
        }
        if(node.right != null){
            preOrder(node.right);
        }
    }

	//중위 순회: 왼-위-오
    void inOrder(Node node){
        if(node.left != null) inOrder(node.left);
        System.out.print(node.data + " ");
        if(node.right != null)inOrder(node.right);
    }
    
    //후위 순회: 왼-오-위
    void postOrder(Node node){
        if(node.left != null) postOrder(node.left);
        if(node.right != null)postOrder(node.right);
        System.out.print(node.data + " ");
    }
}

TreePrinter.java - 이진 트리 출력 코드

package tree;

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

public class TreePrinter
{
    /** Node that can be printed */
    public interface PrintableNode
    {
        /** Get left child */
        PrintableNode getLeft();


        /** Get right child */
        PrintableNode getRight();


        /** Get text to be printed */
        String getText();
    }


    /**
     * Print a tree
     *
     * @param root
     *            tree root node
     */
    public static void print(PrintableNode root)
    {
        List<List<String>> lines = new ArrayList<List<String>>();

        List<PrintableNode> level = new ArrayList<PrintableNode>();
        List<PrintableNode> next = new ArrayList<PrintableNode>();

        level.add(root);
        int nn = 1;

        int widest = 0;

        while (nn != 0) {
            List<String> line = new ArrayList<String>();

            nn = 0;

            for (PrintableNode n : level) {
                if (n == null) {
                    line.add(null);

                    next.add(null);
                    next.add(null);
                } else {
                    String aa = n.getText();
                    line.add(aa);
                    if (aa.length() > widest) widest = aa.length();

                    next.add(n.getLeft());
                    next.add(n.getRight());

                    if (n.getLeft() != null) nn++;
                    if (n.getRight() != null) nn++;
                }
            }

            if (widest % 2 == 1) widest++;

            lines.add(line);

            List<PrintableNode> tmp = level;
            level = next;
            next = tmp;
            next.clear();
        }

        int perpiece = lines.get(lines.size() - 1).size() * (widest + 4);
        for (int i = 0; i < lines.size(); i++) {
            List<String> line = lines.get(i);
            int hpw = (int) Math.floor(perpiece / 2f) - 1;

            if (i > 0) {
                for (int j = 0; j < line.size(); j++) {

                    // split node
                    char c = ' ';
                    if (j % 2 == 1) {
                        if (line.get(j - 1) != null) {
                            c = (line.get(j) != null) ? '┴' : '┘';
                        } else {
                            if (j < line.size() && line.get(j) != null) c = '└';
                        }
                    }
                    System.out.print(c);

                    // lines and spaces
                    if (line.get(j) == null) {
                        for (int k = 0; k < perpiece - 1; k++) {
                            System.out.print(" ");
                        }
                    } else {

                        for (int k = 0; k < hpw; k++) {
                            System.out.print(j % 2 == 0 ? " " : "─");
                        }
                        System.out.print(j % 2 == 0 ? "┌" : "┐");
                        for (int k = 0; k < hpw; k++) {
                            System.out.print(j % 2 == 0 ? "─" : " ");
                        }
                    }
                }
                System.out.println();
            }

            // print line of numbers
            for (int j = 0; j < line.size(); j++) {

                String f = line.get(j);
                if (f == null) f = "";
                int gap1 = (int) Math.ceil(perpiece / 2f - f.length() / 2f);
                int gap2 = (int) Math.floor(perpiece / 2f - f.length() / 2f);

                // a number
                for (int k = 0; k < gap1; k++) {
                    System.out.print(" ");
                }
                System.out.print(f);
                for (int k = 0; k < gap2; k++) {
                    System.out.print(" ");
                }
            }
            System.out.println();

            perpiece /= 2;
        }
    }
}

BinarySearchTreeMain.java

package tree;

public class BinarySearchTreeMain {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        bst.add(10);

        bst.add(5);

        bst.add(7);
        bst.add(29);
        bst.add(32);
        bst.add(31);
        TreePrinter.print(bst.root);

        bst.preOrder(bst.root);
        System.out.println();
        bst.inOrder(bst.root);
        System.out.println();
        bst.postOrder(bst.root);

        bst.remove(31);
    }
}

 

실행 결과