查找二叉堆的最后一个元素

发布于 2024-07-12 05:39:21 字数 1551 浏览 12 评论 0原文

引用维基百科

使用 传统二叉树数据结构 实现二叉堆。 有 寻找相邻的问题 最后一层的元素 添加元素时的二叉堆 这是可以解决的 从算法上...

对于这样的算法如何工作有什么想法吗?

我无法找到有关此问题的任何信息,因为大多数二进制堆都是使用数组实现的。

任何帮助表示赞赏。


最近,我注册了一个 OpenID 帐户,但无法编辑我的初始帖子或评论答案。 这就是为什么我通过这个答案做出回应。 非常遗憾。


引用 Mitch Wheat 的话:

@Yse:你的问题是“我如何找到 二叉堆的最后一个元素”?

是的,确实如此。 或者更准确地说,我的问题是:“如何找到非基于数组的二进制堆的最后一个元素?”。

引用Suppressingfire:

您所处的环境有吗? 问这个问题? (即,有没有 你想要解决的一些具体问题 解决了吗?)

如上所述,我想知道一种“查找非基于数组的二进制堆的最后一个元素”的好方法,这是插入和删除节点所必需的。

引用罗伊的话:

我觉得最容易理解的是 只需使用普通的二叉树 结构(使用 pRoot 和 Node 定义为[数据,pLeftChild, pRightChild])并添加两个额外的 指针(pInsertionNode 和 pLastNode)。 pInsertionNode 和 pLastNode 都将在期间更新 插入和删除子例程 使数据保持最新状态 内部结构发生变化。 这 为 O(1) 提供对两个插入的访问 点和结构的最后一个节点。

是的,这应该有效。 如果我没有记错的话,当插入节点和最后一个节点的位置由于删除/插入而更改为另一个子树时,找到插入节点和最后一个节点可能会有点棘手。 但我会尝试一下。

引用 Zach Scrivena 的话:

如何执行深度优先 搜索...

是的,这将是一个好方法。 我也来尝试一下。

我仍然想知道是否有一种方法可以“计算”最后一个节点和插入点的位置。 具有 N 个节点的二叉堆的高度可以通过取大于 N 的最小的 2 次方的对数(以 2 为底)来计算。也许也可以计算最深层的节点数。 然后也许可以确定如何遍历堆才能到达插入点或要删除的节点。

quoting Wikipedia:

It is perfectly acceptable to use a
traditional binary tree data structure
to implement a binary heap. There is
an issue with finding the adjacent
element on the last level on the
binary heap when adding an element
which can be resolved
algorithmically...

Any ideas on how such an algorithm might work?

I was not able to find any information about this issue, for most binary heaps are implemented using arrays.

Any help appreciated.


Recently, I have registered an OpenID account and am not able to edit my initial post nor comment answers. That's why I am responding via this answer. Sorry for this.


quoting Mitch Wheat:

@Yse: is your question "How do I find
the last element of a binary heap"?

Yes, it is.
Or to be more precise, my question is: "How do I find the last element of a non-array-based binary heap?".

quoting Suppressingfire:

Is there some context in which you're
asking this question? (i.e., is there
some concrete problem you're trying to
solve?)

As stated above, I would like to know a good way to "find the last element of a non-array-based binary heap" which is necessary for insertion and deletion of nodes.

quoting Roy:

It seems most understandable to me to
just use a normal binary tree
structure (using a pRoot and Node
defined as [data, pLeftChild,
pRightChild]) and add two additional
pointers (pInsertionNode and
pLastNode). pInsertionNode and
pLastNode will both be updated during
the insertion and deletion subroutines
to keep them current when the data
within the structure changes. This
gives O(1) access to both insertion
point and last node of the structure.

Yes, this should work. If I am not mistaken, it could be a little bit tricky to find the insertion node and the last node, when their locations change to another subtree due to an deletion/insertion. But I'll give this a try.

quoting Zach Scrivena:

How about performing a depth-first
search...

Yes, this would be a good approach. I'll try that out, too.

