Scribd
Upload
1 views2 pages

Data Structures Assignment

The document discusses binary search trees (BST) and B-Trees, detailing their construction, traversal methods, and operations such as search, insertion, and deletion. It also covers tree terminology and types, including full, complete, perfect, and skewed binary trees. Additionally, it provides examples of tree traversals for given structures.

Uploaded by

tankarisrilatha719
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
1 views2 pages

Data Structures Assignment

The document discusses binary search trees (BST) and B-Trees, detailing their construction, traversal methods, and operations such as search, insertion, and deletion. It also covers tree terminology and types, including full, complete, perfect, and skewed binary trees. Additionally, it provides examples of tree traversals for given structures.

Uploaded by

tankarisrilatha719
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

1) BST Construction and Traversals

Given elements: 60, 40, 80, 20, 50, 70, 90, 10, 30

Constructed BST (structure):

60
/ \
40 80
/\ /\
20 50 70 90
/\
10 30

Preorder: 60, 40, 20, 10, 30, 50, 80, 70, 90

Inorder: 10, 20, 30, 40, 50, 60, 70, 80, 90

Postorder: 10, 30, 20, 50, 40, 70, 90, 80, 60

2) B-Tree and Operations


B-Tree is a self-balancing search tree where nodes can have multiple keys and children.

Operations:

1. Search: Traverse nodes comparing keys.

2. Insertion: Insert key and split node if overflow.

3. Deletion: Remove key and merge/borrow if underflow.

3) Tree Terminology and Types


Terminology:

Root, Parent, Child, Leaf, Height, Depth, Subtree.

Types of Binary Trees:

1. Full Binary Tree: Each node has 0 or 2 children.

2. Complete Binary Tree: All levels filled except last.

3. Perfect Binary Tree: All levels completely filled.


4. Skewed Tree: Nodes in one direction.

4) BST Insertion Algorithm


Steps:

1. Start at root.

2. If value < node, go left; if >, go right.

3. Insert when null position found.

Example inserting 50 in BST:

Compare with root → go left/right → insert.

B-Tree Characteristics:

1. All leaves at same level.

2. Nodes have multiple keys.

3. Balanced height.

5) Traversals of Given Tree


Tree (interpreted):

8
/ \
3 10
/\ \
1 6 14
/\ /
4 7 13

Preorder: 8, 3, 1, 6, 4, 7, 10, 14, 13

Inorder: 1, 3, 4, 6, 7, 8, 10, 13, 14

Postorder: 1, 4, 7, 6, 3, 13, 14, 10, 8

You might also like