// root 를 루트로 하는 트립에 새 노드 node 를 삽입한 뒤 결과 트립의// 루트를 반환한다.Node*insert(Node*root,Node*node){if(root==NULL)returnnode;// node 가 루트를 대체해야 한다: 해당 서브트립을 반으로 잘라// 각각 자손으로 한다if(root->priority<node->priority){NodePairsplitted=split(root,node->key);node->setLeft(splitted.first);node->setRight(splitted.second);returnnode;}elseif(node->key<root->key)root->setLeft(insert(root->left,node));elseroot->setRight(insert(root->right,node));returnroot;}
if 문으로 비교할 때 위에는 node->priority로 비교하고 또 아래 else if 에서는 node->key로 비교하는데요
설명에는 부모의 우선순위가 자식의 우선순위보다 높다고 되어있는데요 우선순위가 높다는건 key값도 크다는 건가요?
그럼 priority를 비교하든 key를 비교하든 결과가 같은 건가요?
트립은 힙과 이진 검색 트리를 합한 겁니다. priority는 노드 생성시 랜덤으로 값이 부여되고 key는 값으로 설정이 됩니다. 트립은 priority 기준으로는 힙구조를 유지하고 key기준으로는 이진 검색 트리를 유지합니다. 따라서 새 노드가 root를 대체할지 여부를 priority로 비교하고, 아니라면 루트의 왼쪽에 위치해야 할지 오른쪽에 위치해야 할지 key를 기준으로 비교합니다.
cjkis
알고책 714 밑 ~ 715책 윗 부분 코드 22.4보면
if 문으로 비교할 때 위에는 node->priority로 비교하고 또 아래 else if 에서는 node->key로 비교하는데요
설명에는 부모의 우선순위가 자식의 우선순위보다 높다고 되어있는데요 우선순위가 높다는건 key값도 크다는 건가요?
그럼 priority를 비교하든 key를 비교하든 결과가 같은 건가요?
9년 전