red black tree의 회전에 관해 질문드립니다

athxue의 이미지

이재규님의 알고리즘책을 보고 있습니다.
책에보면 red black tree의 회전에 관한 설명이 있는데 이해가
잘 안되서 질문드립니다.


이렇게 4,5,8,9가 들어가 있는 트리에 10을 넣었습니다.
그러나 9와 10이 연속으로 빨간노드이기 때문에 정의에
어긋나 회전을 합니다.


회전을 하여도 9와 10은 여전히 연속되어 있습니다.
여기까지는 이해가 가는데 다음게 이해가 안갑니다.


그림에서 보면 9에 있던 빨간색이 8로 내려갔는데 이게 그냥
이렇게 내려가도 되는건지 아니면 중간과정이 생략되어 있는건지
이해가 잘 안되네요

File attachments: 
첨부파일 크기
Image icon _4.jpg15.04 KB
Image icon _3.jpg13.48 KB
Image icon _1.jpg28.37 KB
ole2000의 이미지

아.. 오래전에 한거라 기억이 가물가물 하지만..

규칙중에 어떤 노드에서 NIL까지의 경로에 같은수의 검은색이 있어야 한다는 규칙이 있습니다.

만약에 9가 빨간색이고 8이 검은색, 10이 빨간색이면

위의 규칙에 어긋나게 되는거죠..

저도 오래전에 한거라 확실치는 않구요..

구글에서 red black tree applet으로 검색해보면

자바 애플릿으로 되어있어 직접 트리를 만들어볼수있는게 있을겁니다.

그걸로 직접 대입해보면 이해가 쉬울겁니다.

Be cool...

athxue의 이미지

ole2000 wrote:
아.. 오래전에 한거라 기억이 가물가물 하지만..

규칙중에 어떤 노드에서 NIL까지의 경로에 같은수의 검은색이 있어야 한다는 규칙이 있습니다.

만약에 9가 빨간색이고 8이 검은색, 10이 빨간색이면

위의 규칙에 어긋나게 되는거죠..

저도 오래전에 한거라 확실치는 않구요..

구글에서 red black tree applet으로 검색해보면

자바 애플릿으로 되어있어 직접 트리를 만들어볼수있는게 있을겁니다.

그걸로 직접 대입해보면 이해가 쉬울겁니다.

저도 이해가 안되서 자바 애플릿으로 실행해 봤는데
9에 있던 빨간색이 8로 쏙 내려오더라고요.
어째서 저게 그냥 내려올수 있나 계속 고민하고 있는데
제가 정의를 잘못 이해하고 있는건지..

sardy의 이미지

Red 의 Child는 Red 가 될수 없습니다. RB Tree 속성중의 하나죠.

athxue의 이미지

sardy wrote:
Red 의 Child는 Red 가 될수 없습니다. RB Tree 속성중의 하나죠.

예. 하지만 제가 궁금한건 어떻게 해서 빨간색이 그냥 자식으로
쏙 내려올 수 있나 그게 궁금합니다. 양쪽자식 모두에게로 내려
가는건 이해가 가는데 한쪽 자식으로만 그렇게 이동할수 있는지
의문입니다..

wantthing의 이미지

http://soar.snu.ac.kr/course/ds/20052/notes/Chapter12-1.ppt

저도 같은 내용이 궁금해서 찾다가 구한 자료입니다.
red black tree가 2-3-4 tree를 베이스로 가지고 있네요.
문의하신 부분은 [8 9] node에 10이 추가됨으로써
[8 9 10] node가 구현되고,( 2-3-4 tree로 생각하면)
red black tree에서는 위와 같이 나타내어 지는 것입니다.

처음에 9가 red인 것은 8에 포함되는 node이기 때문이고
8과 10이 빨간색이 되는 건 9가 대표가 되었기 때문에,
9에 포함되는 node로서... 뭐 그런 것 같습니다.

wantthing의 이미지

http://soar.snu.ac.kr/course/ds/20052/notes/Chapter12-1.ppt

저도 같은 내용이 궁금해서 찾다가 구한 자료입니다.
red black tree가 2-3-4 tree를 베이스로 가지고 있네요.
문의하신 부분은 [8 9] node에 10이 추가됨으로써
[8 9 10] node가 구현되고,( 2-3-4 tree로 생각하면)
red black tree에서는 위와 같이 나타내어 지는 것입니다.

처음에 9가 red인 것은 8에 포함되는 node이기 때문이고
8과 10이 빨간색이 되는 건 9가 대표가 되었기 때문에,
9에 포함되는 node로서... 뭐 그런 것 같습니다.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.