Why does a well balanced Binary Search Tree have a search complexity of O(log(n)), if you search for one element?
The idea is that the height (and, therefore, the number of comparisons to make) of such tree must be approximately log(n) where n is the number of leaves. For more information, could you remind the definition of well-balanced and other details, such as whether you store data in leaves only or also in the internal nodes?
I think a "well balanced tree" is one that has a fairly equal distribution of nodes, if that makes sense.
Leaf nodes: Nodes with no children
Interior nodes: Nodes with children
Any node can be considered the root of a subtree.
A tree consists of a collection of nodes connected by directed arcs.
Path length: the number of arcs tranversed
height: the maximum path length from that node to the leaf node
depth: the path length from one root to that node
- root node has a depth of 0
- a tree's depth is the max depth of all its leaf nodes (which is also the tree's height)
Binary Tree:
-nodes have no more than two children
-children are generally referred to as "left" and "right"
Full Binary Tree:
- every leaf is at the same depth
- every internal node has 2 children
- height of h will have $\displaystyle 2^{h+1}-1$ nodes
- height of h will have $\displaystyle 2^{h}$ leaves
Complete binary tree: full except for the bottom level which is filled from left to right.
Binary search trees are binary trees where every node value is:
-greater than all its descendants in the left subtree
-less than or equal to all its descendants in the right subtree
Thanks for the definitions.
The proof that a search complexity is O(log(n)) can only be as precise as the definition of "well-balanced". You also did not say whether information is stored in leaves only or also in internal nodes. The precise bounds are slightly different, but the O(log(n)) estimate is the same in both cases.
For example, if you store information in leaves and "well-balanced" means "complete", then the number n of leaves (and pieces of data) is greater than 2^(h-1) (the number of nodes on the second last level) where h is tree's height. Taking log₂, we get log(n) > h - 1, or h < log(n) + 1. Since search complexity is proportional to tree's height, the complexity is O(log(n)).