[hackerrank] hackerrank challenges Day 22 자바 강의 리뷰

 

 

해커랭크 Day 22 챌린지를 시작해보자. 😊

 

오늘은 Binary Serarch Tree(이진 탐색 트리)에 대해 학습했다.

 

이진 탐색 트리에 대해 잘 모르는 독자들은

필자의 이전 포스팅에서

자세히 다루고 있으니 참고하길 바란다.

 

(포스팅 보러 가기)

 

 

 

필자도 이진 탐색 트리의 개념이 헷갈려

강의를 보고 이해가 되지 않아

위 포스팅을 작성하면서 공부하고나니

코드 이해가 훨씬 쉬웠다!!

 

그럼 소스코드를 확인해보자.

 

---

 

public interface Tree<D extends Comparable> {
    public boolean isEmpty();

    public int cardinality();

    public boolean member(D elt);

    public NonEmptyBST<D> add(D elt);

}

Tree interface

 

 

public class EmptyBST<D extends Comparable> implements Tree<D> {

    public EmptyBST() {

    }

    @Override
    public boolean isEmpty() {
        return true;
    }

    @Override
    public int cardinality() {
        return 0;
    }

    @Override
    public boolean member(D elt) {
        return false;
    }

    @Override
    public NonEmptyBST<D> add(D elt) {
        return new NonEmptyBST<D>(elt);
    }
}

EmptyBST.java

 

 

class NonEmptyBST<D extends Comparable> implements Tree<D> {
    D data;
    Tree<D> left;
    Tree<D> right;


    public NonEmptyBST(D elt) {
        data = elt;
        left = new EmptyBST<D>();
        right = new EmptyBST<D>();
    }

    public NonEmptyBST(D elt, Tree<D> leftTree, Tree<D> rightTree) {
        data = elt;
        left = leftTree;
        right = rightTree;
    }

    public boolean isEmpty() {
        return false;
    }

    public int cardinality() {
        return 1 + left.cardinality() + right.cardinality();
    }

    public boolean member(D elt) {
        if(data == elt) {
            return true;
        } else {
            if(elt.compareTo(data) < 0) {
                return left.member(elt);
            } else {
                return right.member(elt);
            }
        }
    }

    public NonEmptyBST<D> add(D elt) {
        if(data == elt) {
            return this;
        } else {
            if(elt.compareTo(data) < 0) {
                return new NonEmptyBST(data, left.add(elt), right);
            } else {
                return new NonEmptyBST(data, left, right.add(elt));
            }
        }
    }
}

NonEmptyBST.java

 

 

 

위의 이진 탐색 트리 포스팅을 읽고

강의를 듣거나 소스코드를 참고한다면

딱히 어려운 부분은 없을 것인데

 

필자는 caldinality() 부분이 헷갈렸어서

조금 추가 설명하고자 한다.

 

우선 필자가 헷갈렸던 코드부터 살펴보자.

 

public int cardinality() {
    return 1 + left.cardinality() + right.cardinality();
}

 

필자는 왜 cardinality()를 구하는데

1 + left.cardinality() + right.cardinality()의 공식이 필요한지 이해가 되지 않았다.

 

그래서 강의에서 설명하는 부분을 잘 살펴보니

이유는 다음과 같았다.

 

cardinality() 설명

 

강의 설명으로도 한 번에 이해되지 않아

나름(?) 쉽게 설명한다고 설명한 건데

이해가 될지 모르겠다.

 

만약 위 그림을 보고도 이해가 되지 않는 부분이 있다면

댓글을 남겨주면

필자가 다시 설명해주겠다!!

 

---

 

그럼 우리는 다음 포스팅에서

소스 코드 리뷰로 다시 만나자. 😊