[4.2] Binary Search Tree 복습

1. 삽입 및 검색 연산 구현, 검증

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study03
{
    public class Node
    {
        public int data;
        public Node left;
        public Node right;
        public Node(int data)
        {
            this.data = data;
        }
    }
    public class BST
    {
        private Node root;
        public BST()
        {

        }

        public void Add(int data)
        {
            if (root == null)
            {
                root = new Node(data);
            }
            else
            {
                Node node = root;
                while (node != null)
                {
                    //node의 데이터와 인자로 들어온 데이터 비교
                    int comp = data.CompareTo(node.data);
                    if (comp == 0)          //같을때
                    {
                        return;
                    }
                    else if (comp == 1)     //인자 data가 더 클때
                    {
                        if (node.right == null)     //node의 오른쪽 자식이 비어있으면 삽입 후 종료
                        {
                            node.right = new Node(data);
                            break;
                        }
                        node = node.right;
                    }
                    else                        //인자 data가 더 작을때
                    {
                        if (node.left == null)  //node의 왼쪽 자식이 비어있으면 삽입 후 종료
                        {
                            node.left = new Node(data);
                            break;
                        }
                        node = node.right;
                    }
                }
            }
        }

        public bool Search(int data)
        {
            Node node = root;
            while (node != null)
            {
                int comp = data.CompareTo(node.data);
                if (comp == 0)
                {
                    return true;
                }
                node = comp > 0 ? node.right : node.left;
            }
            return false;
        }

        public bool Remove(int data)
        {
            return false;
        }
    }
}

using System;

namespace Study03
{
    public class App
    {
        public App()
        {
            BST tree = new BST();
            tree.Add(30);
            tree.Add(25);
            tree.Add(35);
            tree.Add(21);
            tree.Add(27);
            tree.Add(32);

            var target = 25;
            Console.WriteLine("Target: {0}", target);
            var result = tree.Search(target);
            Console.WriteLine("Result: {0}", result);

            target = 50;
            Console.WriteLine("Target: {0}", target);
            result = tree.Search(target);
            Console.WriteLine("Result: {0}", result);
        }
    }
}

 

2. 삭제연산 구현 및 검증

public bool Remove(int data)
{
    Node node = this.root;
    Node prev = null;

    //삭제할 노드를 찾음
    while (node != null)
    {
        int cmp = data.CompareTo(node.data);
        if (cmp == 0)
        {
            break;
        }
        else if (cmp < 0)
        {
            prev = node;
            node = node.left;
        }
        else
        {
            prev = node;
            node = node.right;
        }
    }

    if (node == null) return false;

    if (node.left == null && node.right == null)
    {
        //자식이 없는 경우
        if (prev.left == node)
        {
            prev.left = null;
        }
        else
        {
            prev.right = null;
        }
        return true;
    }
    else if (node.left == null || node.right == null)
    {
        //자식이 하나 있는 경우
        //삭제하려는 노드의 자식이 어느쪽에 있는지 확인
        var child = node.left ?? node.right;

        //삭제하려는 노드가 부모의 어느쪽에 달려있는지 체크하고 노드의 자식을 부모에 직접 연결 후 삭제
        if (prev.left == node)
        {
            prev.left = child;
        }
        else
        {
            prev.right = child;
        }
    }
    else
    {
        //자식이 두 개 있는 경우 (Prev없이 구현해봄)
        //오른쪽 서브트리에서 가장 작은 값을 찾아서 삭제할 노드에 데이터 복사
        //(오른쪽 서브트리에서 가장 작은 값은 삭제하려는 값과 제일 근접하다 = 복사 후 대입시켜도 트리의 구조를 변화시키지 않음)
        //(왼쪽 서브트리를 이용하려면 왼쪽 서브트리의 제일 오른쪽 값을 이용하면 됨)
        Node min = node.right;  //오른쪽 서브트리의 루트

        while (min.left != null)
        {
            min = min.left;
        }
        var temp = min.data;

        //오른쪽 서브트리의 맨 왼쪽 노드를 삭제
        //min은 무조건 자식이 없거나 하나임. 그러므로 함수 재활용가능
        this.Remove(min.data);
        node.data = temp;
        return true;
    }

    return false;
}

• 자식이 2개가 있는 노드를 제거할 때, min 값을 찾고 다시 Remove(min.data)를 호출한 이유는 우리가 찾은 min 노드는 무조건 if ~ else if를 통과한 것에 해당된다. 그래서 다시 코드를 짤 필요없이 min.data 자체를 다시 함수를 돌리면 된다. 대신 시간이 좀 더 걸린다.
• prev변수를 사용하면 메모리, 시간측에서 더 유리하지만 코드짜기가 귀찮다. Remove(int data) 재호출은 코드의 재사용성을 높인다.