Data Structure_#11 균형이진탐색트리(Red-Black, 2-3-4트리)

Red-Black Tree

​ Bh(13)=2 / bh(17)=2/ bh(25)=1

[조건]

• 노드는 red/black

• root=black

• leaf(None)=black -> NIL: None 노드로 특별히 독립된 노드로 취급(leaf 노드)

• red node—child node: black (red 노드는 무조건 black 자식노드 가져야함)

• 각 노드에서 leaf nodes까지 경로에서의 black node수가 항상 같아야 함

  ​ ->NIL을 뺀 나머지 노드는 내부 노드

  [증명]

  (귀납)

연산

1. 삽입 연산

2,3,4 트리

:이진트리 아님 모든 리프노드는 마지막 레벨에 위치해야 하는 탐색트리

1. 자식 노드 개수 =2, 3, 4 (2-노드,3-노드,4-노드로 구분)

2. 모든 leaf 노드가 같은 level에 존재

3. 리프노드들은 원형 이중 연결리스트에 의해 좌-우로 연결

4. 높이: O(logn)

연산

1. insert(key) => 0(log n)

   ->1 split: O(1)

   ->가운데 key 값을 부모로 올리기

1. Delete: 지울 것이 leaf에 있다 가정 ->0(log n)시간

   =>루트에서부터 leaf까지에서 2노드면 3노드로 바꾸기(형제 중 가장 왼쪽이나 오른쪽을 부모로 올림) -> 0(log n)시간

   -> leaf에 지울 값이 없으면 leaf 랑 바꾸기 & leaf 지우기

   ->좌우 형제노드가 다 2노드일땐: 왼쪽이나 오른쪽으로 부모노드랑 합침(4노드로)

   1. key가 내부노드인 경우

      => successor(key)또는 predecessor(key) 찾아 swap -> 리프노드에 있는 값 지움

   2. key가 리프에 있는 경우

      (1) 3-노드, 4-노드: 단순삭제

      (2) 2-노드인경우

      -> 지우면 underflow발생

      -> 루트에서 리프로 내려가면서 2-노드만나면 무조건 3-노드, 4노드로 바꿈(단, 루트가 2-노드인경우는 제외)

      a. 그 과정에서 트리 높이 1감소

      b. 삭제할 key값이 저장된 리프노드는 3-노드/ 4-노드가 되어 단순 삭제 가능

   3. 2-노드를 3-노드/4-노드로 변경

      => rotation: 왼 또는 오른쪽 3-노드/4-노드 형제에서 값하나 빌려와서 3-노드로 만듦

   

2-3-4 를 red-black으로!

: 2nod를 black 노드로 & 3 node는 쪼개지기 & 4 node 중간을 black 한 후 양쪽을 밑으로(red)