[TIL] DAY80_iOS_Making a VendingMachineApp(2),자료구조(Tree)
- 2 mins
DAY80
Making a VendingMachineApp(2)
IBOutlet Collection 기능에 대해 학습하고 중복되는 아웃렛을 제거한다.
중복되는 요소들 중 하나를 View Controller로 끌어서 IBOutletCollection 만듦
만든 IBOutletCollection 옆의 동그라미(+) 버튼을 Main.storyboard의 중복되는 요소들로 드래그하여 UI 객체배열 완성
각 요소를 구분하기 위한 tag 부여
IBAction을 하나 만들어서 각 요소와 연결
IBAction 내에서 IBOutletCollection으로 만든 배열 사용
UIImageView 에서 이미지를 표시할 때 사각형 코너를 둥글게하도록 변경해본다.
Identity Inspector > User Defined Runtime Attributes에 키 추가 :
테두리: layer.borderWidth (Number)
테두리색상: layer.borderUIColor (Color)
둥근테두리: layer.cornerRadius (Number)
자료구조(3/7)
Tree
트리란? 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조 로, 계층적 관계(Hierarchical Relationship)을 표현하는 자료구조이다.
트리의 구성요소
노드(Node) : 트리를 구성하는 각각의 요소
간선(Edge) : 트리를 구성하기 위해 노드와 노드를 연결하는 선
루트 노드(Root Node) : 트리 구조에서 최상위에 있는 노드
단말 노드(Terminal Node( = leaf Node)) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다.
비단말 노드(Internal Node (내부노드)) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.
Binary Tree(이진트리)
이진트리에서 각 층별로 숫자를 매기는 데 이것을 해당 층의 레벨(Level)이라고 한다.
레벨은 0부터 시작하고 루트 노드의 레벨은 0이다
트리의 가장 최고레벨을 높이(height)라고 한다.
포화 이진 트리(Full Binary Tree)와 완전 이진 트리(Complete Binary Tree)
포화 이진 트리 : 모든 레벨이 꽉 찬 트리
완전 이진 트리 : 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리
노드의 개수가 n개 일 때, i번째 노드에 대해서 parent(i) = i/2 , left_child(i) = 2i , right_child(i) = 2i + 1 의 index 값을 갖는다.
이진탐색트리(BST, Binary Search Tree)
효율적인 탐색을 위해서는 어떻게 찾을까만 고민해서는 안된다. 그보다는 효율적인 탐색을 위한 저장방법이 무엇일까를 고민해야 한다. 이진 탐색 트리는 이진 트리의 일종이다. 단 이진 탐색 트리에는 데이터를 저장하는 규칙이 있다. 그리고 그 규칙은 특정 데이터의 위치를 찾는데 사용할 수 있다.
규칙
이진 탐색 트리의 노드에 저장된 키는 유일하다.
루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.
루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.
왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.
이진 탐색 트리의 탐색 연산은 O(log n)의 시간 복잡도 를 갖는다. 사실 정확히 말하면 O(h)라고 표현하는 것이 맞다. 트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두 배씩 증가하기 때문이다. 하지만 이러한 이진 탐색 트리는 Skewed Tree(편향 트리)가 될 수 있다. 저장 순서에 따라 계속 한 쪽으로만 노드가 추가되는 경우가 발생하기 때문이다. 이럴 경우 성능에 영향을 미치게 되며, 탐색의 Worst Case가 되고 시간 복잡도는 O(n) 이 된다.
배열보다 많은 메모리를 사용하며 데이터를 저장했지만 탐색에 필요한 시간 복잡도가 같게 되는 비효율적인 상황이 발생한다. 이를 해결하기 위해 Rebalancing 기법이 등장하였다. 균형을 잡기 위한 트리 구조의 재조정을 Rebalancing이라 한다. 이 기법을 구현한 트리에는 여러 종류가 존재하는데 그 중에서 하나가 Red-Black Tree이다.
