[javascript] tree , 트리의 탐색 (2)

지난번 해시테이블 포스팅도 그렇고 이번 트리도 그렇고 꽤나 양이 방대해서 그런지 시리즈로 포스팅을 하고 있다. 나도 몰랐고 처음 해보는 자료구조들이라서 그런지 예제도 이해하는데 오래 걸리고 이를 토대로 다시 정리하는 것도 생각보다 오래 걸린다. ㅜ.ㅜ 으쌰 으쌰해야겠다. 

 

tree의 표현 방법

트리를 만드는 방법은 배열 혹은 연결리스트로 만드는 방법이 있다. 

 

 

배열로 표현하는 방법은 다음과 같다. 

 

임의의 노드 A의 부모노드 인덱스 .          : 해당 노드의 인덱스 i / 2;

임의의 노드 A의 왼쪽 자식노드 인덱스.    : 해당 노드의 인덱스 i * 2;

임의의 노드 A의 오른쪽 자식노드 인덱스. : 해당 노드의 인덱스 ( i * 2 ) +1 

 

배열로 트리를 만들게 되면 배열의 0번째 방은 사용하지 않는다. 그리고 배열로 만든 트리가 해당 배열의 size까지의 포화이진트리가 아닌 경우 메모리 공간의 낭비가 심하게 된다. 

 

연결리스트로 만든 트리는 노드 내부에 left LInk , right Link라는 필드에 다른 노드 메모리 주소를 가지고 있는 포인터를 저장하게 된다. 

이 포인터를 이용해서 새로운 노드가 필요할 때 마다 동적으로 노드를 만든다음 포인터를 저장만 하면 되기 때문에 배열에 비해서 유연하다는 장점이 있다. 

 

이진탐색트리

이진 탐색트리는 탐색을 쉽게 하기 위하여 각 노드들의 배치를 부모노드보다 클때와 작을때로 나눠 각각 왼쪽 혹은 오른쪽에 배치하는 트리를 말한다. 일상에서 생각해보면 책의 페이지를 찾기 위해서 중간을 펼쳐보고 해당 페이지보다 원하는 페이지번호가 작으면 왼쪽으로 이동하고 높다면 오른쪽을 펼치는 것이 이진탐색트리의 기본 메카니즘과 비슷하다. 

 

이 이진탐색트리를 이용해 데이터를 삽입하려면 이진트리의 탐색 방법에 대해서 먼저 알아야한다. 

 

이진트리의 탐색 방법은 대표적으로 3가지이며 탐색하는 인덱스의 해당 노드가 언제 검색되는지에 따라서 전위 , 중위 , 후위탐색으로 나뉜다. 

 

현재배열

constructor(){
         this.array = [null,20,11,30,8,14,25,38,4,null,null,null,null,null,null,42]
    }

 

 

중위탐색 

 

 inorder(i){
        if(i == null) i = 1;
        if(this.array[i] != null){
            this.inorder(i * 2)
            console.log(this.array[i]);
            this.inorder((i * 2) +1);
        }
        
    }

 

중위 탐색은 트리의 왼쪽 부터 깊게 들어갔다가 위로 올라오면서 부모노드를 찍고 오른쪽 노드를 다시 탐사하는 형태를 가진다. 

 

전위 탐색

    preorder(i){
        if(i == null) i = 1;
        if(this.array[i] != null){
            console.log(this.array[i]);
            this.preorder(i * 2)
            this.preorder((i * 2) +1);
        }
    }

전위 탐색은 edge를 타고 내려오자 마자 만나는 노드의 데이터를 훑고 왼쪽노드로 이동한다. 이 방식을 재귀적으로 반복한다. 

 

후위탐색

 postorder(i){
        if(i == null) i = 1;
        if(this.array[i] != null){   
            this.postorder(i * 2)
            this.postorder((i * 2) +1);
            console.log(this.array[i]);
        }
    }

후위 탐색은 자식노드가 있다면 왼쪽 노드들 부터 훑고 오른쪽 노드를 다 훑은 다음 부모노드를 확인한다.