💾 searching, recursion, tree

오늘 배울 것 ✏️

• 자료구조의 활용 방법
  1) 검색과 재귀
  2) 트리에 대한 기본 개념

Searching

• 특정 노드를 추가하거나 삭제를 위해서는 검색이 우선되야 한다 (선행)
• 최적 알고리즘 경로를 측정하는데 쓰인다
• 검색하는 컬렉션이 무작위적이고 정렬되지 않은 경우, 선형 검색이 기본적인 검색 방법임

# 하나의 반복문과 리스트(자료구조)의 인덱스, 조건문을 활용하여 특정값을 찾을 때까지 반복
def linear_search(arr, target):
	
    for idx in range(len(arr)):
    	if arr[idx] == target
        	return idx
    # 전체 배열을 다 돌았다
    return -1

Recursion

• 자기 자신을 재호출하는 것
• 재귀의 개념은 수학적 사고에 기반하고, 코드를 작성하기 전에 문제를 해결하는 재호출 로직을 발견해야 한다.
• 수학 공부를 하는 것처럼 직접 손으로 풀어보자.
• 재귀 호출은 스택의 개념이 적용되며, 함수의 내부는 스택처럼 관리된다 (후입선출)(Last Input First Out)
• 재귀로 문제를 해결하는 방법?
  - 하위 문제를 쉽게 해결할 수 있을 떄까지 문제를 더 작은 하위 문제로 쪼개기
  • 분할 정복법 : 하나의 문제를 분할하면서 해결하고 해결 후 하나로 다시 합치는 방법
• 예시

def counter(num):
	# 멈추는 조건
	if num == 1:
		return 1
	# 1이 될때까지 하나씩 더해주기
    	# num 부터 1까지 한번씩 나올 수 있도록 거꾸로 돌리기
	else:
		return num + counter(num-1)

재귀의 조건

1. base case (기본 케이스 또는 조건) 이 있어야 함

• 알고리즘이 반복을 중지하도록 하는 조건
  ex) sum(num) num까지 다 더하는 함수의 경우, num의 값이 1이면 멈춘다 (return 1)

2. 추가 조건과 기본 케이스의 차이를 확인한다.

• 로직의 차이
• 계속 반복하다가 기본 케이스 값을 만족하기 위한 추가 조건이 필요하다
• 반복을 중지하는 조건 외 나머지 조건들
  ex) num = num - 1

3. 반드시 자기 자신(함수)를 호출해야 한다

• 함수의 마지막 줄에서 재귀작업을 수행한다 (꼭 아닐수도 있지만)

최대공약수를 구하는 재귀 함수 (유클리드 호제법)

1. base case : 둘 중 작은 수가 큰 수로 나눠진다면 멈춘다

• 최대공약수 : 두 수를 나누는 가장 큰 수
• x > y 일때 x % y = 0 이라면 y가 최대 공약수

2. 추가 조건

• x % y != 0 이라면 y, x%y (x를 y로 나눈 나머지)가 나눠지는지 확인
• x % y가 0이 될때까지 반복

3. 자기 자신 호출

• return gcd(x, x%y)

Tree

자료 구조의 중요 개념

1. root 뿌리 노드

• 가장 위쪽에 있는 노드로, 트리별 하나만 있음
• 루트와 부모는 다름. 부모노드는 자식 노드가 1개 이상 있는 경우에 존재하는 노드

2. sub tree 서브 트리

• 자식 노드이면서 부모 노드 역할을 하는 노드가 있는 트리.
• 전체 트리 안에 서브 트리 여러개로 나눌 수 있음

3. 차수

• 노드가 갖고 있는 최대 자식 노드 수
• 위의 경우 차수는 3개
  - 1의 차수(3), 3의 차수(2)

4. leaf 리프 노드

• 레벨별로 가장 마지막에 있는 노드
• 단말노드(terminal node), 외부노드(external node)
• 리프는 트리별로 여러개가 있을 수 있다

5. 레벨

• 루트노드에서 얼마나 멀리 떨어져있는지 각각 나타냄 (계층)
• root node level : 0
• 아래로 내려갈때마다 +1 (0, 1, 2)

6. 높이

• 루트에서 가장 멀리 떨어진 리프까지의 거리 (레벨과 달리 값 하나)
• 리프 레벨의 최대값 (2)

7. sibling 형제 노드

• 부모가 같은 노드

Binary Tree

• 이진 트리는 노드별로 최대 2개의 서브 노드를 갖는 트리 (차수 최대 2) (left, right)
• 조건

