Table of Contents
Trees
In the single-linked and double-linked 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
Left-Complete 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
Depth-First Traversals
In Order Traversal
Pre Order Traversal
Post Order Traversal
Example: Expression Tree
Depth-First Traversals
Depth-First Traversals
Example: Inorder Traversal
Example: Inorder Traversal
Example: Postorder Traversal
Example: Postorder Traversal
Example: Preorder Traversal
Example: Preorder Traversal
Multiway Trees
B trees
A B-Tree 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 B-Tree of order 2
Deletion
A B-Tree of order 2
A B-Tree of order 2
A B-Tree of order 2
A B-Tree of order 2
20, 30, 35, 40,
|
Author: Computer Science Dept.
|