Question

binary search tree and operations in it?(Assignment) 1 page​

Answer 1

Answer:

•) Basic operations on a BST

Create: creates an empty tree.

Insert: insert a node in the tree.

Search: Searches for a node in the tree.

Delete: deletes a node from the tree.

Inorder: in-order traversal of the tree.

Preorder: pre-order traversal of the tree.

Postorder: post-order traversal of the tree.

•) Special types of BT

Heap

Red-black tree

B-tree

Splay tree

N-ary tree

Trie (Radix tree)

•) Runtime.

Data structure: BST

Worst-case performance: O(n)

Best-case performance: O(1)

Average performance: O(log n)

Worst-case space complexity: O(1)

{ Where n is the number of nodes in the BST. Worst case is O(n) since BST can be unbalanced.}