센티넬 노드
Sentinel node | 이 글은 검증을 위해 인용구가 추가로 필요하다.– · · · (2021년 1월)(이를 |
컴퓨터 프로그래밍에서, Sentinel 노드는 통과 경로 종단기로서 연결된 목록과 트리와 함께 사용되는 특별히 지정된 노드다.이 유형의 노드는 데이터 구조에 의해 관리되는 데이터를 보유하거나 참조하지 않는다.
혜택들
|
다음 이점 중 하나 이상을 얻기 위해 Sentinel을 경로 종단기로 사용하는 대신 사용한다.
- 운영 속도 약간 증가
- 데이터 구조의 견고성 향상(논의할 여지가 있음)
단점
- 알고리즘의 복잡성과 코드 크기가 약간 증가함
- 데이터 구조가 동시에 액세스되는 경우(즉, 액세스되는 모든 노드는 최소한 "읽기 전용"을 위해 보호되어야 함을 의미), 센티넬 기반 구현의 경우, 센티넬 노드는 뮤텍스에 의해 "읽기-쓰기"를 위해 보호되어야 한다.상당히 많은 사용 시나리오에서 이러한 추가 뮤텍스는 심각한 성능 저하를 초래할 수 있다.[1]이를 피하는 한 가지 방법은 "읽기-쓰기"를 위해 목록 구조를 전체적으로 보호하는 반면, "읽기 전용"을 위해 데이터 구조를 전체적으로 보호하는 것으로 충분하다(업데이트 작업이 따르지 않는 경우).
- Sentinel 개념은 디스크에 데이터 구조를 기록하는 데 유용하지 않다.
예
연결된 목록에서 검색
다음은 단일 링크 목록에서 특정 검색 키를 검색하기 위한 서브루틴의 두 가지 버전(C 프로그래밍 언어로 구현됨)이다.첫 번째 것은 센티넬 값을 사용한다. NULL, 그리고 두 번째 sentinel 노드에 대한 sentinel 노드.Sentinel, 목록 끝 표시기로서.단독으로 연결된 목록 데이터 구조의 선언과 두 서브루틴의 결과는 동일하다.
구조상의 sll_node { // 단일 연결 목록의 한 노드 구조상의 sll_node *다음에; // 목록 끝 표시기 또는 -> 다음 노드 인트로 핵심을; } sll, *맨 처음의; NULL을 목록 끝 표시기로 사용하는 첫 번째 버전
// 글로벌 초기화 맨 처음의 = NULL; // 첫 번째 삽입 전(표시되지 않음) 구조상의 sll_node *검색(구조상의 sll_node *맨 처음의, 인트로 search_key) { 구조상의 sll_node *마디를 짓다; 을 위해 (마디를 짓다 = 맨 처음의; 마디를 짓다 != NULL; 마디를 짓다 = 마디를 짓다->다음에) { 만일 (마디를 짓다->핵심을 == search_key) 돌아오다 마디를 짓다; // 발견 } // search_key가 목록에 포함되어 있지 않음: 돌아오다 NULL; } 그for-반복당 두 가지 테스트(노란색 선) 포함:
node != NULL;if (node->key == search_key).
Sentinel 노드를 사용한 두 번째 버전
전역적으로 사용 가능한 포인터sentinel의도적으로 작성된 데이터 구조로Sentinel목록 종료 표시기로 사용된다.
// 전역 변수 sll_node 센티넬, *보초병 = &센티넬; // 글로벌 초기화 보초병->다음에 = 보초병; 맨 처음의 = 보초병; // 첫 번째 삽입 전(표시되지 않음) 포인터가 항상 목록의 끝에 있어야 한다는 점에 유의하십시오.이것은 삽입 및 삭제 기능에 의해 유지되어야 한다.그러나 NULL 포인터를 사용할 때와 거의 동일한 노력이다.
구조상의 sll_node *SearchWithSentinel 노드(구조상의 sll_node *맨 처음의, 인트로 search_key) { 구조상의 sll_node *마디를 짓다; // 검색을 위해 "노드" Sentinel 준비: 보초병->핵심을 = search_key; 을 위해 (마디를 짓다 = 맨 처음의; 마디를 짓다->핵심을 != search_key; 마디를 짓다 = 마디를 짓다->다음에) {} // 후 처리: 만일 (마디를 짓다 != 보초병) 돌아오다 마디를 짓다; // 발견 // search_key가 목록에 포함되어 있지 않음: 돌아오다 NULL; } 그for-반복당 하나의 테스트(노란색 선)만 포함:
node->key != search_key;.
Python의 이중 연결 목록 구현
특히 순환되고 이중으로 연결된 목록 중 하나인 링크된 목록 구현은 목록의 시작과 끝을 구분하는 보초 노드를 사용하여 현저하게 단순화할 수 있다.
- 목록은 다음 및 이전 포인터가 자신을 가리키는 Sentinel 노드인 단일 노드로 시작한다.이 조건은 목록이 비어 있는지 여부를 결정한다.
- 비어 있지 않은 리스트에서, 센티넬 노드의 다음 포인터는 리스트의 머리부분을, 이전 포인터는 리스트의 꼬리를 준다.
다음은 Python의 이중 연계 목록 구현이다.
계급 노드: 반항하다 __init___(자아의, 자료, 다음에=없음, 선구적인=없음): 자아의.자료 = 자료 자아의.다음에 = 다음에 자아의.선구적인 = 선구적인 반항하다 __repr___(자아의) -> 발을 동동 구르다: 돌아오다 f'노드(데이터=)'{자아의.자료})' 계급 LinkedList: 반항하다 __init___(자아의): 자아의._sentinel = 노드(자료=없음) 자아의._sentinel.다음에 = 자아의._sentinel 자아의._sentinel.선구적인 = 자아의._sentinel 반항하다 pop_left(자아의) -> 노드: 돌아오다 자아의.remove_by_ref(자아의._sentinel.다음에) 반항하다 펑펑 터지다(자아의) -> 노드: 돌아오다 자아의.remove_by_ref(자아의._sentinel.선구적인) 반항하다 add_nodeleft(자아의, 마디를 짓다): 자아의.add_node(자아의._sentinel, 마디를 짓다) 반항하다 add_node(자아의, 마디를 짓다): 자아의.add_node(자아의._sentinel.선구적인, 마디를 짓다) 반항하다 add_left(자아의, 자료): 마디를 짓다 = 노드(자료=자료) 자아의.add_nodeleft(마디를 짓다) 반항하다 덧셈을(자아의, 자료): 마디를 짓다 = 노드(자료=자료) 자아의.add_node(마디를 짓다) 반항하다 remove_by_ref(자아의, 마디를 짓다) -> 노드: 만일 마디를 짓다 이다 자아의._sentinel: 높이다 예외('보초는 절대 제거할 수 없다.') 마디를 짓다.선구적인.다음에 = 마디를 짓다.다음에 마디를 짓다.다음에.선구적인 = 마디를 짓다.선구적인 마디를 짓다.선구적인 = 없음 마디를 짓다.다음에 = 없음 돌아오다 마디를 짓다 반항하다 add_node(자아의, 부노드를 만들다, 뉴노드): 뉴노드.다음에 = 부노드를 만들다.다음에 뉴노드.선구적인 = 부노드를 만들다 부노드를 만들다.다음에.선구적인 = 뉴노드 부노드를 만들다.다음에 = 뉴노드 반항하다 샅샅이 뒤지다(자아의, 가치를 매기다): 자아의._sentinel.자료 = 가치를 매기다 마디를 짓다 = 자아의._sentinel.다음에 하는 동안에 마디를 짓다.자료 != 가치를 매기다: 마디를 짓다 = 마디를 짓다.다음에 자아의._sentinel.자료 = 없음 만일 마디를 짓다 이다 자아의._sentinel: 돌아오다 없음 돌아오다 마디를 짓다 반항하다 __iter___(자아의): 마디를 짓다 = 자아의._sentinel.다음에 하는 동안에 마디를 짓다 이다 아닌 자아의._sentinel: 양보하다 마디를 짓다.자료 마디를 짓다 = 마디를 짓다.다음에 반항하다 재평가하다(자아의): 마디를 짓다 = 자아의._sentinel.선구적인 하는 동안에 마디를 짓다 이다 아닌 자아의._sentinel: 양보하다 마디를 짓다.자료 마디를 짓다 = 마디를 짓다.선구적인 어떻게 해야 하는지 주목하라.add_node()메소드는 매개 변수의 새 노드에 의해 이동될 노드를 취함curnode. 왼쪽에 붙이는 경우 이것은 비어 있지 않은 목록의 머리인 반면 오른쪽에 붙이는 경우에는 꼬리인 것이다.하지만 그 연결이 어떻게 Sentinel을 다시 참조하도록 설정되었는지 때문에, 그 코드는 빈 목록에도 역시 사용할 수 있다.curnode감시 노드가 될 겁니다
이진 트리에서 검색
문서 이진 검색 트리와 유사한 일반 선언:
구조상의 bst_node { // 이진 검색 트리의 노드 1개 구조상의 bst_node *어린아이의[2]; // 각각: ->노드 또는 경로 끝 표시기 인트로 핵심을; } ; 구조상의 bst { // 이진 검색 트리 구조상의 bst_node *뿌리를 내리다; // ->노드 또는 경로 끝 표시기 } *비스트; 전역적으로 사용 가능한 포인터 sentinel의도적으로 준비된 단일 데이터 구조로Sentinel = *sentinel아이가 없음을 나타내는 데 사용된다.
// 전역 변수 bst_node 센티넬, *보초병 = &센티넬; // 글로벌 초기화 센티넬.어린아이의[0] = 센티넬.어린아이의[1] = 보초병; 비스트->뿌리를 내리다 = 보초병; // 첫 번째 삽입 전(표시되지 않음) 포인터 센티넬은 항상 트리의 모든 잎을 나타내야 한다는 점에 유의하십시오.이것은 삽입 및 삭제 기능에 의해 유지되어야 한다.그러나 NULL 포인터를 사용할 때와 거의 동일한 노력이다.
구조상의 bst_node *SearchWithSentinel 노드(구조상의 bst *bst, 인트로 search_key) { 구조상의 bst_node *마디를 짓다; // 검색을 위해 "노드" Sentinel 준비: 보초병->핵심을 = search_key; 을 위해 (마디를 짓다 = bst->뿌리를 내리다;;) { 만일 (search_key == 마디를 짓다->핵심을) 부숴뜨리다; 만일 search_key < 마디를 짓다->핵심을: 마디를 짓다 = 마디를 짓다->어린아이의[0]; // 왼쪽으로 이동 다른 마디를 짓다 = 마디를 짓다->어린아이의[1]; // 오른쪽으로 이동 } // 후 처리: 만일 (마디를 짓다 != 보초병) 돌아오다 마디를 짓다; // 발견 // search_key가 트리에 포함되어 있지 않음: 돌아오다 NULL; } - 언급
- SearchWithSentinelnode 검색을 사용하면 R/O 속성이 손실된다.이것은 동시성이 있는 애플리케이션에서 그것은 보통 보초 절약량을 초과하는 노력인 뮤텍스에 의해 보호되어야 한다는 것을 의미한다.
- SearchWithSentinelnode는 중복의 허용오차를 지원하지 않는다.
- 보초로서 사용하기 위해서는 정확히 하나의 "노드"가 있어야 하지만, 그것에 대한 포인터가 엄청나게 많을 수도 있다.
참고 항목
참조
- ^ Ignatchenko, Sergey (1998), "STL Implementations and Thread Safety", C++ Report
