기본 콘텐츠로 건너뛰기

개발 공부 - [검색트리] 레드블랙트리 - 2

INSERT

- 보통의 BST에서처럼 노드를 INSERT한다.

- 새로운 노드 z를 red노드로 한다.

- RB-INSERT-FIXUP을 호출한다.

RB-INSERT(T, z)
 y <- nil[T]
 x <- root[T]
 while x != nil[T]
   do y <- x
     if key[z] < key[x]
       then x <- left[x]
       else x <- right[x]
 p[z] <- y
 if y = nil[T]
   then root[T] <- z
   else if key[z] < key[y]
          then left[y] <- z
          else right[y] <- z
 left[z] <- nil[T]
 right[z] <- nil[T]
 color[z] <- RED
 RB-INSERT-FIXUP(T, z)



FIXUP

레드블랙트리의 규칙이 위반될 가능성이 있는 조건들


각 노드는 red 혹은 black이다.

위반 가능성 없음


루트노드는 black이다.

새로운 노드 z가 루트 노드라면 규칙 위반, 아니라면 위반 가능성 없음

새로운 노드 z가 루트 노드라면 간단하게 노드를 블랙으로 바꾸는 작업을 해주면 된다.


모든 리프노드(즉, NIL 노드)는 black이다.

새로운 노드의 자식들을 NIL노드로 설정하므로 위반 가능성 없음


red노드의 자식노드들은 전부 black이다.(즉, red노드는 연속되어 등장하지 않고)

위반 될 가능성이 있다. 부모 노드가 원래 RED였다면, RED - RED 가 되므로 위반이 발생한다.

가장 큰 문제가 되는 것이 RED - RED 조건을 위반 하는 것이다.


모든 노드에 대해서 그 노드로 부터 자손인 리프노드에 이르는 모든 경로에는 동일한 개수의 black노드가 존재한다.

새로운 노드를 RED로 추가 했으므로, 위반 가능성 없음


Loop Invariant (루프를 돌면서 변하지 않고 유지되는 조건) :

z는 red 노드
오직 하나의 위반만이 존재한다.
조건 2 : z가 루트노드이면서 red이거나, 또는
조건 4 : z와 그 부모 p[z]가 둘 다 red 이거나.
: 조건 4를 해결하기 위해 부모노드를 타고 올라가다 보면, 또다른 RED - RED 위반이 있을 수 있다. 최악의 경우 루트노드까지 타고올라가게 되면, 조건 2를 위반 한 것이므로 루트노드를 블랙으로 바꿔주고 종료하면 된다.

종료조건 :
부모노드 p[z]가 black이되면 종료한다. 조건2가 위반일 경우 z를 블랙으로 바꿔주고 종료한다.

INSERT의 시간복잡도

- BST에서의 INSERT : O(logn)

- RB-INSERT-FIXUP
Case 1, 4에 해당할 경우 z가 2레벨 상승한다.
Case 2, 3, 5, 6에 해당할 경우 O(1)
따라서, 트리의 높이에 비례하는 시간복잡도를 가진다.

즉, INSERT의 시간복잡도는 O(logn)



참고: https://ict-nroo.tistory.com/71?category=698685 

댓글

  1. 수도 코드를 좀 구동하는 코드로 바꿔보려고 할 것 (오늘은 못 하니 3 들을 때 할 것)

    답글삭제

댓글 쓰기

이 블로그의 인기 게시물

Ebook - 전자책 drm 상관 없이 pdf로 만들기

