Trees

26/11/01


Click here to start


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.