이진트리
* 트리 자료구조
- 트리는 나무를 거꾸로 뒤집어 놓은 형태
*이진트리
: 자식 노드가 최대 2개(좌우노드라고도함)
*이진검색 트리
: 이진트리중 활용도가 높은 트리로, 값 크기를 기준으로 일정형태로 구성
(왼쪽 자식노드는 나보다 작고, 오른쪽자식노드는 나보다 크다, 같거나 기준 붙어도 ok)
*포화이진트리
: 루트로부터 시작해서 모든 노드가 정확히 두개 씩의 자식노드를 가지도록 꽉 채워진 트리
노드수가 2의 k제곱 - 1
*전 이진트리
: 모든 자신 노드 개수가 0개 또는 2개
*완전 이진트리
: 노드의 수가 맞지 않아 포화 이진트리를 만들 수 없을 때 왼쪽부터 모두 채워나간 이진트리(포화이진트리만들어나가는 과정)
이진검색트리검색
이진검색트리에서의 값 검색
-> 매우 빠르게 검색가능 ,완전 이진트리인 경우 O(log2n) -> O(logn)
깊이 1 => 원소 2-1 -> 1번
깊이 2 => 원소 4-1 -> 2번
깊이 3 => 원소 8-1 -> 3번
깊이 k => 원소 2의k제곱-1 -> k번
원소 n(=2의 k제곱 -1) -> log2(n+1)번
이진검색트리노드 삽입
이진검색트리에서 값의 삽입
-> 매우 빠르게 값의 삽입가능, 완전이진트리인 경우, O(log2n)
이진트리순회
-> 트리는 보통 루트노드부터 순회를 시작함
1. 너비 우선 탐색
먼저 들어간 (가까운) 노드를 먼저 처리
Queue이용
보통 좌측 자식노드에서 우측자식 노드 순으로 탐색
2. 깊이우선 탐색(그래프와 다름)
Tree Traversal(중위,전위,후위)순회
나중에 들어간 노드를 먼저 처리함
stack("Recursive 재귀/ 순환)이용
모든 노드를 3번씩 지남
* 전위
내꺼->왼쪽->오른쪽
*중위
왼쪽->내꺼->오른쪽
: 중위 순회 탐색 시 키 값은 오름차순 나열이 된다.
*후위
왼쪽->오른쪽->내꺼
이진검색트리에서 노드 삭제
1. 자식노드가 없는경우(리프노드인 경우)
: 부모가 None을 가리키게 한 후[노드삭제]
2. 자식 노드가 하나인 경우
: 부모가 자식을 대신 가리키게 한 후 [노드삭제]
3. 자식 노드가 2개인 경우
:서브 트리에서 대체 노드와 치환
(왼쪽 서브트리에서 키 값이 가장 큰 노드 or 오른쪽 서브트리에서 키 값이 가장 작은 노드)
수식표기법
전위 : X % X + = 3 1 5 10 2 + 2 1
----> 연산자가 앞에 있다, [연산자 숫자 숫자] 찾아라
중위 : (3-1+5) X 10 % 2 X (2+1) = 105
후위 : 3 1 - 5 + 10 X 2 % 2 1 + X
----> [숫자 숫자 연산자] 찾아라
'개발일기 > Python' 카테고리의 다른 글
[Python] - 축소정복 (0) | 2023.04.24 |
---|---|
[Python] 알고리즘 - 완전탐색 (0) | 2023.04.24 |
[Python] 기본적인 자료구조 - 그래프(Graph) (0) | 2023.04.24 |
[Python] 알고리즘 효율성 분석 (0) | 2023.04.24 |
[Python] 알고리즘 - 최대 공약수 구하기(유클리드 알고리즘) (0) | 2023.03.14 |