Still I am wondering, if there is a way to "calculate" the locations of the last node and the insertion point. The height of a binary heap with N nodes can be calculated by taking the log (of base 2) of the smallest power of two that is larger than N. Perhaps it is possible to calculate the number of nodes on the deepest level, too. Then it was maybe possible to determine how the heap has to be traversed to reach the insertion point or the node for deletion.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(6

°如果伤别离去 2024-07-19 05:39:21

基本上,引用的语句是指解决在堆中插入和删除数据元素的位置的问题。 为了保持二叉堆的“形状属性”,堆的最低层必须始终从左到右填充,不留任何空节点。 为了保持二叉堆的平均插入和删除时间为 O(1),您必须能够确定下一次插入的位置以及用于删除根节点的最低级别上最后一个节点的位置,两者都在恒定的时间内。

对于存储在数组中的二进制堆(其隐式的压缩数据结构,如维基百科条目中所述),这很容易。 只需将最新的数据成员插入到数组的末尾,然后将其“冒泡”到位(遵循堆规则)。 或者用数组中的最后一个元素替换根,“冒泡”进行删除。 对于数组存储中的堆,堆中的元素数量是一个隐式指针,指向要插入下一个数据元素的位置以及在哪里找到要用于删除的最后一个元素。

对于存储在树结构中的二叉堆来说,这个信息并不那么明显,但是因为它是一棵完全二叉树,所以可以计算出来。 例如,在具有 4 个元素的完全二叉树中,插入点始终是根节点左子节点的右子节点。 用于删除的节点始终是根节点的左子节点的左子节点。 对于任何给定的任意树大小,树将始终具有特定的形状,并具有明确定义的插入点和删除点。 因为树是一个“完全二叉树”,对于任何给定的大小都有特定的结构,所以很有可能在 O(1) 时间内计算出插入/删除的位置。 然而,问题是,即使您知道它的结构位置,您也不知道该节点在内存中的位置。 因此,您必须遍历树才能到达给定节点,这是一个 O(log n) 过程,使所有插入和删除操作的时间最少为 O(log n),从而破坏了通常所需的 O(1) 行为。 由于注意到的遍历问题,任何搜索(“深度优先”或其他搜索)都将至少为 O(log n),并且由于半排序堆的随机性质,通常为 O(n)。

诀窍是能够通过增强数据结构(“线程化”树,如在维基百科文章)或使用其他指针。

在我看来,最容易理解的实现是使用一个普通的简单二叉树结构(使用定义为 [data, pParent, pLeftChild, pRightChild] 的 pRoot 和 Node ),并且具有较低的内存和额外的编码开销添加两个附加指针(pInsert 和 pLastNode)。 pInsert 和 pLastNode 都将在插入和删除子例程期间更新,以便在结构内的数据发生更改时保持它们最新。 此实现提供对结构的插入点和最后一个节点的 O(1) 访问,并且应该允许在插入和删除中保留总体 O(1) 行为。 实现的成本是两个额外的指针和插入/删除子例程中的一些少量额外代码(也称为最小)。

编辑:为 O(1) insert() 添加伪代码

这是平均 O(1) 的插入子例程的伪代码:

define Node = [T data, *pParent, *pLeft, *pRight]

void insert(T data)
{
    do_insertion( data );   // do insertion, update count of data items in tree

    # assume: pInsert points node location of the tree that where insertion just took place
    #   (aka, either shuffle only data during the insertion or keep pInsert updated during the bubble process)

    int N = this->CountOfDataItems + 1;     # note: CountOfDataItems will always be > 0 (and pRoot != null) after an insertion

    p = new Node( <null>, null, null, null);        // new empty node for the next insertion

    # update pInsert (three cases to handle)
    if ( int(log2(N)) == log2(N) )
        {# #1 - N is an exact power of two
        # O(log2(N))
        # tree is currently a full complete binary tree ("perfect")
        # ... must start a new lower level
        # traverse from pRoot down tree thru each pLeft until empty pLeft is found for insertion
        pInsert = pRoot;
        while (pInsert->pLeft != null) { pInsert = pInsert->pLeft; }    # log2(N) iterations
        p->pParent = pInsert;
        pInsert->pLeft = p;
        }
    else if ( isEven(N) )
        {# #2 - N is even (and NOT a power of 2)
        # O(1)
        p->pParent = pInsert->pParent;
        pInsert->pParent->pRight = p;
        }
    else 
        {# #3 - N is odd
        # O(1)
        p->pParent = pInsert->pParent->pParent->pRight;
        pInsert->pParent->pParent->pRight->pLeft = p;
        }
    pInsert = p;

    // update pLastNode
    // ... [similar process]
}

因此,insert(T) 的时间复杂度为 O(1)平均:在所有情况下都精确地为 O(1),除非树必须在 O(log N) 时增加一级,这会在每次 log N 插入时发生(假设没有删除)。 添加另一个指针 (pLeftmostLeaf) 可以使 insert() 对于所有情况都是 O(1),并避免交替插入和插入的可能病理情况。 完整二叉树中的删除。 (添加 pLeftmost 留作练习[相当简单]。)

Basically, the statement quoted refers to the problem of resolving the location for insertion and deletion of data elements into and from the heap. In order to maintain "the shape property" of a binary heap, the lowest level of the heap must always be filled from left to right leaving no empty nodes. To maintain the average O(1) insertion and deletion times for the binary heap, you must be able to determine the location for the next insertion and the location of the last node on the lowest level to use for deletion of the root node, both in constant time.

For a binary heap stored in an array (with its implicit, compacted data structure as explained in the Wikipedia entry), this is easy. Just insert the newest data member at the end of the array and then "bubble" it into position (following the heap rules). Or replace the root with the last element in the array "bubbling down" for deletions. For heaps in array storage, the number of elements in the heap is an implicit pointer to where the next data element is to be inserted and where to find the last element to use for deletion.

For a binary heap stored in a tree structure, this information is not as obvious, but because it's a complete binary tree, it can be calculated. For example, in a complete binary tree with 4 elements, the point of insertion will always be the right child of the left child of the root node. The node to use for deletion will always be the left child of the left child of the root node. And for any given arbitrary tree size, the tree will always have a specific shape with well defined insertion and deletion points. Because the tree is a "complete binary tree" with a specific structure for any given size, it is very possible to calculate the location of insertion/deletion in O(1) time. However, the catch is that even when you know where it is structurally, you have no idea where the node will be in memory. So, you have to traverse the tree to get to the given node which is an O(log n) process making all inserts and deletions a minimum of O(log n), breaking the usually desired O(1) behavior. Any search ("depth-first", or some other) will be at least O(log n) as well because of the traversal issue noted and usually O(n) because of the random nature of the semi-sorted heap.

The trick is to be able to both calculate and reference those insertion/deletion points in constant time either by augmenting the data structure ("threading" the tree, as mention in the Wikipedia article) or using additional pointers.

The implementation which seems to me to be the easiest to understand, with low memory and extra coding overhead, is to just use a normal simple binary tree structure (using a pRoot and Node defined as [data, pParent, pLeftChild, pRightChild]) and add two additional pointers (pInsert and pLastNode). pInsert and pLastNode will both be updated during the insertion and deletion subroutines to keep them current when the data within the structure changes. This implementation gives O(1) access to both insertion point and last node of the structure and should allow preservation of overall O(1) behavior in both insertion and deletions. The cost of the implementation is two extra pointers and some minor extra code in the insertion/deletion subroutines (aka, minimal).

EDIT: added pseudocode for an O(1) insert()

Here is pseudo code for an insert subroutine which is O(1), on average:

define Node = [T data, *pParent, *pLeft, *pRight]

void insert(T data)
{
    do_insertion( data );   // do insertion, update count of data items in tree

    # assume: pInsert points node location of the tree that where insertion just took place
    #   (aka, either shuffle only data during the insertion or keep pInsert updated during the bubble process)

    int N = this->CountOfDataItems + 1;     # note: CountOfDataItems will always be > 0 (and pRoot != null) after an insertion

    p = new Node( <null>, null, null, null);        // new empty node for the next insertion

    # update pInsert (three cases to handle)
    if ( int(log2(N)) == log2(N) )
        {# #1 - N is an exact power of two
        # O(log2(N))
        # tree is currently a full complete binary tree ("perfect")
        # ... must start a new lower level
        # traverse from pRoot down tree thru each pLeft until empty pLeft is found for insertion
        pInsert = pRoot;
        while (pInsert->pLeft != null) { pInsert = pInsert->pLeft; }    # log2(N) iterations
        p->pParent = pInsert;
        pInsert->pLeft = p;
        }
    else if ( isEven(N) )
        {# #2 - N is even (and NOT a power of 2)
        # O(1)
        p->pParent = pInsert->pParent;
        pInsert->pParent->pRight = p;
        }
    else 
        {# #3 - N is odd
        # O(1)
        p->pParent = pInsert->pParent->pParent->pRight;
        pInsert->pParent->pParent->pRight->pLeft = p;
        }
    pInsert = p;

    // update pLastNode
    // ... [similar process]
}

So, insert(T) is O(1) on average: exactly O(1) in all cases except when the tree must be increased by one level when it is O(log N), which happens every log N insertions (assuming no deletions). The addition of another pointer (pLeftmostLeaf) could make insert() O(1) for all cases and avoids the possible pathologic case of alternating insertion & deletion in a full complete binary tree. (Adding pLeftmost is left as an exercise [it's fairly easy].)

忆沫 2024-07-19 05:39:21

我第一次参加stackoverflow。

是的,扎克·斯克里维纳(Zach Scrivena)的上述回答(上帝,我不知道如何正确地指代其他人,抱歉)是正确的。 如果我们给出节点数,我想添加的是一种简化的方法。

基本思想是:

给定这棵满二叉树中的节点数 N,进行“N % 2”计算并将结果压入堆栈。 继续计算直到N == 1。然后将结果弹出。 结果1表示右,0表示左。 序列是从根位置到目标位置的路线。

示例:

树现在有 10 个节点,我想在位置 11 处插入另一个节点。如何路由它?

11 % 2 = 1  --> right    (the quotient is 5, and push right into stack)
 5 % 2 = 1  --> right    (the quotient is 2, and push right into stack)
 2 % 2 = 0  --> left     (the quotient is 1, and push left into stack. End)

然后出栈:left -> 右-> 正确的。 这是从根开始的路径。

My first time to participate in stack overflow.

Yes, the above answer by Zach Scrivena (god I don't know how to properly refer to other people, sorry) is right. What I want to add is a simplified way if we are given the count of nodes.

The basic idea is:

Given the count N of nodes in this full binary tree, do "N % 2" calculation and push the results into a stack. Continue the calculation until N == 1. Then pop the results out. The result being 1 means right, 0 means left. The sequence is the route from root to target position.

Example:

The tree now have 10 nodes, I want insert another node at position 11. How to route it?

11 % 2 = 1  --> right    (the quotient is 5, and push right into stack)
 5 % 2 = 1  --> right    (the quotient is 2, and push right into stack)
 2 % 2 = 0  --> left     (the quotient is 1, and push left into stack. End)

Then pop the stack: left -> right -> right. This is the path from the root.

做个ˇ局外人 2024-07-19 05:39:21

您可以使用二叉堆大小的二进制表示来查找最后一个节点的位置,时间复杂度为 O(log N)。 可以存储并增加大小,这将花费 O(1) 时间。 这背后的基本概念是二叉树的结构。

假设我们的堆大小是 7。7 的二进制表示是“111”。 现在,请记住始终省略第一位。 所以,现在我们只剩下“11”。 从左到右阅读。 该位为“1”,因此,转到根节点的右子节点。 那么左边的字符串是“1”,第一位是“1”。 因此,再次转到您所在的当前节点的右子节点。 由于您不再有需要处理的位,这表明您已到达最后一个节点。 因此,该过程的原始工作是将堆的大小转换为位。 省略第一位。 根据最左边的位,如果为'1'则转到当前节点的右子节点,如果为'0'则转到当前节点的左子节点。

正如您总是到二叉树的最后一样,此操作始终需要 O(log N) 时间。 这是查找最后一个节点的简单而准确的过程。

第一次读你可能不明白。 尝试在论文中针对二进制堆的不同值使用此方法,我相信您会得到其背后的直觉。 我相信这些知识足以解决你的问题,如果你想要更多的数字解释,你可以参考我的博客

希望我的回答对您有所帮助,如果有帮助,请告诉我......! ☺

You could use the binary representation of the size of the Binary Heap to find the location of the last node in O(log N). The size could be stored and incremented which would take O(1) time. The the fundamental concept behind this is the structure of the binary tree.

Suppose our heap size is 7. The binary representation of 7 is, "111". Now, remember to always omit the first bit. So, now we are left with "11". Read from left-to-right. The bit is '1', so, go to the right child of the root node. Then the string left is "1", the first bit is '1'. So, again go to the right child of the current node you are at. As you no longer have bits to process, this indicates that you have reached the last node. So, the raw working of the process is that, convert the size of the heap into bits. Omit the first bit. According to the leftmost bit, go to the right child of the current node if it is '1', and to the left child of the current node if it is '0'.

As you always to to the very end of the binary tree this operation always takes O(log N) time. This is a simple and accurate procedure to find the last node.

You may not understand it in the first reading. Try working this method on the paper for different values of Binary Heap, I'm sure you'll get the intuition behind it. I'm sure this knowledge is enough to solve your problem, if you want more explanation with figures, you can refer to my blog.

Hope my answer has helped you, if it did, let me know...! ☺

软甜啾 2024-07-19 05:39:21

如何执行深度优先搜索,先访问左子节点,然后再访问右子节点,以确定树的高度。 此后,您遇到的第一片深度较短的叶子,或者缺少子节点的父节点将指示您在“冒泡”之前应将新节点放置在何处。


上述深度优先搜索 (DFS) 方法并不假设您知道树中的节点总数。 如果此信息可用,那么我们可以利用完全二叉树的属性快速“放大”到所需的位置:

N为总和树中的节点数,H 是树的高度。

(N,H) 的一些值为 (1,0)、(2,1)、(3,1)、(4,2)、... , (7,2), (8, 3)。
两者相关的一般公式为 H = ceil[log2(N+1)] - 1。
现在,只给定N,我们希望以最少的步数从根遍历到新节点的位置,即没有任何“回溯”。
我们首先计算高度 H = ceil[log2(N完美二叉树)中的节点总数 M >+1)] - 1,即 M = 2^(H+1) - 1。

如果 N == M,那么我们的树就是完美,新节点应该添加到新的级别中。 这意味着我们可以简单地执行 DFS(先左后右),直到到达第一个叶子; 新节点成为该叶子节点的左子节点。 故事结局。

然而,如果N < M,那么我们的树的最后一层仍然有空位,新节点应该添加到最左边的空位。
树最后一层的节点数仅为 (N - 2^H + 1)。
这意味着新节点在最后一层从左侧开始 X = (N - 2^H + 2) 位置。

现在,要从根部到达那里,您需要在每个级别进行正确的转弯(L vs R),以便您最终到达最后一个级别的点X。 在实践中,您可以在每个级别进行少量计算来确定转弯。 然而,我认为下表显示了大局和相关模式,而没有陷入算术的泥沼(您可能会认为这是 均匀分布的算术编码):

0 0 0 0 0 X 0 0 <--- represents the last level in our tree, X marks the spot!
          ^
L L L L R R R R <--- at level 0, proceed to the R child
L L R R L L R R <--- at level 1, proceed to the L child
L R L R L R L R <--- at level 2, proceed to the R child 
          ^                      (which is the position of the new node)
          this column tells us
          if we should proceed to the L or R child at each level

编辑:添加了关于如何在假设我们知道树中节点总数的情况下以最短的步骤到达新节点的描述。

How about performing a depth-first search, visiting the left child before the right child, to determine the height of the tree. Thereafter, the first leaf you encounter with a shorter depth, or a parent with a missing child would indicate where you should place the new node before "bubbling up".


The depth-first search (DFS) approach above doesn't assume that you know the total number of nodes in the tree. If this information is available, then we can "zoom-in" quickly to the desired place, by making use of the properties of complete binary trees:

Let N be the total number of nodes in the tree, and H be the height of the tree.

Some values of (N,H) are (1,0), (2,1), (3,1), (4,2), ..., (7,2), (8, 3).
The general formula relating the two is H = ceil[log2(N+1)] - 1.
Now, given only N, we want to traverse from the root to the position for the new node, in the least number of steps, i.e. without any "backtracking".
We first compute the total number of nodes M in a perfect binary tree of height H = ceil[log2(N+1)] - 1, which is M = 2^(H+1) - 1.

If N == M, then our tree is perfect, and the new node should be added in a new level. This means that we can simply perform a DFS (left before right) until we hit the first leaf; the new node becomes the left child of this leaf. End of story.

However, if N < M, then there are still vacancies in the last level of our tree, and the new node should be added to the leftmost vacant spot.
The number of nodes that are already at the last level of our tree is just (N - 2^H + 1).
This means that the new node takes spot X = (N - 2^H + 2) from the left, at the last level.

Now, to get there from the root, you will need to make the correct turns (L vs R) at each level so that you end up at spot X at the last level. In practice, you would determine the turns with a little computation at each level. However, I think the following table shows the big picture and the relevant patterns without getting mired in the arithmetic (you may recognize this as a form of arithmetic coding for a uniform distribution):

0 0 0 0 0 X 0 0 <--- represents the last level in our tree, X marks the spot!
          ^
L L L L R R R R <--- at level 0, proceed to the R child
L L R R L L R R <--- at level 1, proceed to the L child
L R L R L R L R <--- at level 2, proceed to the R child 
          ^                      (which is the position of the new node)
          this column tells us
          if we should proceed to the L or R child at each level

EDIT: Added a description on how to get to the new node in the shortest number of steps assuming that we know the total number of nodes in the tree.

软的没边 2024-07-19 05:39:21

如果您没有参考父母的解决方案!
要找到下一个节点的正确位置,您需要处理 3 种情况

  • 情况 (1) 树级别已完成 Log2(N)
  • 情况 (2) 树节点数为偶数
  • 情况 (3) 树节点数为奇数

插入:

void Insert(Node root,Node n)
{
Node parent = findRequiredParentToInsertNewNode (root);
if(parent.left == null)
parent.left = n;
else
parent.right = n;
}

查找节点以便插入它

void findRequiredParentToInsertNewNode(Node root){

Node last = findLastNode(root);

 //Case 1 
 if(2*Math.Pow(levelNumber) == NodeCount){
     while(root.left != null)
      root=root.left;
  return root;
 }
 //Case 2
 else if(Even(N)){
   Node n =findParentOfLastNode(root ,findParentOfLastNode(root ,last));
 return n.right;
 }
//Case 3
 else if(Odd(N)){
  Node n =findParentOfLastNode(root ,last);
 return n;
 }

}

要查找最后一个节点,您需要执行 BFS(广度优先搜索)并获取队列中的最后一个元素

 Node findLastNode(Node root)
 {
     if (root.left == nil)
         return root

     Queue q = new Queue();

     q.enqueue(root);
     Node n = null;

     while(!q.isEmpty()){
      n = q.dequeue();
     if ( n.left != null )
         q.enqueue(n.left);
     if ( n.right != null )
         q.enqueue(n.right);
        }
   return n;
}

查找最后一个节点的父节点,以便将节点设置为 null,以防替换为移除案例中的根

 Node findParentOfLastNode(Node root ,Node lastNode)
{
    if(root == null)
        return root;

    if( root.left == lastNode || root.right == lastNode )
        return root;

    Node n1= findParentOfLastNode(root.left,lastNode);
    Node n2= findParentOfLastNode(root.left,lastNode);

    return n1 != null ? n1 : n2;
}

Solution in case you don't have reference to parent !!!
To find the right place for next node you have 3 cases to handle

  • case (1) Tree level is complete Log2(N)
  • case (2) Tree node count is even
  • case (3) Tree node count is odd

Insert:

void Insert(Node root,Node n)
{
Node parent = findRequiredParentToInsertNewNode (root);
if(parent.left == null)
parent.left = n;
else
parent.right = n;
}

Find the parent of the node in order to insert it

void findRequiredParentToInsertNewNode(Node root){

Node last = findLastNode(root);

 //Case 1 
 if(2*Math.Pow(levelNumber) == NodeCount){
     while(root.left != null)
      root=root.left;
  return root;
 }
 //Case 2
 else if(Even(N)){
   Node n =findParentOfLastNode(root ,findParentOfLastNode(root ,last));
 return n.right;
 }
//Case 3
 else if(Odd(N)){
  Node n =findParentOfLastNode(root ,last);
 return n;
 }

}

To find the last node you need to perform a BFS (breadth first search) and get the last element in the queue

 Node findLastNode(Node root)
 {
     if (root.left == nil)
         return root

     Queue q = new Queue();

     q.enqueue(root);
     Node n = null;

     while(!q.isEmpty()){
      n = q.dequeue();
     if ( n.left != null )
         q.enqueue(n.left);
     if ( n.right != null )
         q.enqueue(n.right);
        }
   return n;
}

Find the parent of the last node in order to set the node to null in case replacing with the root in removal case

 Node findParentOfLastNode(Node root ,Node lastNode)
{
    if(root == null)
        return root;

    if( root.left == lastNode || root.right == lastNode )
        return root;

    Node n1= findParentOfLastNode(root.left,lastNode);
    Node n2= findParentOfLastNode(root.left,lastNode);

    return n1 != null ? n1 : n2;
}
药祭#氼 2024-07-19 05:39:21

我知道这是一个旧线程,但我一直在寻找同一问题的答案。 但我无法承担 o(log n) 解决方案,因为我必须在几秒钟内找到最后一个节点数千次。 我确实有一个 O(log n) 算法,但由于执行此操作的次数太多,我的程序正在爬行。 经过深思熟虑,我终于找到了解决这个问题的办法。 不确定是否有人觉得这很有趣。

该解决方案的搜索时间复杂度为 O(1)。 对于插入来说,它肯定小于 O(log n),尽管我不能说它是 O(1)。

只是想补充一点,如果有兴趣,我也可以提供我的解决方案。
解决方案是将二叉堆中的节点添加到队列中。 每个队列节点都有前指针和后指针。我们不断从左到右向队列末尾添加节点,直到到达二叉堆中的最后一个节点。 此时,二叉堆中的最后一个节点将位于队列的末尾。
每次我们需要找到最后一个节点时,我们都会从后面出队,倒数第二个现在成为树中的最后一个节点。
当我们想要插入时,我们从后面向后搜索第一个可以插入的节点并将其放在那里。 它不完全是 O(1),但显着减少了运行时间。

I know this is an old thread but i was looking for a answer to the same question. But i could not afford to do an o(log n) solution as i had to find the last node thousands of times in a few seconds. I did have a O(log n) algorithm but my program was crawling because of the number of times it performed this operation. So after much thought I did finally find a fix for this. Not sure if anybody things this is interesting.

This solution is O(1) for search. For insertion it is definitely less than O(log n), although I cannot say it is O(1).

Just wanted to add that if there is interest, i can provide my solution as well.
The solution is to add the nodes in the binary heap to a queue. Every queue node has front and back pointers.We keep adding nodes to the end of this queue from left to right until we reach the last node in the binary heap. At this point, the last node in the binary heap will be in the rear of the queue.
Every time we need to find the last node, we dequeue from the rear,and the second-to-last now becomes the last node in the tree.
When we want to insert, we search backwards from the rear for the first node where we can insert and put it there. It is not exactly O(1) but reduces the running time dramatically.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文