본문 바로가기
반응형

전체 글155

Tree Structure 노트7 - 2-3 Tree 높이균형트리 2-3 Tree 2-3 Tree는 내부노드의 차수가 2 또는 3인 균형 탐색트리이다. AVL 트리의 단점인 삽입과 삭제 시의 전체 트리를 재구성하는 부분을 최대한 줄이는 것이 핵심. - 노드 하나에 항목이 2개의 값이 있으며 링크는 3개가 있을 수 있음. - 노드 안에 항목의 수가 2개 있을 수 있고 각 항목은 크기대로 순서를 갖음. - 해당 노드가 가리키는 3개의 링크는 왼쪽부터 순서대로 링크 되어 있음. 단점 : 하나의 노드 안에 2개의 데이터가 모두 존재할 때 해당 노드를 분할하는 작업이 만만치 않음. 특징 : - 각 노드는 2개 이하의 항목과 3개 이하의 링크를 가짐. - 노드 안의 각 항목은 item1 2022. 4. 9.
Tree Structure 노트6 - AVL Tree 높이균형트리(Height balanced tree) AVL트리 AVL트리 : 스스로 균형을 잡는 이진 탐색 트리. 트리의 높이가 h일때 이진 탐색 트리의 시간 복잡도는 O(h). 한쪽으로 치우친 skewed tree가 되면 트리의 높이가 높아지기 때문에 이를 방지하고자 높이 균형을 유지하는 AVL트리 사용. -> self-organizing data structure. balance factor가 2이상 차이가 나면 작업. 특징 : AVL트리는 이진 탐색 트리의 속성을 가짐./ 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1./ 어떤 시점에서 높이 차이가 1보다 커지면 회전(rotation)을 통해 균형을 잡아 높이 차이를 줄임./ AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 삭제, 검색의 .. 2022. 4. 9.
Tree Structure 노트5 - K-ary Tree, Selection Tree K-ary 트리와 Selection 트리 k-ary tree : degree의 최대 수가 k인 tree를 의미함. 모든 노드가 n개를 초과하는 자식 노드를 가지지 않는 트리. n이 2이면 binary tree가 되고, 3이면 ternary tree가 됨. 특징 : 높이가 h인 k-ary tree는 최대 n의 h제곱-1의 노드를 가질 수 있음. 높이가 3인 binary tree의 노드는 최대 7개. 종류 : ㆍcomplete n-ary tree : 완전 트리. 마지막 level을 제외한 모든 level이 완전히 채워져 있고, 마지막 level의 모든 노드는 가능한 한 가장 왼쪽에 있는 tree. ㆍperfect n-ary tree : 포화 트리. leaf node를 제외한 모든 노드의 차수가 0이며, 모든.. 2022. 4. 8.
Legend Wraith https://play.google.com/store/apps/details?id=com.UndefinedMJ.LegendWraith Legend Wraith - Google Play 앱 스크린을 탭하여 비행하라! 장애물을 넘어 점수를 얻고 총알을 피하라! play.google.com 유니티로 만든 앱. play store에 올려봤음. score 만점따고 인증하면 만원드림. 2022. 4. 8.
디자인 패턴 - 커멘드 패턴 커멘드 패턴은 간단하게 말하면 호출 캡슐화 - 함수 호출을(명령, 메시지) 캡슐화 한 후에 대리자(invoker)를 통해서 간접적으로 명령을 실행시키는 방법. 재사용성이 높은 클래스를 설계하는 패턴. -이벤트가 발생했을때 실행될 기능이 다양하면서도 변경이 필요할 수 있을때 이벤트를 발생시키는 클래스를 변경하지 않고 재사용하고자 할때 유용함. (갈아끼우기쉬움 if문 없애기) -실행할 함수의 캡슐화로 Invoker 클래스와 Receiver 클래스 사이의 의존성을 제거함. => 실행될 기능의 변경에도 Invoker 클래스의 수정 없이 그대로 사용 가능. command 객체의 본질 : [receiver reference, method reference, argument reference]의 조합. Java의 r.. 2022. 4. 8.
Tree Structure 노트4 - 집합연산트리, Segment Tree 집합 연산(Set Operation)과 트리(Tree) Forest = a Union of { trees } 집합에 필요한 연산 ㆍUnion (x, y) - 원소 y를 포함하고 있는 Si를 원소 x를 포함하는 집합 Sj와 합친다. Si는 사라지고 Sj의 크기는 커진다. ㆍFind (x) - 원소 x가 S집합의 i번인 경우 집합의 index i를 출력. (원소를 포함한 집합을 find) Directed Rooted Tree를 이용한 집합(Set)의 표현 - union(3,5), union(2,4), union(5,7), find(7), union(10,13), find(9), union(3,10) ③ 2022. 4. 7.
반응형

티스토리툴바