[Algorithm] BT (Binary Tree) & BST (Binary Search Trees)

BT (Binary Tree)

자료구조 중 이진 트리라는 것이 있다.

트리(Tree) 라는 명칭은 그 모양이 부모로부터 나무뿌리처럼 뻗어나가기 때문에 그렇게 생겼다고 느껴도 괜찮을 것이다.

이렇게 뿌리를 내리기 시작하는 최초의 부분을 루트라고 한다.

모든 트리구조는 바로 이 루트를 기준으로 뻗어나간다.

주로 객체들이 연결되어 있는데, 연결된 객체를 노드라고 한다.

어떻게 가든 결국 루트로 부터 선이 이어져있는 노드들은 루트의 자식이 된다.

새로운 노드(객체)에 연결하는 작업을 입력(insert)로 보고, 연결된 노드(객체)의 이어진 선을 잘라내는 작업을 삭제(delete)로 본다.

일반적은 트리는 일단 이렇다.

그런데 이진 트리는, 트리의 개념을 그대로 상속받은 특별한 트리이다.

일단 노드가 가질 수 있는 자식노드의 수가 두 개뿐이다.

(일반적인 이진트리)

자식 노드가 두개라고 해도 굳이 왼쪽이나 오른쪽으로 반드시 가득 차 있어야만 하는 것은 아니다.

(포화이진트리의 예)

자식이 있다면 무조건 둘 다 있고 아니면 하나도 없는 이진트리를 생각할 수 있다. 이런 트리를 포화이진트리라고 한다. 따라서 포화이진트리에서는 자식 수가 0아니면 2가 된다. 또, 루트를 기준으로 노드의 수가 왼쪽 서브트리, 오른쪽 서브트리 모두 같음을 알 수 있다.

(완전이진트리의 예)

이진트리에서, 왼쪽 자식노드부터 채워 모든 자식노드 수를 짝수로 채워나가는 이진트리를 완전이진트리라고 한다.

자식노드가 없으면 상관 없지만, 입력이 발생 한다면 왼쪽부터 챙겨주는 방식이다. 차곡차곡 모이면 포화이진트리 모양이 나올 수도 있다.

그러나 자식이 두개 있어도 된다고 했지, 꼭 자식노드가 두개씩 있을 필요는 없다고 미리 이야기했다. 자식이 오로지 단 하나씩만 갖는 이진트리를 생각할 수 있다. 그 중에서도 왼쪽 혹은 오른쪽으로만 자식이 있는 트리를 편향이진트리라고 한다. 자식이 단 하나씩 있는 트리는 솔직히 트리의 구조를 계속 유지할 이유가 없다. 왜냐하면, 루트에서 시작하여 연결된 노드들의 모습이 연결리스트(Linked-List)와 다르지 않다. 

BST (Binary Search Tree)

이진 트리의 검색과 관련하여 Hackerrank 의 풀이를 공유한다.

       int getHeight(Node* root){

            Node* next = NULL;

            int leftH, rightH;

            leftH = rightH = 0;

            

            next = root;

            while( next != NULL){

                next = (next->left == NULL ? next->right : next->left);     // 좌측 지향 검색

                leftH++;

            }

            next = root;

            while( next != NULL){

                next = (next->right == NULL ? next->left : next->right);    // 우측 지향 검색

                rightH++;

            }

            

            return ( leftH > rightH ? leftH : rightH ) - 1; // root 제외

        }

참고

BST 문제 해커랭크 : hackerrank : 30 days of code : 22

삼성소프트웨어맴버쉽 이진트리편 : http://secmem.tistory.com/204