Question

fill in the blank

	Binary Search Tree	AVL Tree	Red-Black Tree
complexity	O(log N), O(N) in the worst case	O(log N)	O(log N)
Advantages	- Increasing and decreasing order traversal is easy - Can be implemented	- The complexity remains O(Log N) for a large number of input data.	- Insertion and deletion operation is very efficient - The complexity remains O(Log N) for a large number of input data.
Disadvantages	- The complexity is O(N) in the worst case	- The implementation is complicated. - Deletion operation is costly as it takes lots of rotation and pointers	The implementation is complicated.
Running time		not efficient because it check the tree after each insertion and deletion to make sure it's balance.
Memory		It's required an extra memory to store the balance factor
height		does not exceed 1.44 log n	Minimum log2(n+1) but not greater than 2log2(n+1).

Answer 1

Solution

	Binary Search Tree	AVL Tree	Red-Black Tree
Running time	not efficient because for searching element sometimes we need to traverse all the element samething for insertion and deletion sometimes we need to traverse ll the element		it is efficient because it needs only 1 bit of information per node because of the stricly balanced fastest retrieval is possible
Memory	Each node has a key and an associated value a bit need for key and another bit needed for associated value		it needs only 1 bit of information per node
Height	Maximum height of the binary search tree is n-1 Minimum height is floor(log2n)

Explanation

Missed information filled in

the table is comparison between binary search tree, AVL tree and Red Black tree

---

all the best