开发者

What does this pseudo code mean?- Binary Search Tree Successor Function

开发者 https://www.devze.com 2022-12-21 05:56 出处:网络
if right[x] != NIL then return TREE-MINIMUM(right[x]) y<-p[x] while y!= NIL and x = right[y] do x<-y
if right[x] != NIL
 then return TREE-MINIMUM(right[x])

 y<-p[x]
 while y!= NIL and x = right[y]
  do x<-y
  y<-p[y]
 return y

I know what "if right[x] != NIL then return tree-min" means and I've translated it to:

if(p->RChild) return fMinValue(p->RChild);//returns the min value of the sub-开发者_运维知识库tree starting at the right child node of p

The rest I'm having trouble understanding.


<- is most likely the assignment operator. p I would guess is parent. What else are you confused about?


Here p[] almost certainly means "the parent node of". You're working on node x, so p[x] means "the parent of the current node" (just like right[x] means "the right-hand child of the current node").

The <- notation is assignment. Like = in c-like languages.

The second part of the algorithm presented here walks up the tree looking for the first time you ascended a left link instead of a right one. But I'm not sure that I would describe this as a successor function.

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号