You are not logged in.

#1 2022-11-17 09:10:07

HikamJC
Member
From: Urbana, Illinois
Registered: 2022-06-28
Posts: 6

Threaded Binary Search Trees Advantage

We know that there are n+1 left and right pointers in a binary search tree with n nodes that contain null. To use the memory that contains null, we modify the binary tree as follows -
or every node z in the tree:

if left[z] = NULL, we put in left[z] the value of tree-predecessor(z) (i.e, a pointer to the node which contains the predecessor key),
if right[z] = NULL, we put in right[z] the value of tree-successor(z) (again, this is a pointer to the node which contains the successor key).

This type of tree is known as a threaded binary search tree, and the new linkages are known as threads.
And my question is, what are the primary benefits of Threaded Binary Search Trees? (in comparison to "Regular" binary search trees). I read this article that said that it is preferable to implement in-order traversal repeatedly rather than recursively.
Is that the only distinction? Is there any method to employ the threads? Is that a significant advantage? If so, please explain why. Recursive traversal also takes O(n) time.


Hello, my name is Hikam, and I'm a Prolific Java programmer with 4+ years of experience and a solid background in RESTful and JSP development. OddPointer is looking for efficient programming. In recent years, I have built an average of 10+ native Java apps per year. I'm also familiar with C++, C, and HTML, and am actively learning CSS and Python.

Offline

Board footer

Powered by FluxBB