Tree

트리를 알아보자,,

우선 트리하면 대표적인게 컴퓨터의 File System.

이외에 HTML Tag구조, 도-시군구-읍면동 주소체계, DBMS, 라우터 통신 알고리즘, 검색엔진에 사용된다.

트리는 아래로만 흐르는 방향그래프(Directed Graph)이다. 만약 그런 제약이 없다면 그래프.

 

Binary Tree

이진트리는 자식의 갯수가 무조건 두개로 고정되어있다.

*모든 노드가 2개의 서브트리를 갖고 있음.

*공집합도 이진트리임.

일반 트리와 이진 트리의 차이점

1) 이진트리의 모든 노드는 차수가 2 이하, 즉 자식 노드의 갯수가 2 이하. 일반 트리는 자식 노드의 갯수 제한 없음.

2) 일반 트리와 달리 이진트리는 노드를 하나도 갖지 않을 수도 있음.

3) 서브트리간 순서가 존재함. : 왼쪽 서브트리, 오른쪽 서브트리를 구별함.

 

이진트리는 포화 이진트리(full binary tree), 완전 이진트리(complete binary tree), 편향 이진트리(한쪽으로만 뻗은 것)

 

Perfect Binary Tree(포화 이진 트리)

: 모든 level이 꽉 찬 이진트리. 완전이진트리이기도 하다.

 

Full Binary Tree(정 이진 트리)

: 모든 노드가 0 or 2개의 자식노드만 갖는 이진트리

 

Complate Binary Tree(완전 이진 트리)

: 왼쪽에서 오른쪽 순서로 채워진 이진트리

---

이진트리 순회 방법엔 전위,중위,후위가 있다.

 

1)전위

2)중위

 

3)후위

 

트리 전위,순위,후위 구현.

