Temporal analysis of a binary search tree search algorithm

Question

The following is an iterative algorithm for moving the binary search tree in order (first left child , then parent , finally right child ) without using a stack:

(Idea: the whole idea is to find the leftmost child of the tree and find the successor of the node at hand each time and print its value until there is no more node.)

 void In-Order-Traverse(Node root){ Min-Tree(root); //finding left-most child Node current = root; while (current != null){ print-on-screen(current.key); current = Successor(current); } return; } Node Min-Tree(Node root){ // find the leftmost child Node current = root; while (current.leftChild != null) current = current.leftChild; return current; } Node Successor(Node root){ if (root.rightChild != null) // if root has a right child ,find the leftmost child of the right sub-tree return Min-Tree(root.rightChild); else{ current = root; while (current.parent != null && current.parent.leftChild != current) current = current.parent; return current.parrent; } } 

It has been argued that the temporal complexity of this Theta(n) algorithm suggests that there are n nodes in the BST, which is certainly true. However, I can’t convince myself that, I believe, some of the nodes intersect more than a constant number of times, which depends on the number of nodes in their subtrees and summing all these visits, will not lead to the time complexity of Theta(n)

Any idea or intuition on how to prove this?

Answer 1

It’s easier to reason with ribs, not knots. Let's talk based on the code for the Successor function.

Case 1 ( then branch)

For all nodes with the correct child, we immediately go to the correct subtree ("right turn"), then we always look for the left subtree ("left turn") using the Min-Tree function. We can prove that such a crawl will create a path whose edges are unique - the edges will not be repeated in any crawl made from any other node with the correct child, since the crawl ensures that you will never visit the “right turn”, the edge of others knots on a tree. (Proof by construction).

Case 2 ( else branch)

For all nodes without the correct child (the else branch), we will visit the ancestors, following the "right" edges, until you need to make a "left turn" or meet the root of the binary tree. Again, the edges in the created path are unique - they will never be repeated in one other workaround made from any other node without the right child. This is because:

• With the exception of the initial node and node reached by the next edge of the "left turn", all other nodes between them have the correct child (which means that they are excluded from the else branch). The source node, of course, does not have the right child.
• Each node has a unique parent element (only the root of the node has no parent), and the path to the parent is either a "left turn" or a "right turn" (node ​​is the left child or the right child). For any node (ignoring the correct child condition), there is only one path that creates the template: many are "right-handed" and then "left-handed."
• Since the nodes between them have the correct child, there is no way for the edge to appear in 2 rounds, starting from different nodes. (Since we are currently looking at nodes without a valid child).

(The proof here is pretty waving, but I think it can be formally proved by contradiction).

Since the edges are unique, the total number of edges traversed only in case 1 (or only for case 2) will be O (n) (since the number of edges in the tree is equal to the number of vertices - 1), Thus, after summing 2 cases, In-Order traversal will be O (n).

Note that I only know that each edge is visited no more than once — I don’t know whether all edges visit or not, but the number of edges is limited by the number of vertices, which is correct.

It is easy to see that it is also Omega (n) (each node is visited once), so we can conclude that it is Theta (n).

Answer 2

This program works in Θ (N) time. Θ (N) does not mean that each node is visited exactly once. Remember that there is a constant factor. Thus, Θ (N) can indeed be limited to 5 N or 10 N or even 1000 N. Thus, it does not give you an accurate count of the number of visits to a node.

The time complexity of iterative traversal of the binary search tree in order can be analyzed as follows:

Consider a tree with N nodes,

Let the execution time be denoted by a complexity function T(N) .

Let the left auxiliary tree and the right hypochondrium contain the nodes X and NX-1, respectively

Then the time complexity T(N) = T(X) + T(NX-1) + c ,

Now consider the two extreme cases of a BST ,

CASE 1: A BST , which is perfectly balanced, i.e. both sub-elements have an equal number of nodes. For example, consider the below BST,

  10 / \ 5 14 / \ / \ 1 6 11 16 

For such a tree, the complexity function has the form

 T(N) = 2 T(⌊N/2⌋) + c 

The main theorem gives us the complexity Θ (N) in this case.

CASE 2: Completely unbalanced BST, i.e. either the left auxiliary tree or the right auxiliary tree is empty. There for X = 0. For example, consider the BST shown below,

  10 / 9 / 8 / 7 

Now T(N) = T(0) + T(N-1) + c ,

 T(N) = T(N-1) + c T(N) = T(N-2) + c + c T(N) = T(N-3) + c + c + c . . . T(N) = T(0) + N c 

Since T (N) = K, where K is a constant,

T (N) = K + N c

Here for T (N) = Θ (N).

Thus, the complexity is Θ(N) for all cases.

Answer 3

I also can not imagine how it will be O (n). To find only one as a successor, i.e. Node Successor(Node root) will be O (log n), since it depends on the height of the tree. Doing this for each of n nodes will give O (n log n).

Answer 4

We focus on edges instead of nodes. (to better understand the intuition in this picture: http://i.stack.imgur.com/WlK5O.png )

We claim that in this algorithm, each edge is visited no more than two times (in fact, he visited exactly two times);

The first time he went down, and the second time he went up. To visit the rib more than two times, we need to cross this direction down again: down, up, down , ....

It is proved that it is impossible to have a second downward visit of the rib.

Suppose we cross edge (u , v) down a second time, which means that one of u ancestors has a successor that is decedent from u .

It's impossible:

We know that when we cross the edge up, we look for the left edge to find a successor, therefore, if u is to the left of the successor, the successor of this successor is on its right, moving to the right side of the successor (to find its successor), reaching u again, and therefore edge (u,v) again impossible. (to find a successor, we either move to the right or up, but not to the left)