红黑树 - 如何找到节点的父节点？
在红黑树中，当旋转时，您需要知道谁是特定节点的父节点。 但是，该节点仅引用右子节点或左子节点。
我想给一个节点实例变量“parent”，但正是因为这个原因，我认为不值得这样做，而且每次旋转更改父引用也太复杂了。
public class Node {
private left;
private right;
private isRed;
private parent; //I don't think this is good idea
}
所以，我的解决方案是编写 findParent() 方法，使用搜索来查找父级。我想知道是否还有其他方法可以找到节点的父节点？
我的解决方案：
示例树：
50
/ \
25 75
如果您想找到节点 25 的父节点，请传递类似以下内容：
Node parent = findParent(Node25.value);
它会返回节点 50。
protected Node findParent(int val) {
if(root == null) {
return null;
}
Node current = root;
Node parent = current;
while(true) {
if(current.val == val) { //found
return parent;
}
if(current == null) { //not found
return null;
}
parent = current;
if(current.val > val) { //go left
current = current.left;
}
else { //go right
current = current.right;
}
}
}
In red-black tree, when rotate, you need to know who is the parent of particular node.
However, the node only has reference to either right or left child.
I was thinking to give a node instance variable "parent" but just for this reason I don't think it is worth doing so and also it would be too complicated to change parent reference per rotation.
public class Node {
private left;
private right;
private isRed;
private parent; //I don't think this is good idea
}
So, my solution is to write findParent() method that use search to find parent. I am wondering if there is any other way to find a node's parent?
My solution:
sample tree:
50
/ \
25 75
If you want to find parent of Node 25, you pass something like:
Node parent = findParent(Node25.value);
and it returns node50.
protected Node findParent(int val) {
if(root == null) {
return null;
}
Node current = root;
Node parent = current;
while(true) {
if(current.val == val) { //found
return parent;
}
if(current == null) { //not found
return null;
}
parent = current;
if(current.val > val) { //go left
current = current.left;
}
else { //go right
current = current.right;
}
}
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
父指针的使用是可选的。如果您放弃父指针，那么您将不得不使用递归编写插入/删除操作（递归方法调用将父信息保留在堆栈上），或者编写一个迭代版本，当它沿着树向下移动时，它会维护自己的父堆栈。
可以在这里找到关于红黑树的非常好的描述
http://adtinfo.org/
其中包括对rbtree 实现的数量，包括带和不带父指针的。
如果您确实想节省空间（这很公平），可以在这里找到 rbtree 实现的非常精彩的描述
http://www.eternallyconfuzzled.com/tuts/datastructs/jsw_tut_rbtree.aspx
如果用于插入/删除实现，您所描述的用于搜索节点父节点的方法将非常低效。使用指针或使用递归。
The use of a parent pointer is optional. If you forgo the parent pointer then you will have to write insert/delete operations using recursion (the recursive method calls preserve the parent information on the stack) or write an iterative version which maintains its own stack of parents as it moves down the tree.
A very good description of red-black trees can be found here
http://adtinfo.org/
That includes descriptions of a number of rbtree implementations including with and without parent pointers.
If you do want to save on space (and that is fair enough) a really excellent description of an rbtree implementation can be found here
http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx
The method you have described for searching for a node's parent would be very inefficient if used by the insert/delete implementations. Use a pointer or use recursion.
让你的节点有一个
parent引用需要每个节点一个额外的指针/引用。将此与每当需要知道给定节点的父节点时需要遍历树进行比较。之间的权衡
我认为这两个选项之间的选择有些主观，但就我个人而言，我会选择简单地跟踪父节点参考。
作为您的参考点，
java.util.TreeMap被实现为红黑树，其中Entry节点包含left、< code>right 和parent引用。Having your nodes have a
parentreference requires one extra pointer/reference per node. Compare this with needing to traverse the tree whenever you need to know the parent for a given node.This is then a trade-off between
I think that the choice between these two options is somewhat subjective but personally I would choose to simply keep track of the
parentreferences.As a point of reference for you,
java.util.TreeMapis implemented as a Red-Black tree whichEntrynodes that containleft,right, andparentreferences.当您遍历树以到达枢轴节点时，您可以缓存前一个父节点，或者如果您需要多级“撤消”，您可以将每个遍历的节点缓存到堆栈上。
该缓存将是旋转算法的本地变量，因此它不需要树中的任何更多空间或昂贵的额外遍历。
As you traverse the tree to get to your pivot node you can cache the previous parent or if you need more than one level of "undo" you could cache each traversed node on to a stack.
This cache would be a variable local to your rotation algorithm so it wouldn't require any more space in the tree or expensive additional traversals.
存储父级绝对比查找它更好。更新父引用并不那么复杂。
It's definitely better to store the parent than to look it up. Updating parent reference is not that complex.
除了父指针和再次查询父级之外，另一个解决方案是维护祖先堆栈。
假设有人希望将 23 插入到以下树中：
红黑树
通常插入的算法是:
如果 23 在树中，则查找 23 所在的节点
如果 23 已经存在，则返回失败
如果 23 不存在，则将其放在那里。
根据需要运行重新平衡/着色例程。
现在，要使用堆栈方法，您需要分配一个足够大的堆栈来支持树的每一层一个节点（我认为 2 * Ceiling(Log2(count)) + 2）应该可以满足您的要求。您甚至可以保留分配用于插入或删除的堆栈，并在开始插入时清除它。
所以——看看根源。将其推入堆栈。 23 大于根中的值，所以向右走。现在将节点当前节点（值 21）压入堆栈。如果 23 在树中，它一定在当前节点的右侧。但当前节点右侧的节点是空哨兵。因此，该空标记应该替换为具有您的值的节点。父级是堆栈顶部的项目（最近推送的），祖父级是下一个......等等。既然你似乎正在学习......Java为你提供了一个堆栈接口，所以你不需要开发自己的堆栈来执行此操作。就用他们的吧。
至于这是否比父指针方法更好，这对我来说似乎是有争议的——为了简单性和消除维护辅助数据结构或广泛使用递归的需要，我倾向于使用父指针方法。也就是说，在应用重新平衡/着色例程时，任何一种方法都比查询当前节点的父节点更好。
Another solution, besides parent pointers and querying the parent all over again is to maintain an ancestor stack.
Suppose someone wishes to insert 23 into the following tree:
Red Black Tree
Generally the algorithm to insert is:
Find node where 23 would be if it is in the tree
If 23 is already there, return failure
If 23 is not already there, put it there.
Run your re-balancing/coloring routine as needed.
Now, to use the stack approach, you allocate a stack big enough to support one node per level of your tree (I think 2 * Ceiling(Log2(count)) + 2) should have you covered. You could even keep a stack allocated for insertion or deletion and just clear it whenever you start an insertion.
So -- Look at the root. Push it onto the stack. 23 is greater than value in the root, so go right. Now push node current node (value 21) onto the stack. If 23 is in the tree, it must be to the right of current node. But the node to the right of the current node is a null-sentinel. Thus, that null-sentinel should be replaced with a node with your value. The parent is the item on the top of the stack (most recently pushed), the grandparent is next in line ... etc. Since you seem to be learning ... Java supplies a stack interface for you so you won't need to develop your own stack to do this. Just use theirs.
As to whether this is better than the parent pointer approach, that seems debatable to me -- I would lean to the parent pointer approach for simplicity and elimination of the need to maintain an ancillary data structure or use recursion extensively. That said, either approach is better than querying the parent of the current node as you apply your re-balancing/coloring routine.