figure skewed binary search tree would give poor performance the keys are added to the tree if the keys are added in random orderthe height of the tree is going to be around log where is the number of nodes in the tree this is because if the keys are randomly distributedabout half of them will be less than the root and half will be greater than the root remember that in binary tree there is one node at the roottwo nodes in the next leveland four at the next the number of nodes at any particular level is where is the depth of the level the total number of nodes in perfectly balanced binary tree is where represents the height of the tree perfectly balanced tree has the same number of nodes in the left subtree as the right subtree in balanced binary treethe worst-case performance of put is (log )where is the number of nodes in the tree notice that this is the inverse relationship to the calculation in the previous paragraph so log gives us the height of the treeand represents the maximum number of comparisons that put will need to do as it searches for the proper place to insert new node unfortunately it is possible to construct search tree that has height simply by inserting the keys in sorted orderan example of such tree is shown in figure in this case the performance of the put method is (nnow that you understand that the performance of the put method is limited by the height of the treeyou can probably guess that other methodsgetinand delare limited as well since get searches the tree to find the keyin the worst case the tree is searched all the way to the bottom and no key is found at first glance del might seem more complicatedsince it may need to search for the successor before the deletion operation can complete but remember that the worst-case scenario to find the successor is also just the height of the tree which means that you would simply double the work since doubling is constant factor it does not change worst case analysis of (nfor an unbalanced tree summary in this we have looked at the tree data structure the tree data structure enables us to write many interesting algorithms in this we have looked at algorithms that use trees to do the following summary