yes24와 교보문고에서 ebook을 구매 해야 했는데 너무 불편하고, 필기가 매우 화날 정도로 안 좋아서 원시적으로 사용하기로 했다. 1. 목적 : ebook에서 필기 및 사용이 불편하여 pdf로 변환  2. 용도 : 개인 사용 목적이며 화질이 다소 저하되어도 필기만 용이하면 상관 없음 3. 방법 1) 휴대폰 및 카메라로 동영상을 촬영했다. DRM 때문에 프로그램으로는 촬영이 안 되는 것을 확인했다. 2) 마우스 클릭 해주는 매크로를 사용했다. (1) key_macro.exe > https://blog.daum.net/pg365/250 듀얼 모니터에서 위치 이탈 현상이 있긴 해도 괜찮았다. (2) AutoClick.exe > http://bestsoftwarecenter.blogspot.com/2011/02/autoclick-22.html 이 걸로 잘 사용했다. 3초마다 한 번 클릭하도록 사용했다. 3) 동영상을 이미지로 변경해주는 프로그램을 사용했다. Free Video to JPG Converter > https://free-video-to-jpg-converter.kr.uptodown.com/windows 일 하면서 듀얼 모니터에 켜 놨는데 속도가 괜찮았다. * Every frame 으로 사용해야 한다. 4) 중복 사진 제거해주는 프로그램을 사용했다. VlsiPics  > http://www.visipics.info/index.php?title=Main_Page 생각보다 느리니 퇴근시에 걸어놓고 가면 된다. 한번 play가 끝나면 Auto-select 하고 Delete 하면 된다. 5) 이미지를 일괄 Crop 작업 해주는 프로그램을 사용했다. JPEGCrops > https://jpegcrops.softonic.kr/ * https://joker1209.tistory.com/11 도 참고했다. View -> Large 로 크게 본 뒤, Edit -> Syncronize Crops 로 일괄 동일하게 적용하는 방식을 사

개발 공부 - json JSONObject 사용 시 백슬래시(\), 원화 표시(\) 제거 및 치환

import org.json.simple.JSONObject; String dataString = new String(authData.toJSONString()); dataString = dataString.replaceAll("\\\\", ""); String 으로 안 바뀌는 가 싶어서 String 으로 변환 해 주고 작업 하였다. 사실 toJSONString 해도 정상 동작 해야 하는데 이유를 잘 모르겠음. 그리고 나서 다시 이클립스 구동 하니 toString 도 먹은 걸로 봐서 이상하다고 생각! String dataString = authData.toString(); dataString = dataString.replaceAll("\\\\", ""); 어쨌든 백 슬래시 제거를 해줘야 하는데 \\ 도 아니고 \\\\를 해야 변환이 가능했다는 결말이었습니다. 참고 : https://stackoverflow.com/questions/15450519/why-does-string-replace-not-work/15450539 test =test.replace("KP", "");  replace 후에 담아 주지 않으면 적용이 안 됩니다!

카카오 계정 삭제 - 카카오 계정 탈퇴 하는 법

몇일 동안 카카오톡 계정 삭제를 하려고 신경질이 나 있었습니다. 간단하게 말하면 그냥 https://accounts.kakao.com/weblogin/deactivate 이 링크만 알려줬으면 될 걸 왜 이렇게 어렵게 만들어!! 안녕하세요. kakao입니다. 문의해주신 내용 관련하여 답변 드리겠습니다. 카카오톡을 이용해 주셔서 감사합니다. 카카오에서는 고객님의 카카오계정을 임의로 탈퇴 처리 해드리기어려운 점 양해 부탁드리며,  번거로우시더라도 탈퇴를 원하시는 카카오계정으로 로그인 하시어  아래의 방법을 통해 직접 탈퇴 하실 수 있습니다. 카카오계정은 카카오톡을 포함하여 카카오스토리, 카카오게임, 카카오페이지 등  다른 카카오 서비스를 모두 이용할 수 있는 통합 계정입니다.  따라서, 카카오톡을 탈퇴하여도 카카오계정에 연결된 다른 서비스가 있다면  카카오계정은 자동으로 탈퇴되지 않습니다.  카카오톡, 카카오스토리 서비스를 이용하고 계신 경우  카카오계정에 연결된 카카오 서비스를 모두 탈퇴하신 후  마지막으로 카카오스토리, 카카오톡을 탈퇴하시면 카카오계정이 함께 탈퇴됩니다.    ※ 카카오계정에 연결된 서비스는      ' 카카오톡, 카카오스토리 앱> 더보기> 내 프로필> 카카오계정> 연결된 서비스 관리' 에서       확인하실 수 있습니다.  ※ 카카오톡, 카카오스토리 탈퇴 시에 '카카오계정은 탈퇴되지 않는다'는 안내를 받으셨다면     카카오톡, 카카오스토리 탈퇴한 이후에 카카오계정 탈퇴 페이지에서     별도로 카카오계정 탈퇴를 진행하시면 됩니다. 단, 카카오계정 탈퇴 시 금전적인 문제가 발생할 수 있거나,  타인의 서비스 이용에 영향을 줄 수 있는 경우에는 바로 탈퇴할 수 없으며,  해당 서비스를 해지하거나 설정을 변경하신 후 카카오계정을 탈퇴하실 수 있습니다.  ※ 이미 카카