Scribd
Upload
5 views3 pages

Understanding Tree Data Structures

Chapter 3 discusses tree data structures, which are non-linear and represent hierarchical relationships through nodes and edges. It covers basic terminologies, properties, types of trees (including binary trees and B-trees), and their applications in various fields such as databases and file systems. The chapter emphasizes the efficiency of tree operations like searching and sorting.

Uploaded by

ingridekoungoup
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
5 views3 pages

Understanding Tree Data Structures

Chapter 3 discusses tree data structures, which are non-linear and represent hierarchical relationships through nodes and edges. It covers basic terminologies, properties, types of trees (including binary trees and B-trees), and their applications in various fields such as databases and file systems. The chapter emphasizes the efficiency of tree operations like searching and sorting.

Uploaded by

ingridekoungoup
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

Chapter 3: Tree Data Structure

1. Introduction to Trees
A tree is a non-linear data structure that represents hierarchical relationships. It is made up
of nodes connected by edges. The topmost node is called the root.

2. Basic Terminologies
• Node: A fundamental unit containing data.

• Root: Topmost node of the tree.

• Parent & Child: A node connected above/below another node.

• Siblings: Nodes sharing the same parent.

• Leaf Node: Node with no children.

• Internal Node: Node with at least one child.

• Depth: Distance from root to a node.

• Height: Longest path from a node to a leaf.

3. Properties of Trees
• A tree with N nodes has N−1 edges.

• There is exactly one path between any two nodes.

• Trees are recursive structures.

4. Types of Trees
• General Tree: No restrictions on number of children.

• Binary Tree: Each node has at most two children.

• Full Binary Tree: Every node has 0 or 2 children.

• Complete Binary Tree: All levels are filled except possibly the last.

• Perfect Binary Tree: All internal nodes have 2 children and all leaves are at same level.

• Binary Search Tree (BST): Left subtree contains smaller values, right subtree larger values.

• AVL Tree: Self-balancing BST.

• B-Tree: Multi-way search tree used in databases.


5. Binary Trees in Detail
Binary trees allow efficient searching and traversal. Common operations include:

• Insertion

• Deletion

• Searching

Traversals:

• Inorder (Left, Root, Right)

• Preorder (Root, Left, Right)

• Postorder (Left, Right, Root)

• Level-order (Breadth-first traversal)

6. Binary Search Tree (BST)


A BST maintains sorted order. Operations have:

• Time Complexity (average): O(log n)

• Time Complexity (worst): O(n)

BST Operations:

• Insert: Place new value in correct position.

• Search: Navigate left or right depending on target.

• Delete: Three cases—leaf node, node with one child, node with two children.

7. AVL Trees
AVL Trees are height-balanced BSTs. The height difference (balance factor) between left
and right subtree is ≤ 1.

Rotations used to maintain balance:

• Left Rotation

• Right Rotation

• Left-Right Rotation

• Right-Left Rotation

8. B-Trees
B-Trees allow multiple children and are optimized for disk access. Used in databases and
filesystems.

Properties:

• Each node can contain multiple keys.

• Balanced by design.

• Suitable for large data storage.

9. Applications of Trees
• File system representation

• Database indexing (B-Trees)

• Expression parsing in compilers

• Routing algorithms

• Hierarchical data representation

10. Summary
Trees are powerful structures for representing hierarchical relationships. They provide
efficient operations for searching, sorting, and managing structured data.

You might also like