붉은 색 검은 색 나무에 삽입

Question

붉은 색 검은 나무를 삽입하는 코드를보고 있습니다. 이 트리에는 "크기"라는 추가 필드가 있으며 노드 x에 뿌리를 둔 하위 트리의 크기를 유지합니다.

AugmentedRBT_Insert(T,x){ 
    BST_Insert(T,x); //insert as if it is a normal BST 
    x[color]=red; //insert as a red node 
    size[x]=1; 
    tmp=parent[x]; 
    while(tmp!=NULL){ //start from the node x and follow the path to root 
     size[tmp]=size[tmp]+1; //update the size of each node 
     tmp=parent[tmp]; 
    } 
} 

는 착색 회전 고정 잊어

은 그들이 다른 기능이 수행 될 것이다 : 여기에 새로운 노드를 삽입하기위한 의사 코드이다. 내 질문은 왜 새로 추가 된 노드 "x"의 크기를 1로 설정합니까? 나는 어떤 하위 트리도 가지지 않을 것이기 때문에 크기는 1이어야하지만 RBT의 요구 사항 중 하나는 모든 빨간 노드에 두 개의 검은 색 자식이 있다는 사실입니다. 실제로 모든 리프 노드는 NULL이고 노드 x "검은 색으로, 그것은 여전히 ​​검은 색 NULL 노드 2 개가 있어야하고 우리는 크기를 3으로 설정해야한다고 생각합니까? 내가 잘못?

감사합니다.

Answer 1

대부분의 이진 트리 에서처럼 빨강 - 검정 나무에 삽입되는 것은 잎에서 직접 발생합니다. 따라서 리프에 뿌리를 둔 하위 트리의 크기는 1입니다. leaves always have the "root" or "nil" as a child, which is black이므로 빨간색 노드에는 두 개의 검은 색 하위가 있습니다. 이러한 null 요소는 노드가 아니므로 노드를 계산하지 않습니다.

그런 다음 모든 부모의 크기를 루트까지 조정합니다 (방금 추가 한 노드에 대해 각각 +1이됩니다).

마지막으로 필요하면 균형을 맞추기 위해 트리를 회전 할 때이 값을 수정합니다. 구현시 크기 업데이트와 회전을 둘 대신 한 번에 수행하는 것이 좋습니다.