Hoguz

- 리스트의 경우 삽입, 삭제 후에도 정렬 상태를 유지해야 하므로 O(N)시간이 소요

- 이러한 문제점을 보완한 자료구조가 트리 구조

- 트리는 일반적 트리, 이진트리로 구분

- 이진트리는 탐색트리, heap자료구조, 구문트리(syntax Tree)로 구분

- 트리의 용어는 Root, child, Degree(count of child), parent, leaf(no child), Sibling, Ancestor, Descendant, Subtree, Level, Height, Key로 구성

- leaf의 경우 Terminal or External 이라 불리며 leaf가 아닌 노드를 internal or Non-Terminal 라고 불린다.

- 용어에 대한 확실한 이해가 없으면 차후 공부할때 많이 힘들므로 용어는 꼭 외우는 것이 좋다

- 최대 차수가 k인 트리에 n개의 노드가 있다면 none 레퍼런스 수는 nk - (n-1) = n(k-1) + 1 이다

- 즉 아이들이 최대 k개인 노드가 있다면 

- 일반적인 이진트리는 왼쪽 자식, 오른쪽 형제 순으로 key를 구성한다.

- 이진트리의 정의는 각 노드의 자식수가 2 이하인 트리이다. 즉 자식이 2, 1 또는 없을수도(이때의 경우는 leaf) 이다

- 이진트리는 널리 활용된다.

- 이진트리의 경우 포화이진트리, 완전 이진트리, 두가지가 있다.

- 포화이진트리란 모든 이파리의 깊이가 같고 각 내부노드가 2개의 자식노드를 가지는 트리이다

- 완전이진트리란 마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차있고 마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워진 트리이다.

(레벨은 곧 높이, 즉 4레벨의 트리라면 3레벨까지는 포화이진트리로 구성되어있고 마지막 4레벨의 노드들의 경우 왼쪽부터 채워진 트리)

- 레벨 k에 있는 최대 노드 수는 2^(K-1) 이다.( 3레벨의 경우 최대 4개의 노드가 있을 수 있다)

- 레벨 k인 이진트리의 최대 노드 수는 2^H -1 이다

주소 값 찾아오기, 주소 데이터 찾아오기, 삭제 등.

기본적인 메서드를 모두 만들었다.

단순 연결리스트의 핵심은 내 앞이 나를 설명한다는 것.

또한 무엇을 하든간에 계속해서 다음을 찾아주면서 옮겨다녀야 한다.

for, while 무엇이든간에 계속해서

head, head.next ... 반복

한가지 파이썬을 할때 간과했던 점은

비슷하지만 살짝 다른 메서드 들의 경우엔 기존의 메서드들을 재사용 하여 쓰면 훨씬 간편하게 작성할수 있다는 점?

이번 파트는 본격적인 삽입, 삭제 메서드 이다.

연결리스트의 핵심은 나를 증명해주는 것이 내 앞에 있다는 것이다.

즉 철수-영희-미자 가 있다고 하면 미자를 찾기 위해선 영희가 있어야 한다.

이러한 개념을 알고 있다 하더라도 두번째로 마주하게 되는 위기는 참조변수와 객체 부분이다.

새로운 노드를 집어넣은다고 해보자.

즉 철수 - 영희 - 유주 - 미자 처럼 만들고자 할때의 중요한 점은 위에서 말했듯이 미자를 증명하던 것은 영희라는 점이다.

즉 우리는 영희 옆에 유주가 들어가기를 원하지만 만약 이를 먼저 한다면

미자를 다시는 찾을 수 없다!!

따라서 제일 먼저 유주의 옆에 미자가 있다고 선언을 해준 후에 영희 옆에 유주를 집어 넣어야 한다.

(강사님은 장소 = 값 이라고 설명하셨는데 이 설명이 제일 간단하며 와닿는듯 하다)

이를 좀더 코드화 시켜보자면

1. 유주옆 = 미자(그런데 여기서 미자를 증명하는 것은 영희 이므로 이는 곧 영희옆 이라 쓸 수 있다)

== 유주옆 = 영희옆

2. 영희옆 = 유주

...

삭제 작업도 마찬가지이고 꼭 무언가를 넣거나 삭제하기 전에 주소를 옮겨주는 작업을 해줘야 한다는 것, 그것이 매우 중요하다.