[자료구조] Tree(트리)

자료구조 한 눈에 보기

선형 자료구조 (Linear)

• 선형 자료구조란 하나의 자료 뒤에 하나의 자료가 존재하는 것이다.
• 자료들 간의 앞뒤 관계가 1:1의 선형관계
• 배열과 리스트가 대표적이고 더 나아가서 스택, 큐도 이에 해당된다.

선형구조(Linear) 특징

• 가장 간단한 자료구조
• 접근 속도가 빠름
• 기억장소를 연속으로 배정받기 때문에 기억장소 이용 효율은 밀도가 1로서 가장 좋음
• 자료의 개수가 n개 일때, 삽입시 평균 이동 횟수 : n+1/2, 삭제시 평균 이동 횟수 : n-1/2
• 삽입, 삭제 시 자료의 이동이 필요하기 때문에 작업이 번거로움

선형구조는 언제 쓰이는가?

• 예시 : 4호선 지하철 노선도

• 선 하나에 데이터가 연결되어있는 것을 보면 알 수 있다.

코드로 이해하기

List<String> routeMap = new ArrayList<>();
        routeMap.add("서울역");
        routeMap.add("숙대입구");
        routeMap.add("삼각지");
        routeMap.add("신용산");
        routeMap.add("이촌");
        routeMap.add("동작");
        routeMap.add("총신대입구");
        routeMap.add("사당");

        for (String station : routeMap) {
            System.out.print(station + " -> ");
        }

        System.out.println("집");

비선형 자료구조 (NonLinear)

• 비선형 자료구조란 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 것이다.
• 자료들 간의 앞뒤 관계가 1:n, 또는 n:n 의 관계
• 트리와 그래프가 대표적이며 계층적 구조를 나타내기에 적절하다.

비선형구조 (NonLinear) 특징

• 방향성이 있음
• 각 노드는 어떤 자료형으로도 표현이 가능
• 사이클이 존재할 수 없다(하나의 연결 그래프)
• 트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등이 있음

비선형구조는 왜 필요할까?

• 예시 : 청와대 조직도
  

• 청와대 표를 보면 알 수 있다.
• 위에서 아래로 퍼져나가는 것을 보자.

어떻게 구현할 것인가?

List<List> newStructure = new ArrayList<>();
        newStructure.add(new ArrayList());

• 근데 이렇게 하면 될 것 같지만, 구현하기 불가능할정도로 어려워진다.
• 그래서 보통 배열안에 list를 만드는 방식을 사용한다.