(참고한 영상 : https://youtu.be/TohdsR58i3Q )

class Node{
    int data;
    Node left;
    Node right;
}
 
class Tree{
    public Node root;
 
    public void setRoot(Node node){
        this.root=node;
    }
    public Node getRoot(){
        return root;
    }
    public Node makeNode(Node left, int data, Node right){
        Node node = new Node();
        node.data = data;
        node.left = left;
        node.right = right;
        return node;
    }
 
    //왼쪽, 자신, 오른쪽 순서 (중위 순회)
    public void inorder(Node node){
        if(node!=null){
            inorder(node.left);
            System.out.println(node.data);
            inorder(node.right);
        }
    }
 
    //자신, 왼쪽, 오른쪽 순서 (전위 순회)
    public void preorder(Node node){
        if(node!=null){
            System.out.println(node.data);
            preorder(node.left);
            preorder(node.right);
        }
    }
 
    //왼쪽, 오른쪽, 자신 순서 (후위 순회)
    public void postorder(Node node){
        if(node!=null){
            postorder(node.left);
            postorder(node.right);
            System.out.println(node.data);
        }
    }
}
public class Main {
 
    public static void main(String[] args) {
 
        //Tree 생성성
       Tree t= new Tree();
        Node n4 = t.makeNode(null,4,null);
        Node n5 = t.makeNode(null,5,null);
        Node n2 = t.makeNode(n4,2,n5);
        Node n3 = t.makeNode(null,3,null);
        Node n1 = t.makeNode(n2,1,n3);
 
        //루트 지정
        t.setRoot(n1);
 
        //출력
        t.inorder(t.getRoot());
        t.preorder(t.getRoot());
        t.postorder(t.getRoot());
    }
}
 

 

BST(Binary Search Tree)

이진트리의 일종. 완전이진트리가 아님! 중위순회한다. 

1. 키가 유니크 해야함.

2. 부모의 키가 왼쪽자식 노드의 키보다 커야함.

3. 부모의 키가 오른쪽 자식 노드의 키보다 작아야함.

4. 왼쪽, 오른쪽 서브트리도 BST이다.

O(log n)의 탐색 연산 시간복잡도 가짐. --> 정확히는 O(h). 트리의 높이를 더할수록 추가할 수 있는 노드 수가 두배씩 증가하기 때문.

한쪽으로 쏠린 편향트리가 될 수 있는데(불균형 이진트리), 성능에 영향을 미치고 O(n)이 될 수 있음.

 

BST구현 (참고영상 : https://youtu.be/Y9Ar9eerxQU )

//정렬된 고유한 정수로만 이뤄진 배열로 이진 검색트리를 구현해보기
//중간 값을 계속 찾아 반을 잘라가면서 구현함.
//한번 이동할 때마다 찾아야하는 데이터가 절반씩 줄어들어 O(lon n)시간복잡도 가짐.
//반을 자르고 확인하는 반복적인 일이 일어나므로, 재귀적으로 구현한다.
//1.Tree로 만들 데이터가 들어있는 Array
//2.해당그룹이 시작하는 index, 끝나는 index
class Tree{
    class Node {
        int data;
        Node left;
        Node right;
 
        Node(int data) {
            this.data = data;
        }
    }
        Node root; //tree가 시작되는 root Node
        //배열정보 받아서 Tree만드는 일을 시작해주는 메서드
        public void makeTree(int[] a){
            //재귀호출 실행하기 전 재귀호출에 필요한 데이터 처음으로 던져주는 일 함.
            //재귀 끝나면 root노드의 주소를 받아 맴버변수에 저장
            root = makeTreeR(a,0,a.length-1);
        }
 
        //배열정보, 시작index, 끝index
        public Node makeTreeR(int []a, int start, int end){
            if(start>end) return null;
            int mid = (start+end)/2;
            Node node = new Node(a[mid]);
            node.left = makeTreeR(a,start,mid-1);
            node.right = makeTreeR(a, mid+1,end);
            return node;
        }
 
        //Tree 잘 만들어졌는지 확인하는 이진검색트리 구현
        public void searchBTree(Node n, int find){
            if(find<n.data){
                System.out.println("Data is smaller than "+n.data);
                searchBTree(n.left,find);
            }
            else if(find>n.data){
                System.out.println("Data is bigger than " + n.data);
                searchBTree(n.right,find);
            }
            else{
                System.out.println("Data found!");
            }
        }
}
 
 
 
public class Main {
    public static void main(String[] args) {
        int[] a = new int[10];
        for(int i=0;i<a.length;i++){
            a[i]=i;
        }
        Tree t = new Tree();
        t.makeTree(a);
        t.searchBTree(t.root,2);
    }
}
 

 

 

Tree의 Balance확인하기

(참고영상 : https://youtu.be/zhhxBrtaOO0 )

//주어진 이진트리의 Balaance가 맞는지 확인하는 함수 구현
//(여기서 Balance가 맞다는 의미는 어떤 노드의 양쪽 서브트리의 길이가 1이상 차이 나지 않는 것을 뜻함)
//양쪽 노드에 가장 긴 줄기만 비교해서 결정하자고 판단한 경우
 
class Tree{
    class Node{
        int data;
        Node left;
        Node right;
        Node (int data) {
            this.data = data;
        }
    }
 
    Node root;
    Tree(int size){
        root = makeBST(0,size-1);
        //unbalance test
        root.right.right.right.right = new Node(10);
        root.right.right.left = new Node(11);
    }
 
    Node makeBST(int start, int end){
        if(start>end) return null;
        int mid = (start + end) / 2;
        Node node = new Node(mid);
        node.left = makeBST(start,mid-1);
        node.right=makeBST(mid+1,end);
        return node;
    }
    boolean isBalanced(Node root){
        //마지막 노드를 지났으면 true 반환
        if(root == null) return true;
 
        //양쪽 서브트리의 길이를 받아서 차이 계산
        int heightDiff = getHeight(root.left) - getHeight(root.right);
 
        //1이상 차이나면
        if(Math.abs(heightDiff)>1){
            return false;
        }
        //왼쪽과 오른쪽이 둘 다 발란스가 맞는지 맞는 경우에만 true리턴.
        //tree의 마지막 노드에서 true를 반환하기 때문에, 위에서 1이상 차이가 나지 않는 한 false는 없음.
        else{
            return isBalanced(root.left) && isBalanced(root.right);
        }
    }
 
    //노드를 던지면, 해당 노드를 root로 이하 서브트리의 가장 긴 줄기의 레벨이 몇인지 알아보는 함수
    //O(N log n)의 시간복잡도를 가짐. 노드가 호출 될 때마다 매번 다시 가서 길이를 재니까!
    int getHeight(Node root){
        //tree 마지막 노드를 지났으면 level count에서 1을 빼준다.
        if(root == null) return -1;
 
        //그렇지 않으면 왼,오 child노드들을 반복적으로 호출하면서 둘중 더 긴 줄기를 선택하고,
        //거기에 1을 더해서 반환.
        //반환할 때 1을 더하면 함수가 벗겨질 때마다 level이 하나씩 증가하면서 세나가는 구조.
        return Math.max(getHeight(root.left), getHeight(root.right)) +1;
    }
 
 
    //노드를 돌면서 동시에 길이를 재는 방식으로 구현
    //정수의 가장 작은 값을 반환한다면 false라고 가정!
    //한번씩만 방문하면 되므로 O(N)으로 시간이 줄어든다.
 
    //길이를 재는 함수
    int checkHeight(Node root){
        if(root == null) return -1; //레벨에서 하나 빼줌
        //왼쪽 노드를 돌면서 서브트리의 길이 잼
        int leftHeight = checkHeight(root.left);
        //받은 결과값이 정수값중 가장 작으면 비교할 필요 없이 바로 false반환.
        if(leftHeight == Integer.MIN_VALUE) return Integer.MIN_VALUE;
 
        //오른쪽 노드 돌면서 서브트리의 길이 잼
        int rightHeight = checkHeight(root.right);
        if(rightHeight==Integer.MIN_VALUE) return Integer.MIN_VALUE;
 
        //양쪽 서브트리의 가장 긴 줄기 값을 비교한다
        int heightDiff = leftHeight - rightHeight;
        if(Math.abs(heightDiff)>1){
            return Integer.MIN_VALUE;
        } else{
            //두개 길이 중 큰 값에 1을 더해서 반환.
            //재귀호출을 맨 끝에서 한꺼풀 벗겨질 때마다 1씩 더하여 길이로 사용
            return Math.max(leftHeight, rightHeight) +1;
        }
    }
 
    //재귀함수 호출해줄 함수 선언
    boolean isBalanced2 (Node root){
        return checkHeight(root) != Integer.MIN_VALUE;
    }
 
 
    class Level{
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
    }
    //재귀함수 호출
    boolean isBalanced3(Node root){
        Level obj = new Level();
 
        //시작노드, 저장할 obj
        checkBalanced(root,obj,0);
        //가장 작은 서브트리의 길이와, 가장 긴 서브트리의 길이를 비교하고 1 이상이면 false(unbalance)
        if(Math.abs(obj.min - obj.max)>1) return false;
        else return true;
    }
 
    void checkBalanced(Node node, Level obj, int level){
        if(node==null){
            if(level<obj.min) obj.min = level;
            else if(level>obj.max) obj.max = level;
            return;
        }
        checkBalanced(node.left, obj, level+1);
        checkBalanced(node.right, obj, level+1);
    }
}
 
 
public class Main {
    public static void main(String[] args) {
        //10개의 노드를 가진 이진트리
        Tree t = new Tree(10);
 
        //기준 노드의 왼쪽, 오른쪽의 가장 긴 서브트리의 길이로만 비교
        System.out.println(t.isBalanced(t.root));
        System.out.println(t.isBalanced2(t.root));
 
        //가장 짧은, 가장 긴 길이를 비교교
       System.out.println(t.isBalanced3(t.root));
    }
}
 

 

 

 

BST의 효율을 높이기 위해서는 불균형트리를 완전이진트리와 같이 균형트리로 바꾸어주어야 하는데,

대표적으로 AVL트리, B-트리가 있다.

 

AVLTree는 Red-Black Tree는 다음에,,,

B-Tree는 자식노드가 2개 이상인 트리이다.

hyungjoon6876.github.io/jlog/2018/07/20/btree.html

참고하면 좋은 블로그!