[ 이산 수학 ] 9. 재귀함수 / tree

재귀함수에서 해야하는 것

 

- Basis Step : Function에서 zero ( =초기단계 ) 의 상태(값)를 명시하기

- Recursive Step : 각 값을 찾을 수 있는 규칙 제시하기

 

 

 

 

이렇게 규칙을 제시해줘야 함

 

 

 

어떠한 경우에도 n=0이거나 범위에서 가장 작은 값을 초기 단계로 생각하면 됨

 

 

 

- Set에서도 재귀적으로 된다

1)

 

2)

 

저렇게 확장시켜나갈 수도 있다고 한다.

 

시그마 옆에 별 붙어있는 건, 그 안에 있는 원소 개수 상관없이 어떻게 이어붙어셔 만드는 건 다 자기거라는 거

 

 

 

String의 길이

 

l(wx)  = 

 

 

 

괄호를 봤을 때, 어떻게든 갖고있는 순서에 조합만 더 넣는 건 되기 때문에

()는 일단 가능. 그리고 그 순서 그대로 그 안에 들어가는 것들은 같은 집합에 있는 원소면 가능

ex) ()  가능, w도 같은 집합이면 (w) , w() , ()w 다 가능

 

이 매커니즘으로 봤을 때 (()()) 가능할 거 같음?

--> (    )  안에 () () 들어가는 것이므로 가능, 순서도 안 섞였으니까 가능

 

))(()는 당연히 안 됨

 

 

 

 

Tree

 

 

Basis : 하나의 vertex를 가진 꽉 찬 이진 트리가 있다.

Recursive : 꽉 찬 subtree 2개가 있을 때, 그 각 두 개의 root들과 연결하는 root r인 vertex가 있음.

 

 

구조적인 귀납법

집합에는 순서가 없기 때문에 k번째 -> k+1 번째 이런 걸 할 수가 없음. 구조적인 귀납법을 해야함

근데 그냥 귀납법인 거 같은데..

 

예) 

Tree의 height 는 가장 큰 Subtree의 height에서  +1 해준다 ( root까지 생각해서 )

 

 

 

예제2) 

 

전체 노드 수 = 1 + subtree1에 있는 노드 수 + subtree2에 있는 노드 수

                     < 1+ 위에 theorem에 나온 식 대입.

                     < 식을 정리해서 2개 식을 하나로 정리하는데 그냥 *2 해도 어차피 더 클테니까 

                       *2한 상태에서 둘 중에 더 많은 노드의 개수가 있는 쪽으로 가져간다.

                     = 2* 2^(많은 쪽의 노드 개수의 공식)   

       

 

 

(구조적 귀납법)

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=qnpfr0730&logNo=70086304981

 

(참고)

https://bite-sized-learning.tistory.com/482

[이산수학]이진 트리의 정의 및 종류(완전, 포화, 편향)

https://velog.io/@ja_an/%EC%9D%B4%EC%82%B0%EC%88%98%ED%95%99-%EC%A0%95%EA%B7%9C%EC%8B%9D%EA%B3%BC-%EC%A0%95%EA%B7%9C%EB%AC%B8%EB%B2%95

 

 

(출처)

한동대학교 최희열교수님 - 이산수학