크래프톤정글 5주차; TIL 2 - Red-Black Tree의 insert, delete 연산, C typedef, enum 활용, 메모리에서 스택과 힙의 자라나는 방향

• 개인적으로 공부하면서 지속적으로 정보를 추가, 수정, 삭제합니다.
• 정확하지 않은 부분 피드백 주시면 감사합니다.
• TIL 노트의 일부를 정리해서 적합한 카테고리의 노트 항목에 추가합니다.

2022-11-27

Red-Black Tree의 insert 연산

참고: https://www.geeksforgeeks.org/red-black-tree-set-2-insert/
https://www.geeksforgeeks.org/c-program-red-black-tree-insertion/

무엇?

• 삽입하려는 x 노드의 엉클이 red일 때
  
• 삽입하려는 노드 x의 엉클이 black 일때

1. Left Left Case
   

2. Left Right Case
   

3. Right Right Case
   

4. Right Left Case
   

→ 자료구조 노트에 정리해서 RB트리 항목 추가!

왜?

어떻게?

Red-Black Tree의 삭제 delete 연산

참고: https://eat2go.tistory.com/37
https://velog.io/@bongf/Red-Black-tree-레드블랙트리-fdu4oe3a
https://blogshine.tistory.com/102

무엇?

• BST 삭제 방식
  • 자녀가 0, 1, 2개일때의 3가지 케이스 (자세한 건 여기 BST 항목 ☞ 컴퓨터 과학, 자료구조, 알고리즘 with C언어 )
    • 자녀 0개: 그냥 지움
    • 자녀 1개: 지워지는 노드의 자리를 그 자녀가 대체
    • 자녀 2개: 지워지는 노드를 대체할 가장 중간 값을 찾아(RHS의 최솟값, LHS의 최댓값) 값을 지워질 노드에 복사하고 값을 복사 당한 노드도 지움
• RB 트리의 조건
  1. 모든 노드는 레드 아니면 블랙
  2. 루트 노드는 블랙
  3. 잎 노드(=NIL 노드)는 블랙
  4. 부모가 레드면 자식은 모두 블랙
  5. 한 노드에서 그것의 잎 노드까지 가는 경로에서 거치는 블랙 노드의 수는 동일함
• extra black
  • red-and-black
    • 삭제되는 색이 red인 노드를 대체하는 노드에 extra black을 부여한 경우
  • doubly black
    • 삭제되는 색이 black인 노드를 대체하는 노드에 extra black을 부여한 경우

왜?

트리의 삭제 연산은 제일 까다롭다!
삭제 후에 트리에 미치는 여파 때문인데 삭제 후에도 여전히 트리의 속성을 만족해야 한다.

어떻게?

• 삭제 방식은 일반 BST 연산을 따름
• 삭제 이후에 RB 트리 조건을 위반했는지 확인 → 위반했다면 fix하기
  • 삭제되는 색이 red -> pass
  • 삭제되는 색이 black -> RB트리 조건 2, 4, 5번을 위반할 수 있음
• 위반한 RB 트리 속성 재조정 (이때 extra black이라는 개념 등장) → 삭제되는 색을 가진 노드를 대체하는 노드에 extra black 부여
  • red-and-black -> black 으로 바꿈
  • doubly black → 형제의 색, 형제의 자녀들의 색에 따라 4가지 case

C typedef, enum 활용

참고: https://zoosso.tistory.com/1036

무엇?

왜?

어떻게?

파이썬에서는 enumerate() 함수가 원소와 인덱스를 동시에 다룰 수 있게 해줬는데, 이거랑 비슷하다

메모리 구조, 스택이 아래로 늘어나고 힙이 위로 늘어나는 이유

참고: https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=jsky10503&logNo=221215993229
https://www.hackerschool.org/Sub_Html/HS_University/BOF/essential/PDF_Files/15.pdf

무엇?

위와 같은 가상 주소 공간에서 스택은 아래로 자라나고, 힙은 위로 자라나는 구조이다. 왜 그럴까? (헷갈리게)

왜?

가장 위의 커널 영역은 운영체제를 위한 코드와 데이터를 위한 공간이다. 커널은 CPU와 메모리에 어떤 프로그램을 로드할 것인지 관리하며, 따라서 보호되어야 하고, 응용 프로그램은 이 구역의 코드에 직접 접근할 수 없다.
이러한 이유로 커널 영역을 침범하지 못하도록, 커널 아래에 있는 스택 구역은 위에서 아래로 자라난다. 따라서 아무리 스택이 커져도 접근 불가 영역인 커널을 건드리지 않게 된다.
또한 힙과 스택 사이에는 공유 라이브러리를 위한 영역이 있는데, 이 영역을 마주보고 힙과 스택이 자라난다. 따라서 메모리 공간을 알뜰하게 활용할 수 있게 된다.