Module 4 - BST Introduction

일단 tree 를 공부하기 전에 항상 물어야할 질문이 있다.

"왜 써야하는가?" 

tree 는 이 녀석들이 하지 못하던 searching 을 빠르게 만들어준다. 

한심한 녀석들...

 

root = 맨 꼭대기 의 수, tree 의 "왕"  

internal node = child 가 있는 node, <아이가 있는 엄마>

external nodes = child 가 없는 node (leaf 라고도 불린다) <미혼모>

root = 0 내려갈수록 1씩 증가

leaf = 0 후손이 생길때마다 1씩 증가

이번 시간에는 binary tree 안에 속해있는 Binary Search Trees 라는 귀여운 녀석이 있는데 이녀석을 탐구해볼 생각이다. 

binary search tree

줄여서 BST, 이녀석이 되려면 총 3가지 조건이 필요하다.

• 1. 자식이 둘까지만 가능하다. 3명 이상인 다자녀 집안은 취급하지 않는것 같다.
• 2. children은 left, right 로 label 되어야 한다. 
• 3. 왼쪽 child 가 오른쪽 child 보다 작아야 한다. 위계질서가 확실해야 하는 듯. 

Tree 종류들

• FULL TREE = 자녀 2 명 아님 0명 고정 
• COMPLETE TREE = 위에서부터 왼 => 오 로 훑을때 맨 마지막꺼 빼고 전부 채워져야함 
• DEGENERATE TREE = 쭈욱 자녀 1명 (4대독자 느낌) ( worst case tree 라고 많이 불림 사실 linked list 와 같다)

root 왼쪽 subtree 애들은 전부 root 보다 작아야 한다 vice versa

30 이 루트인 20 보다 커서 bst 가 안됨

binary search = 오른쪽 왼쪽으로 갈때마다 절반이 줄어드니 search 가 O(log n) 으로 빨라진다

물론 degenerate tree 는 O(n)이니 조심 

BST 는 linear data structure 이 아니라서 traversal algorithm 으로 만들어 줘야한다

• preorder
• inorder 
• postorder
• levelorder

preorder 

그림으로 구현하는법

node 확인후 왼쪽노드 recursion, 오른쪽 recursion

이해하기 쉽게 설명하면 동네 가게를 전부 털고싶은 도둑이 꼭대기 집부터 시작해서 왼쪽집 먼저 가고 왼쪽이 이미 방문한 집이면 오른쪽 집을 턴다고 생각하면 편하다. 여기서 아래집으로 털면서 내려가다가 빈집 = null 이 생기면 그 윗집으로 다시 return, 아랫집을 둘다 털었으면 그 윗집으로 또 return, 결국 원점인 꼭대기집으로 돌아와서 퇴근한다

구현: java 

public List<Integer> preorder() {
    List<Integer> list = new ArrayList<>();
    preorderHelper(root, list);
    return list;
}

private void preorderHelper(Node node, List<Integer> list) {
    if (node != null) {
        list.add(node.data);
        preorderHelper(node.left, list);
        preorderHelper(node.right, list); 
    }
}

postorder 

왼쪽 recursion, 오른쪽 recusion 끝나고 node 확인

preorder 과 차이라면 recursion 이후에 노드를 확인하는 것 하나

 

이해하기 쉽게 설명하자면 아까 빈집털이 예시로 이번엔 다 털고 return 해야만 할때 노드를 확인한다고 생각하면 편하다
recurse left, right 을 다 해보고 빈집이어야 윗집으로 return 하기 때문 

그림으로 구현

public List<Integer> postorder() {
        List<Integer> list = new ArrayList<>();
        postorderHelper(root, list);
        return list;
    }
    
    private void postorderHelper(Node node, List<Integer> list) {
        if (node != null) {
            postorderHelper(node.left, list);
            postorderHelper(node.right, list);
            list.add(node.data);
        }
    }

inorder

recursion left, right 사이에 노드 확인

왼쪽 노드를 확인하고 돌아올때 노드를 확인한다 

그림 구현

public List<Integer> inorder() {
        List<Integer> list = new ArrayList<>();
        inorderHelper(root, list);
        return list;
    }
    
    private void inorderHelper(Node node, List<Integer> list) {
        if (node != null) {
            inderHelper(node.left, list);
            list.add(node.data);
            inorderHelper(node.right, list);
            }
    }

levelorder = 위부터 왼=> 오 훑으면서

마트에서 계산할때 물건 놓는것처럼 queue 에 루트부터 왼-오 자식으로 돌면서 추가한다. 추가할때마다 queue 를 지우고 traversal 에 추가 (하나씩 계산해서 장바구니에 넣는 느낌)

그림 구현

    public List<T> levelorder() {
        List<T> lst = new ArrayList<T>();
        LinkedList<BSTNode<T>> items = new LinkedList<>();
        items.addLast(root);
        while (!items.isEmpty()) {
            BSTNode<T> node = items.removeFirst();
            if (node != null) {
                lst.add(node.getData());
                items.addLast(node.getLeft());
                items.addLast(node.getRight());
            }
        }
        return lst;
    }

언제 뭘 써야 되나요?

• Preorder: 
• Inorder: data 가 sort 되어 나옴 
• Postorder: 이 순서대로 data 를 지우면 항상 leaf 만 지울수 있게 됨  
• Levelorder: