0
$\begingroup$

I needed to implement a priority queue for a project I'm working on and had this idea. In a priority queue BST implementation wouldn't it be more efficient if the poll node pointed to its parent since it's guaranteed to not have a left child? This would make polling faster since we don't have to traverse the tree to find the poll node's parent and link it with the poll node's right child. for example:

enter image description here

poll():

when we call poll() here it'll go to the poll's parent (5) and make its left child the poll's right child, and then go to the new poll node (4) and make it point to its new parent. this is an O(1) operation.

Worst case is the poll's right child has left children of its own, in which case we'll have to traverse the leftmost node in that subtree and make it point to its parent and assign it as the poll node. Now it becomes O(log(n)) but faster than regular traversal since we're not starting from the root.

add():

add() is similar to a regular BST except for two optimizations.

  1. If the new data is lower than the poll node's data then make it the poll node's left child and have it point to its parent (old poll node) and assign the newly added node as the poll node. this is an O(1) operation.
  2. If the new data is lower than the poll node's right child's data then insert starting from that subtree. This is an O(log(n)) operation but is faster since we're not starting from the root.

Other than that insert is like a normal BST.

Does this data structure make sense to use in practice?

$\endgroup$
3
  • 1
    $\begingroup$ en.wikipedia features threaded binary trees. $\endgroup$
    – greybeard
    Commented Jul 26, 2022 at 6:47
  • $\begingroup$ "Did i invent a new data structure" No. It still is a binary tree as it stores the elements in that way. $\endgroup$
    – Rinkesh P
    Commented Jul 26, 2022 at 6:50
  • 1
    $\begingroup$ The answer to your question requires a thorough discussion of the efficiency of the various operations, in front pf practical use cases. All I can say is that such a structure does not seem to be much in use. $\endgroup$
    – user16034
    Commented Jul 26, 2022 at 8:12

1 Answer 1

0
$\begingroup$

it's a small optimization for the purpose of puling out the left most node not enough to call it a new data structure IMO.

There are is another time when this optimization is a pessimization; If the left-most node you remove doesn't have any children then it's parent must now point to its own parent. This requires a traversal from root.

Also this doesn't help in keeping the tree balanced for which you might end up traversing back up further than your discount parent pointer can get you anyway.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.