1. 루트 노드를 중심으로 두 개의 서브 트리로 나눠진다
2. 나눠진 두 서브트리도 각각 두 개의 서브트리를 갖는다.
3. 서브트리의 노드가 반드시 값을 갖고 있을 필요는 없다. (==노드가 없는 상태)
   
   -> 서브트리의 노드가 없는 경우도 이렇게 있슴

# 기본 코드
# 이진트리 노드 생성

class BinaryTreeNode:
	def __init__(self, value):
    	self.left = None #왼쪽 서브 노드
        self.value = value #해당 노드 값
        self.right = None #오른쪽 서브 노드

포화 이진 트리

모든 리프 노드들이 동일한 레벨을 갖고 있는 경우 (0,1,2,3)

완전 이진 트리

위의 경우처럼 3레벨에서 서브 노드 몇개가 빠졌다

• 노드가 위에서 아래로 채워져있다 (빠지더라도 가장 아래부터 빠짐)
• 노드가 왼쪽에서 오른쪽 순서대로 채워져있다 (빠지더라도 오른쪽 부터 빠짐)

이진트리중 많이 쓰이는 트리..

Binary Search Tree (BST ㄷㄷ)

이진검색트리

• 노드를 정확하게 정렬하는 이진 트리 유형
• 목적 자체가 검색 (최종 목적 - 노드 정렬)

값 크기 조건

• 왼쪽 서브노드의 값 (left child) < 루트(부모)노드의 값(root) < 오른쪽 서브 노드의 값(right child)

• 중복값을 갖고 있는 노드가 없어야 한다

• 왼쪽 서브트리 노드들의 값은 루트 값보다 작아야 함

• 오른쪽 서브트리 노드들의 값은 루트 값보다 커야 함

위에 대한 규칙이 정해진 이유

• 왼쪽 -> 오른쪽으로 검색하는 구조이기 때문
• 트리와 같은 자료구조는 기본이 되는 연결리스트를 참조해서 만들어진 개념이기 때문 (왼쪽->오른쪽)
  (연결리스트를 개선해서 만든 자료구조)
  
  위의 사진의 경우 1 -> 2 -> 4 -> 5 -> 6 -> 7 식으로 검색함 (???)

  검색 방법
  4를 검색할 때 6보다 작으므로 왼쪽 부터 검색
  4가 2보다 크므로 오른쪽 검색
  4가 5보다 작으므로 왼쪽 검색
  4 검색 성공

검색 실패의 경우, 8이 6보다 크므로 오른쪽 검색
8이 7보다 크므로 오른쪽 검색 -> 노드 없음 -> 검색 실패

특징

• 위와 같은 규칙에 따라 구조가 단순함 (값에 따라 구조 자체가 정해짐)
• 검색하는 순서에 따라 노드 값을 오름차순, 또는 내림차순으로 얻는다 (중복값 없음)
• 정렬되어 있으니 검색이 쉽다. 그래서 노드 삽입도 쉽다.

소스코드

class node:
	def __init__(self, value):
    	self.value = value
        self.left = None
        self.right = None
        
 # 이진 검색 트리
 class binary_search_tree:
 	def __init__(self, head):
    		self.head = head # root node
        
    	def insert_node(self, value):
    		self.base_node = self.head # 헤드를 root node로 설정
        	while True: 
        		if value < self.base_node.value: # root 값이 삽입할 노드의 값보다 크면
            			if self.base_node.left == None : # 그리고 왼쪽 노드가 비어있으면
        				self.base_node.left = node(value) # 해당 값을 갖고 있는 노드 생성
                    			break # 그리고 while문 끝내기 (삽입 했으니깐)
                	else: # 근데 안 비어있으면
                		self.base_node = self.base_node.left # 루트를 그 안 비어있는 왼쪽 노드로 내려가기
                		#그리고 while True이므로 break 될때까지 반복
         		else: # root 값이 삽입할 노드의 값보다 작으면
            		if self.base_node.right == None:
                		self.base_node.right = node(value)
                    		break
                	else:
                		self.base_node = self.base_node.right
                        
                        
       	def search_node(self, value):
        	self.base_node = self.head
            
            while self.base_node: # root 노드 값이 있을때까지
            	if self.base_node.value == value:
                	return True
                else:
                	if self.base_node.value > value :
                    		self.base_node = self.base_node.left
                    	else:
                    		self.base_node = self.base_node.right
            return False