[TIL]Day 17

이진탐색트리에서 원소 삭제

1. 키를 이용해서 노드를 찾는다.

• 해당 키의 노드가 없으면, 삭제할 것도 없음
• 찾은 노드의 부모 노드도 알고 있어야 함(아래 2번 때문)

2. 찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리의 구조를 정리한다.

인터페이스의 설계
입력: 키(key)
출력:
삭제한 경우 True
해당 노드가 없는 경우 False

이진 탐색 트리 구조의 유지
삭제되는 노드가
1. 말단인 경우

• 삭제 후 링크 None
• 삭제되는 노드가 root면? self.root = None

2. 자식 1개

• 삭제되는 노드 자리에 그 자식을 대신 배치
• 자식이 왼? 오?
• 부모 노드릐 링크를 조정(왼?오?)
• 삭제되는 노드가 루트면 새로운 노드가 루트

3. 자식 2개

• 삭제되는 노드보다 바로 다음 큰 키를 가지는 노드를 찾아 그 노드를 삭제되는 노드 자리에 대신 배치하고 이 노드를 대신 삭제

이진 탐색트리가 효율적이지 못한 경우

1씩 증가된 숫자들이 들어있는... 구조가 불균형적인 경우

배열을 통한 힙

노드번호는 1부터 시작->루트노드 번호가 1
노드번호 m을 기준으로

• 왼쪽 자식의 번호: 2 * m
• 오른쪽 자식의 번호: 2 * m + 1
• 부모 노드의 번호: m//2

자리바꾸기 파이썬 문법

a,b = b,a

최대힙에서 원소의 삭제

1. 루트 노드의 제거 - 이것이 원소들 중 최댓값
2. 트리의 마지막 자리 노드를 임시로 루트 노드 자리에 배치(완전이진트리 모양을 만듦)
3. 자식노드들과의 값 비교와 아래로, 아래로 이동

• 자식은 둘 있을수도 있는데, 어느 쪽으로 이동?
• 자식중에 더 큰 값을 알아야함

파이썬에서 큐사용

import heapq
heapq.heapify(L) #리스트 L로부터 min heap 구성
m = heapq.heappop(L) #min heap L에서 최소값 삭제 반환
heapq.heappush(L,x) #min heap L에 원소 x삽입

힙은 최대 혹은 최소를 빨리 꺼낼수 있는 성질을 가지고 있음!

동적계획법이란

주어진 최적화문제를
재귀적인 방식으로 보다 작은 부분 문제로 나누어
부분 문제를 풀어, 이 해를 조합하여
전체 문제의 해답에 이르는 방식

알고리즘의 진행에 따라 탐색해야할 범위를 동적으로 결정함으로써
탐색범위를 한정할 수 있음
부분해를 구한 후 조합해서 전체 문제를 해결한다는 개념

파이썬 문법 array::

#리스트 역순 정렬
l[::-1]

참고 url
https://blog.wonkyunglee.io/3