세트2 이진 탐색 트리 (binary search tree) → 딕셔너리, 세트를 구현할 때 쓸수있다. 그 이유는 뒤에서 살펴 보겠다. 이진탐색트리속성 부모 노드 왼쪽에는 무조건 부모노드보다 작은 자식노드가 들어가고 부모노드 오른쪽에는 부모노드보다 무조건 큰 자식 노드가 들어간다. 배열이나 파이썬리스트로 구현하지 않고 노드 인스턴스를 연결해서 구현 모든 자식노드가 부모의 레퍼런스를 저장하고 있다. InOrder 순회를 하면 데이터의 값이 순서대로 출력된다. ⇒ ABCDEFGHI 삽입연산 새로운 노드 생성 루트 노드부터 비교하면서 저장할 위치 찾음 찾은 위치에 새롭게 만든 노드 연결 시간복잡도 : O(h) h=높이 탐색연산 주어진 노드의 데이터와 탐색하려는 데이터 비교 탐색하려는 데이터가 더 크면 노드의 오른쪽 자식으로간다. 탐색하려는 데이터가 더 작으면 노드의 왼.. 2024. 1. 19. 추상 자료형 기능과 구현 기능 : 연산이 무엇을 하는지 구현 : 연산의 기능을 어떻게 하는지 추상 자료형 자료구조를 추상화 한 것 -> 데이터를 저장, 사용할 때 기능만 생각 추상화 구현을 몰라도 기능만 알면 프로그래밍을 할수있게 해주는 개념 자료구조는 구현까지 알아야해서 생각할 부분이 기능 뿐만 아니라 구현까지 해서 복잡해지지만 추상 자료형은 기능에만 집중 할 수있기 때문에 조금더 생각을 줄일 수있다. ⇒ 추상 자료형을 생각하면 코드의 흐름에 집중 할 수있다. 파이썬 추상화가 많이된 고수준 언어 많은 자료형 이름이 추상 자료형 리스트 데이터간 순서 관계를 유지 할 수있다. 접근 연산 : 특정 위치에 있는 데이터를 가지고 오거나 수정한다. 탐색 연산 : 특정 조건을 만족하는 데이터를 찾는다. 삽입 연산 : 특정 위치.. 2024. 1. 11. 이전 1 다음
