바이너리 검색 트리 알고리즘

Search(T,k) 
x<- root[T] 
while x != NULL and k != key[x] 
do 
    if k<key[x] 
    then x <- left[x] 
    else x <- right[x] 
    return x

방금 알고리즘으로 시작했고 종종 "<"이 표시되고 키 [x] 용어를 사용하여 누군가가 키 배열이 무엇인지 말해 줄 수 있습니까? x는 루트 값을 얻었고 인덱스로 사용됩니까? 나는 이것을 이해하지 못한다. 설명 해주십시오.바이너리 검색 트리 알고리즘

출처

2012-11-01 Pradit

여기 표기법이 조금 다릅니다. 'key [x]'의'x'는 색인이 아닙니다. 이것은 실제로 "노드 x에서 키 값"을 의미합니다. 마찬가지로'left [x]'와 right [x]'는''x''의 왼쪽과 오른쪽 노드를 의미합니다''-'는 단순히 할당 문입니다 – Aziz

객체 지향 표기법에 익숙하다면 'key [x]'를'x.key','left [x]'를'x.left' 등으로 읽을 수 있습니다. – hammar

@hammar, 객체 지향 표기법에서 C 스타일 표기법을 사용하지 마십시오. ? – Vovanium

의사 코드 (실제 언어가 아님)입니다.

이 경우 <-은 '할당 됨'을 의미하며 현대 언어에서는 =의 기능을 수행한다고 생각할 수 있습니다. key[x]은 구조체/객체 x의 key 속성의 약식입니다 (이는 x 클래스의 구성원임을 의미하지는 않으며지도와 같은 데이터 구조에서 검색 될 수 있음). 실제 구현은 알고리즘 구현 자 . 따라서 위 알고리즘으로 C로 작성 될 수

:..이 사이비 코드처럼 보이는

Node* Search(Tree* T, Key k) 
{ 
    Node* x = T->Root(); 
    while ((x != NULL) && (k != x->Key()) 
    { 
     if (k < x->Key()) 
      x = x->Left(); 
     else 
      x = x->Right(); 
    } 

    return x; 
}

출처

2012-11-01 03:45:52 James

명확한 설명 주셔서 감사합니다. – Pradit

자바에서 할당 연산자 =로 <- 생각 당신은 또한 때때로 볼이에 := 같다 다른 가짜 코드 변형.

x은 트리의 노드에 대한 포인터로 사용됩니다. key은 트리를 그릴 때 일반적으로 서클에서 찾은 값이며 left 및 right은 노드의 두 자식입니다.

편집 : 그 psuedo-code는 약간 떨어져 있습니다. 제임스의 모범이 좋다.

출처

2012-11-01 03:48:07 rchanley

바이너리 검색 트리 알고리즘

답변

관련 문제