Considering binary search trees(of any kind) following pseudo code will
help, a successor of a node having a right child is the minimum element in
the subtree rooted at that node's right child, and if that node does not
have any right child, then you have to find the successor that would be one
of the node's ancestors, this pseudo code is taken from CLRS(with a little
change):
NODE successor(NODE x)
If x.right != null
Return minimum(x.right)
Y = x.parent
While (y != null && x = y.right)
X = y
Y = y.parent
Return y
NODE minimum(NODE x)
While(x.left != null)
X = x.left
Return x
Considering the case your tree is a multi-way search tree(like a 2-3-4 tree
or a B-tree In general) the procedure would be like the one presented here,
but also you have to consider existence of key (K+1) inside a node X to
determine the successor both in X and X's ancestors.
From: algogeeks@googlegroups.com [mailto:algoge...@googlegroups.com] On
Behalf Of Vinay Pandey
Sent: Friday, February 13, 2009 9:18 AM
To: algogeeks@googlegroups.com
Subject: [algogeeks] Re: [algogeeks]
which tree?
On Tue, Feb 10, 2009 at 7:01 AM, praba garan <prabagara...@gmail.com> wrote:
how to find the successor of an element in a tree ??
thank u
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
