Please enable JavaScript.
Coggle requires JavaScript to display documents.
Search and Insertion in a Binary Tree - Coggle Diagram
Search and Insertion in a Binary Tree
Binary Tree
Nodes contain elements of a set of orderable items, one element per node, so that for every node all elements in the left subtree are smaller and all the elements in the right subtree are greater than the element in the subtree’s root
Search
Search for an element of a given value v
do it
recursively
If the tree is empty
The search ends in failure
If the tree is not
empty
Compare v with the tree’s root K(r)
If they match
Desired element is found and the search can be stopped
If they don't match
Continue with the search in the left subtree of the root if v < K(r) and in the right subtree if v > K(r)
On each iteration of the algorithm, the problem of searching in a binary search tree is reduced to searching in a smaller binary search tree.
Efficiency
Worst-Case
BigTheta(n)
Average-case
BigTheta(log n)