Question

JAVA: Explain the advantages and disadvantages of binary search tree structures. Discuss ways to quantify performance.

Answer 1

`Hey,

Note: Brother in case of any queries, just comment in box I would be very happy to assist all your queries

Advantages:

1) Stores keys in the nodes in a way that searching, insertion and deletion can be done efficiently.

2) Simple Implementation

3) Nodes in tree are dynamic

4) Level of BST is minmum, then complexity is decreases

5) Operations on Balencing tree is easy compared to Un-balanced tree

Disadvantages:

1) The shape of the tree depends on the order of insertions, and it can be degenerated.

2) When inserting or searching for an element, the key of each visited node has to be compared with the key of the element to be inserted/found.

3) Keys in the tree may be long and the run time may increase.

4) Delete or destory a node, then re-arrange the tree

5) Level is BST increases, complexity to find an element is increases

Quantify performance:

1) At best O(log n), which occur when the tree is full

2) At worst O(n) which occur when the tree is skewed

3) Thought to be on average O(log n)

4) Improve the performance of BST, convert it into AVL - Tree

5) To improve performence a BST, for every insertion a node or element convert into Balanced tree

Kindly revert for any queries

Thanks.