[자료구조] 이진탐색트리, 바이너리서치트리(Binary Search Tree)[JAVA]

이진트리의 개념

위의 그림과같이 두개 이하의 자식노드를 가진 트리를 이진트리라고 한다.

 

이진탐색트리(Binary Search Tree)의 개념

위에서 설명한 이진트리와 바이너리서칭의 개념을 합친 트리 구조이다. 부모노드로부터 값이 큰 노드는 오른쪽, 값이 작은 노드는 왼쪽에 위치한다.

이진탐색트리

이진탐색트리의 특징으로 맨 오른쪽에 위치한 노드는 가장 큰 값을 가진 노드이며, 맨 왼쪽에 위치한 노드는 가장 작은 값을 가진 노드이다. 또한 값을 찾을때 바이너리서칭으로 찾을수 있기 때문에 평균적으로 O(log N)의 속도를 가진다.

 

 

하지만 그림과같이 트리가 구성되어있다면 이진탐색트리의 기능을 하지 못하게 된다. 

이진탐색트리의 구현

public class BinarySearchTree {
    Integer data;
    private BinarySearchTree left;
    private BinarySearchTree right;

    public BinarySearchTree getLeft()
    {
        return left;
    }
    public BinarySearchTree getRight()
    {
        return right;
    }
    public void SetLeft(BinarySearchTree node)
    {
        left = node;
    }
    public void SetRight(BinarySearchTree node)
    {
        right = node;
    }

    public void Insert(int val)
    {
        Search(val).data = val;
    }

    public BinarySearchTree Search(int val)
    {
        if(data == null)
            return this;

        if(data == val)
            return this;

        if(val > data)
        {
            if(right == null)
                right = new BinarySearchTree();
            return right.Search(val);
        }

        if(left == null)
            left = new BinarySearchTree();
        return left.Search(val);
    }

    public BinarySearchTree getBiggest()
    {
        BinarySearchTree temp = this;
        while(temp.right != null)
        {
            temp = temp.right;
        }

        if(temp.data == null)
            return null;
        return temp;
    }
    public BinarySearchTree getSmallest()
    {
        BinarySearchTree temp = this;
        while(temp.left != null)
        {
            temp = temp.left;
        }

        if(temp.data == null)
            return null;
        return temp;
    }

    public void Delete(int val)
    {
        BinarySearchTree temp = Search(val);
        if(temp.data == null)
            return;
        if(temp.left != null)
        {
            BinarySearchTree t2 = temp.left.getBiggest();
            temp.data = t2.data;
            t2.data = null;
        }
        else if(temp.right != null)
        {
            BinarySearchTree t2 = temp.right.getSmallest();
            temp.data = t2.data;
            t2.data = null;
        }
        else
            temp.data = null;
    }

    public void printInorder()
    {
        if(left != null)
            left.printInorder();
        System.out.print(this.data + " ");
        if(right != null)
            right.printInorder();
    }
    public void printPreOrder()
    {
        System.out.print(this.data + " ");
        if(left != null)
            left.printPreOrder();
        if(right != null)
            right.printPreOrder();
    }
    public void printPostOrder()
    {
        if(left != null)
            left.printPostOrder();
        if(right != null)
            right.printPostOrder();
        System.out.print(this.data + " ");
    }
}