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:
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.
- 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.
- 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?
