붉 은 검 은 나무 에 대해
붉 은 검 은 나 무 는 '완전한 균형' 을 추구 하지 않 는 다. 그것 은 부분적으로 균형 요 구 를 달성 하고 회전 에 대한 요 구 를 낮 추어 성능 을 향상 시킨다.
빨 간 검 은 나 무 는 O (log 2 n) 의 시간 복잡 도 로 검색, 삽입, 삭제 작업 을 할 수 있 습 니 다.그 밖 에 디자인 으로 인해 어떠한 불 균형 도 세 번 의 회전 안에서 해결 된다.물론 더 좋 은 것 도 있 지만 실현 하면 더욱 복잡 한 데이터 구 조 는 한 걸음 회전 안에 균형 을 이 룰 수 있 지만 빨 간 검 은 나 무 는 우리 에 게 비교적 저렴 한 해결 방안 을 줄 수 있다.레 드 블랙 트 리 는 알고리즘 시간 복잡 도가 AVL 과 같 지만 통계 성능 은 AVL 트 리 보다 높다.
물론 붉 은 검 은 나 무 는 모든 응용 나무의 영역 에 적응 하지 못 한다.만약 데이터 가 기본적으로 정적 이 라면 그들 이 삽입 할 수 있 고 균형 에 영향 을 주지 않 는 곳 에 있 게 하 는 것 이 더욱 좋 은 성능 을 가 질 것 이다.만약 데이터 가 완전히 정적 이 라면, 예 를 들 어 해시 표를 만 들 면 성능 이 좀 더 좋 을 것 이다.
다음은 자바 로 추가 및 삭제 작업 을 마 쳤 습 니 다.
기본: * 레 드 블랙 트 리 의 노드 (x) 를 왼쪽 회전 * * 왼쪽 회전 설명도 (노드 x 를 왼쪽 회전): * root * / * x p * / \ - (왼쪽 회전) -. / * lx p x rp * / * lp rp lx lp * * / private > void right Rotate (TreeNode x, TreeNode root) {TreeNode p = x. right; if (p. left! = null) {p. left. parent = x;} if(x. parent = = null) {root = p; / x 가 루트 노드 일 때} else {if (x. parent. left = = x) x. parent. left = p; else x. parent. right = p;} p. left = x; x. parent = p;}
우회전: / *
py py
/ /
x p
/ \ --( )-.>> / \
p rx lp x
/ \ / \
lp rp rp rx
* / private > void left Rotate (TreeNode x, TreeNode root) {TreeNode p = x. right; if (p. right! = null) {x. left = p. right;} if (p. right! = null) {p. right. parent = x;} if (x. parent = = null) {root = p; / / x 가 루트 노드 일 때} else {if (x. parent. right = x) x. parent. let = p; else x. parent. right = p;}
삽입:
* 1. ，
* 2.
* 3.
* ：
* ， 。
* 。
* 。 [ ： ， ！]
* ， 。
* 。
* @param n
* @param root
* @param
* @param
*/
private > void insert(TreeNode n,TreeNode root){
while (root != null) {
if (n.key.compareTo(root.key) < 0)
root =root.left;
else
root= root.right;
}
TreeNode p=null;
if(root==null){
root=n;
}else {
p = root.parent;
}
n.parent=p;
n.red=true;
//
if(n.key.compareTo(p.key)>0){
p.right=n;
}else {
p.left=n;
}
insertRedTree(n,root);
}
private > void insertRedTree(TreeNode n,TreeNode root) {
TreeNode parent=n.parent;
//
if(n.parent==null){
n.red=false;
}
while((parent=n.parent)!=null&&parent.red){
TreeNode gParent=n.parent.parent;
//
if(gParent.left.red&&gParent.right.red||(gParent.left.red&&gParent.right!=null)||(gParent.right.red&&gParent.left!=null)){
gParent.right.red=false;
gParent.left.red=false;
gParent.red=true;
n=gParent;
continue;
}
// ，
if(n==parent.right){
n=parent;
parent=n.parent;
n.leftRotate(n,root);
}else{
// ，
parent.red=false;
gParent.red=true;
n.rightRotate(gParent,root);
}
}
root.red=false;
}
삭제:
private > void remove (TreeNode n, TreeNode root) {TreeNode child, parent; if (n. left! = null & n. right! = null) {/ 삭 제 된 노드 에 두 아들 이 있 습 니 다.. / / 여기 서 후계 노드 는 대역 에 해당 합 니 다. / / 후계 노드 의 내용 을 '삭 제 된 노드' 에 복사 한 후 / / 후계 노드 를 삭제 합 니 다. 이렇게 하면 문 제 를 '후계 노드 삭제' 로 교묘 하 게 변환 합 니 다. TreeNode replace = n; / / 후계 노드 replace = replace. right; while (replace. left! = null) {replace = replace. left;}/ * * * * O * / * x y * / * p rx * / \ / * lp rp a b * * x 의 후계 결점 은 a * / if (n. parent = = null) {root = replace;} else {if (n. parent. left = = n) {n. parent. left = replace;} else {n. parent. right = replace;}}child = replace. right; parent = replace. parent; boolean color = replace. red; / 후계 노드 를 덮어 서 삭제 한 값 입 니 다. 후계 노드 의 right 를 parent 에 if (parent = = n) {parent = replace;} else {if (child! = null) {child. parent = parent; parent. left = child; replace. right = n. right; n. right. parent = replace;}}/ / 속성 은 모두 replace. parent = n. parent; replace. red = n. red; replace. left = n. left; n. left. parent = replace; / 원래 색상 이 검은색 if (! color) {/ / 빨간색 검 은 나무의 특성 유지 removeRedTree (child, parent, root);} n = null; return;}
// 。 ， ， 。
if (n.left !=null) {
child = n.left;
} else {
child = n.right;
}
parent = n.parent;
// " "
boolean color = n.red;
if (child!=null)
child.parent = parent;
// "node "
if (parent!=null) {
if (parent.left == n)
parent.left = child;
else
parent.right = child;
} else {
root = child;
}
if (color == false)
removeRedTree(child, parent,root);
n = null;
}
private > void removeRedTree(TreeNode n, TreeNode parent, TreeNode root) {
TreeNode p;
while((n==null||n.red)&&n.parent!=null) {
if (parent.left == n)
p = parent.right;
else p=parent.left;
//x “ + ” ，x 。
if (p.red) {
p.red=false;
parent.red=true;
p.leftRotate(parent,root);
p= parent.right;
}
// x “ + ” ，x ，x 。
if ((p.left==null || !p.left.red) &&
(p.right==null || !p.right.red)) {
p.red=true;
n = parent;
parent = n.parent;
}
else {
//x “ + ” ，x ；x ， 。
if (p.right==null || !(p.right.red)) {
p.left.red=false;
p.red=true;
p.rightRotate(p,root);
p = parent.right;
}
//x “ + ” ，x ；x ，x 。
p.red=p.parent.red;
p.parent.red=false;
p.right.red=false;
p.leftRotate(parent,root);
n=root;
break;
}
}
}
이 글 은 인터넷 의 실현 을 참고 하여 소스 코드 를 읽 는 것 은 우리 가 대신 분 야 를 이해 하 는 큰 지름길 이다. 생명 이 멈 추 지 않 고 분투 하 는 것 이 그 치지 않 는 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
