Knowledge/Data Structure (6) 썸네일형 리스트형 이진 탐색 트리 (Binary Search Tree) 이진 탐색 트리탐색을 위한 자료구조로 저장할 데이터의 크기에 따라 위치를 정의한 것이다.트리 자료 구조의 자료 중 하나로, 각 노드가 2개의 자식 노드를 가질 수 있는 트리이다. ※ 효율적인 탐색 작업을 하기 위해 이진 탐색 트리를 다음과 같이 정의한다.모든 원소는 서로 다른 유일한 키를 갖는다.왼쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 작다.오른쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 크다.좌우 하위 트리도 각각 이진 탐색 트리 구조이다. 이러한 특징때문에 이진 탐색 트리를 중위 순회로 순회하게 되면, 정렬된 값을 읽을 수 있다. 이진 탐색 트리는 왜 중복노드를 가져서는 안될까?이진 탐색 트리는 매우 직관적이고 단순한 검색 알고리즘을 가지고 있다. 이진 탐색 트리 탐색탐색은 항상 .. Stack(스택)과 Queue(큐) 스택(Stack)이란? 스택은 데이터가 들어온 순서대로 차곡차곡 쌓이는 형태의 기억공간을 말한다.출력 시 가장 나중에 쌓인 데이터가 제일 먼저 출력을 하게 된다.그러므로 스택을 선입후출 혹은 LIFO(Last In First Out)이라고도 부른다 스택에서는 TOP, POP, PUSH라는 용어를 사용한다. TOP이란 스택의 맨 위의 데이터인 즉, 최근에 들어온 데이터를 가리키는 화살표라고 생각하면 된다.데이터가 입/출력이 되면 이 TOP이란 화살표는 움직이면서 스택안에서 데이터가 최대 몇개가 저장되어있는지 알 수가 있다. POP이란 스택에 있는 데이터를 이용해 연산을 할 때에 데이터를 삭제하기 위한 것이다. PUSH란 데이터를 삽입하기 위한 것이다. TOP이 다음 데이터가 돌아올 자리로 이동하면 그 자리.. 자료구조와 자료구조를 결정하는 방법 자료구조 (data structure)전산학에서 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법이다.신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다. 프로그램을 설계할 때, 어떠한 자료구조를 선택할지는 가장 우선적으로 고려되어야 한다.자료구조에는 여러 종류가 있으며, 이러한 각각의 자료구조는 각자의 연산 및 목적에 맞추어져 있다. 자바에서는 기본적인 자료구조를 제공하는데 이러한 자료구조를 제공하기 위한 환경을Java Collection Framework라고 한다. Java Collection Framework의 기본 상속구조는 다음과 같다. 그렇다면 자료구조를 결정할 때 고려해야할 사항들은 무엇이 있을까?고려해야하는 사항들은 때에 따라 많겠지만 기본적으로 살펴보면데이터들.. Set (HashSet, TreeSet) Set 순서가 없고 집합이므로 중복된 데이터가 들어갈 수 없다.중복되지 않은 데이터를 구할 때 유용하다. ※ HashSet가장 빠른 임의 접근속도순서를 전혀 예측할 수 없다.HashSet hs = new HashSet(); ※ TreeSet정렬된 순서대로 저장하며 정렬 방법을 지정할 수 있다.TreeSet ts = new TreeSet(); List (ArrayList, LinkedList, Vector) 리스트 (List) 순열(sequence)라고도 불리며, 순서를 가지고 일렬로 나열한 원소들의 모임이다.순서가 있다는 점에서 집합과는 구별되며, 갈림길 없이 일렬로 나열되어 처음과 끝이 각각하나씩만 있다는 점에서 트리나 그래프와도 구별된다. 》》 저장공간이 정해져있지 않으므로 필요에 의해 자동으로 늘어난다.》》 중복이 있고, 순서가 있다. 자바에서는 List자료구조를 크게 ArrayList, LinkedList, Vector 로 세분화할 수 있다. ※ ArrayList객체 내부에 있는 배열에 데이터를 저장한다.ArrayList arraylist = new ArrayList(); 》》 ArrayList 정렬Collections.sort(this); // 올림차순Collections.sort(this, Co.. Map (HashMap, Hashtable, TreeMap) Map 이진 탐색 트리를 기반으로 두개의 자료형을 동시에 저장하도록 만든 자료구조이다. List와 Set이 순서나 집합적인 개념의 인터페이스라면 Map은 검색의 개념이 가미된 인터페이스이다.Map 인터페이스는 데이터를 삽입할 때 Key와 Value의 형태로 삽입되며, Key를 이용해서 Value를 얻을 수 있다. ※HashMapHashMap은 Map 인터페이스를 구현한 클래스로서 중복을 허용하지 않는다. Map의 특징인 Key와 Value의쌍으로 이루어져있다.Map hashmap = new HashMap(); ※HashtableHashMap과 동기화를 보장하냐 안하냐의 차이외에는 거의 동일한 자료구조라고 볼 수 있다.Hashtable hashtable = new Hashtable(); ※TreeMapHa.. 이전 1 다음
