빨간색과 검은 색 트리는 이진 균형 조회 트리입니다. 각 노드에는 노드의 색상을 나타내는 스토리지 비트가 있으며 빨간색 또는 검은 색 일 수 있습니다.
빨간색과 검은 나무에는 다음과 같은 특성이 있습니다.
(1) 각 노드는 빨간색 또는 검은 색입니다
(2) 루트 노드는 검은 색입니다
(3) 노드가 빨간색 인 경우 두 아들은 검은 색입니다.
(4) 각 노드에 대해, 해당 노드에서 후손까지의 모든 경로에는 동일한 수의 검은 색 노드가 포함되어 있습니다.
레드 블랙 트리의 특성을 통해 모든 레드 블랙 트리 기반 구현은 작동 실행 시간이 로그를 제외하고 (범위 룩업 제외) 반환 된 키의 수에 비례 할 수 있음을 보장합니다.
Java의 Treemap은 빨간색과 검은 나무를 통해 구현됩니다.
사진을 그리지 않으면 혼란스러워지기 쉽습니다. 다음은 빨간색과 검은 색 트리의 삽입 작동을 설명하는 다이어그램입니다.
빨간색과 검은 색 트리에 빨간색 노드를 삽입 한 후 6 가지 상황이 있습니다. N은 삽입 된 노드를 나타내고, P는 부모 노드를 나타내고, u는 아저씨 노드를 나타내고, g는 할아버지 노드를 나타내고, x는 현재 작동 노드를 나타냅니다.
코드는 다음과 같습니다.
public class redblackbst <키는 비슷한 <key>, value> {private node root; 개인 정적 최종 부울 레드 = true; 개인 정적 최종 부울 블랙 = 거짓; 개인 클래스 노드 {개인 키 키; // 키 프라이빗 값 val; // 값 비공개 노드 왼쪽, 오른쪽, 부모; // 왼쪽과 왼쪽 자식 및 부모 노드 개인 부울 색상; // 상위 노드 공개 노드 (키 키, value val, node parent, boolean color)가 가리키는 링크의 색상 {this.key = key; this.val = val; this.color = 색상; }} public value get (키 키) {노드 x = 루트; while (x! = null) {int cmp = key.compareto (x.key); if (cmp <0) x = x.left; else if (cmp> 0) x = x.right; 그렇지 않으면 x.val을 반환합니다. } return null; } public void put (키 키, value val) {if (root == null) {// 루트 노드 인 경우 노드를 검은 색 루트 = 새 노드 (key, val, null, black)로 만듭니다. 반품; } // 적절한 삽입 위치를 찾습니다. 노드 부모 = null; 노드 cur = 루트; while (cur! = null) {parent = cur; if (key.compareto (cur.key)> 0) cur = cur.right; else cur = cur.left; } node n = 새 노드 (키, val, 부모, 빨간색); // Ord 정상 새 노드는 빨간색입니다. // 부모 아래에 새 노드를 삽입 if (key.compareto (parent.key)> 0) parent.right = n; else parent.left = n; // 새 노드를 삽입 한 후에는 트리의 일부 노드의 색상과 속성을 조정하여 빨간색과 검은 색 트리의 특징이 파괴되지 않도록해야합니다. fixafterinsertion (n); } private node parentof (node x) {return (x == null? null : x.parent); } private boolean colorof (node x) {return (x == null? null : x.right); } 개인 노드 왼쪽 (노드 x) {return (x == null? null : x.right); } private node rightof (node x) {return (x == null? null : x.right); } private void setColor (노드 x, 부울 색상) {if (x! = null) x.color = color; } private void fixfterinsertion (node x) {while (x! = null && colorof (parentof (x)) == 빨간색) {node grandpa = parentof (parentof (x)); 노드 부모 = parentof (x); if (parent == leftof (할아버지)) {// case 1 || case2 || case3 노드 uncle = rightof (할아버지); if (colorof (uncle) == red) {// case1, 삼촌은 빨간색 setColor (부모, 검은 색); // 상위 노드는 검은 색 SetColor (Uncle, Black)입니다. // 삼촌 노드는 검은 색 setColor (할아버지, 빨간색)입니다. // 할아버지 노드는 빨간색 x = 할아버지입니다. // 할아버지 노드는 검은 색에서 빨간색으로 빨간색이기 때문에 상위 노드의 빨간색과 검은 색 속성과 조상이 조정되어야합니다} else {// case2 || CASE3, UNCLE은 검은 색 IF (x == rightof (parent)) {// case2 x = parent; Rotateleft (x); } // case3 setColor (부모, 검은 색); setcolor (할아버지, 빨간색); Rotateright (할아버지); }} else {// case4 || 사례 5 || Case6 노드 uncle = leftof (할아버지); if (colorof (uncle) == 빨간색) {// case4 || CASE5 || case6 setColor (부모, 검은 색); setColor (삼촌, 검은 색); setcolor (할아버지, 빨간색); x = 할아버지; } else {// case5 || Case6, Uncle은 (x == leftof (부모)) {// case5 x = parent; Rotateright (x); } // case6 setColor (부모, 검은 색); setcolor (할아버지, 빨간색); Rotateleft (할아버지); }}}} private void rotateleft (node x) {if (x == null) return; 노드 y = x.right; x.right = y.left; if (y.left! = null) y.left.parent = x; y.left = x; y.parent = x.parent; if (x.parent == null) {root = y; } else if (x.parent.left == x) {x.parent.left = y; } else {x.parent.right = y; } x.parent = y; } private void rotateright (노드 x) {if (x == null) 반환; 노드 Y = X.Left; x.left = y.right; if (y.right! = null) y.right.parent = x; y.right = x; y.parent = x.parent; if (x.parent == null) {root = y; } else if (x.parent.left == x) {x.parent.left = y; } else {x.parent.right = y; } x.parent = y; }}위의 Rotateleft 및 Rotateright에 대한 다이어그램을 그려야합니다.
위의 기사는 빨간색 및 검은 색 트리 삽입 작업의 원칙과 내가 공유하는 모든 컨텐츠 인 Java 구현 방법 (공유)을 기반으로합니다. 나는 당신이 당신에게 참조를 줄 수 있기를 바랍니다. 그리고 당신이 wulin.com을 더 지원할 수 있기를 바랍니다.