Table of Contents
Trees
In the singlelinked and doublelinked lists, the nodes are joined in a line.
The top of the tree, which consists of just one node, is called the root; the opposite of a real tree, just to make things confusing.
Uses of Trees
Uses of Trees
Uses of Trees
Binary Tree Terminology
Binary Tree Terminology
Binary Tree Terminology
Binary Tree Terminology
Binary Tree Terminology
Binary Tree Terminology
Skinny Tree
Complete Tree
Perfect Tree
LeftComplete Tree
Binary Tree Terminology
Binary Search Trees
A Binary Search Tree
Balanced Binary Trees
A binary tree is a useful data structure when 2 way decisions must be made at each point in a process.
Tree Traversals
DepthFirst Traversals
In Order Traversal
Pre Order Traversal
Post Order Traversal
Example: Expression Tree
DepthFirst Traversals
DepthFirst Traversals
Example: Inorder Traversal
Example: Inorder Traversal
Example: Postorder Traversal
Example: Postorder Traversal
Example: Preorder Traversal
Example: Preorder Traversal
Multiway Trees
B trees
A BTree of order 2
Insertion
Insert 22
PPT Slide
Insertion of an item into an ancestor page may cause that page to overflow, thereby causing the split to propagate.
Exercise.
Deletion
Removal ctd.
If there is no page to be moved from Q (as Q has reached its minimal size) then the values in P and Q may be merged, adding the middle item from the ancestor page of P and Q and tehn entirely dispose of page Q
A BTree of order 2
Deletion
A BTree of order 2
A BTree of order 2
A BTree of order 2
A BTree of order 2
20, 30, 35, 40,

Author: Computer Science Dept.
