n-binary tree

Binary Trees : 

Binary Trees

Overview : 

Overview Trees. Terminology. Traversal of Binary Trees. Expression Trees. Binary Search Trees.

Trees : 

Trees Family Trees. Organisation Structure Charts. Program Design. Structure of a chapter in a book.

Parts of a Tree : 

Parts of a Tree

Tree : 

Tree The term "tree" is used in Computer Science to denote a particular type of abstract data structure. Trees contain data in structures called nodes,which are in turn linked to other nodes in the tree. Additionally, each node is the parent of subtrees. Every node in a tree has 0 or more children. One or more of the subtrees may have no elements and are called empty subtrees. In this way a tree can be described as being made up of multiple subtrees.

Parts of a Tree : 

Parts of a Tree nodes

Slide 7: 

root : Every tree has a primary node called a root , from which all other branch nodes in the tree descend. leaf : The nodes that have no descendents are called leaf nodes.

Parts of a Tree : 

Parts of a Tree parent node

Parts of a Tree : 

Parts of a Tree child nodes parent node

Parts of a Tree : 

Parts of a Tree child nodes parent node

Parts of a Tree : 

Parts of a Tree root node

Parts of a Tree : 

Parts of a Tree leaf nodes

Parts of a Tree : 

Parts of a Tree sub-tree

Parts of a Tree : 

Parts of a Tree sub-tree

Parts of a Tree : 

Parts of a Tree sub-tree

Parts of a Tree : 

Parts of a Tree sub-tree

Binary Tree : 

Binary Tree Each node can have at most 2 children

Traversal : 

Traversal Systematic way of visiting all the nodes. Methods: Preorder, Inorder, and Postorder They all traverse the left subtree before the right subtree. The name of the traversal method depends on when the root is visited.

Preorder Traversal : 

Preorder Traversal Visit the root. Traverse the left subtree. Traverse the right subtree.

Example: Preorder : 

Example: Preorder 31 43 64 20 40 56 28 33 47 59 89

Inorder Traversal : 

Inorder Traversal Traverse the left subtree. Visit the root. Traverse the right subtree.

Example: Inorder : 

Example: Inorder 31 43 64 20 40 56 28 33 47 59 89

Postorder Traversal : 

Postorder Traversal Traverse the left subtree. Traverse the right subtree. Visit the root.

Example: Postorder : 

Example: Postorder 31 43 64 20 40 56 28 33 47 59 89

Expression Tree : 

Expression Tree A Binary Tree built with operands and operators. Also known as a parse tree. Used in compilers.

Example: Expression Tree : 

Example: Expression Tree / + / 1 3 * 6 7 4 1/3 + 6*7 / 4

Notation : 

Notation Preorder Prefix Notation Inorder Infix Notation Postorder Postfix Notation

Example: Infix : 

Example: Infix / + / 1 3 * 6 7 4

Example: Postfix : 

/ + / 1 3 * 6 7 4 Example: Postfix 1 3 / 6 7 * 4 / +

Example: Prefix : 

/ + / 1 3 * 6 7 4 Example: Prefix + / 1 3 / * 6 7 4

Slide 31: 

Height of a tree is the length of the longest path from root to some leaf node. Height of a empty tree is -1. Height of a single node tree is 0. Recursive definition: height(t) = -1 if T is empty = 0 if number of nodes = 1 = 1+ max(height(LT), height(RT)) otherwise Height of a Tree (Review)

Binary Search Tree : 

Binary Search Tree A Binary Tree such that: Every node entry has a unique key. All the keys in the left subtree of a node are less than the key of the node. All the keys in the right subtree of a node are greater than the key of the node.

Slide 33: 

Example 1: 31 43 64 20 40 56 28 33 47 59 89 key is an integer

Insert : 

Insert Create new node for the item. Find a parent node. Attach new node as a leaf.

Insert : 

Insert 31 43 64 20 40 56 28 33 47 59 89 Example: 57

Insert : 

Insert 31 43 64 20 40 56 28 33 47 59 89 Example: 57

Search: Checklist : 

Search: Checklist if target key is less than current node’s key, search the left sub-tree. else, if target key is greater than current node’s key, search the right sub-tree. returns: if found, pointer to node containing target key. otherwise, NULL pointer.

Search : 

Search 31 43 64 20 40 56 28 33 47 59 89 Example: 59 57 found

Search : 

Search 31 43 64 20 40 56 28 33 47 59 89 Example: 61 57 failed

Deleting nodes : 

Deleting nodes Three types of nodes to delete: Leaf Node with one child Node with 2 children

Deleting a leaf : 

Deleting a leaf V C W F T D Y Z X Delete: V U E M K

Deleting a leaf : 

Deleting a leaf C W F T D Y Z X Delete: V U E M K

Deleting a node with 1 child : 

Deleting a node with 1 child Delete: M Connect child to parent of M C W F T D Y Z X U E M K

Deleting a node with 1 child : 

Deleting a node with 1 child Delete: M C W F T D Y Z X U E K

Deleting a node with 2 children : 

Deleting a node with 2 children Need to find which node should replace deleted one Two ways of doing it...go left or go right C W F T D Y Z X U E K Delete: K

Delete K Go left... : 

Delete K Go left... Find RIGHTMOST node in LEFT subtree C W F T D Y Z X U E K

Delete K Go left... : 

Delete K Go left... C W F T D Y Z X U E K Move this node to replace deleted node

Delete K Go left... : 

Delete K Go left... C W F T D Y Z X U E K Reconnect this node’s subtree

Delete K Go left... : 

Deletion completed Delete K Go left... C W E T D Y Z X U F

Delete K Go right... : 

Find LEFTMOST node in RIGHT subtree C W F T D Y Z X U E K Delete K Go right...

Delete K Go right... : 

Move this node to replace deleted node C W F T D Y Z X U E K Delete K Go right...

Delete K Go right... : 

Deletion completed C W F D Y Z X U E T Delete K Go right...

Slide 53: 

AVL Tree

Threaded Binary Trees : 

Threaded Binary Trees Given a binary tree with n nodes, the total number of links in the tree is 2n. Each node (except the root) has exactly one incoming arc only n - 1 links point to nodes remaining n + 1 links are null. One can use these null links to simplify some traversal processes. A threaded binary search tree is a BST with unused links employed to point to other tree nodes. Traversals (as well as other operations, such as backtracking) made more efficient. A BST can be threaded with respect to inorder, preorder or postorder successors.

Threaded Binary Trees : 

Threaded Binary Trees

Threaded Binary Trees : 

Threaded Binary Trees

Threaded Binary Trees : 

Threaded Binary Trees

Threaded Binary Trees : 

Threaded Binary Trees

Threaded Binary Trees : 

Threaded Binary Trees

Threaded Binary Trees : 

Threaded Binary Trees

Algorithm to right-thread BST : 

Algorithm to right-thread BST

Algorithm to right-thread BST : 

Algorithm to right-thread BST

Algorithm to right-thread BST : 

Algorithm to right-thread BST

4.5 B-Trees : 

4.5 B-Trees A B-tree of order M is a tree with the following structural properties. - The root is either a leaf or has between 2 and M children. - All nonleaf nodes (except root) have between M/2 and M children. - All leaves are at the same depth.

B-Trees : 

B-Trees Example: B-tree of order 4

B-Trees : 

B-Trees A B-tree of order 3 (known as a 2-3 tree)

Insertion into a b-tree : 

Insertion into a b-tree They grow at the root. Search if the new key exists in the tree if not. The new key is then added to the leaf node. If the leaf is not full then the insertion is done to that leaf. If the leaf is already full, then the node is split into two nodes on the same level, except that the median key is not put into either of the two new nodes but is instead sent up the tree instead into its parent. If the key is added to the full root then the root splits into two and the median key sent upwards becomes the new root.

Slide 68: 

Inserting the following keys in the b-tree of order 5. A g f b k d h m j e s i r in the given order 1. a g f b a b f g 2. k a b g k f 3. d h m a b d g h k m f 5. e s i r a b d g h k m f j 4. j a b d e g h i f j k m r s

Deletion from a b-tree : 

Deletion from a b-tree If the leaf contains more than the minimum number of entries, then one can be deleted. If the leaf contains the minimum number of entries, then we first look at the two leaves that are immediately adjacent to each other and are children of the same node. If one of these has more than the minimum number of entries, then one of them can be moved into the parent node, and the entry from the parent moved into the leaf where the deletion is occurring. If finally, the adjacent leaf has only the minimum number of entries, then the two leaves and the median entry from the parent can all be combined as one leaf , which will contain no more than the max no of entries allowed. If this step leaves the parent node with too few entries, then the process propagates upward. In the limiting case, the last entry is removed from the root, and then the height of the tree decreases.

Deletion from a b-tree : 

Deletion from a b-tree a b j c f m r d e g h i k l n p s t u x 1. Delete h, r 2. Delete p g i s t u x j c f m s d e g i k l n p t u x t a b

Deletion from a b-tree : 

Deletion from a b-tree a b j c f m t d e g i 3. Delete d j f g i a b e Combine m t k l n s u x Combine

Deletion from a b-tree : 

a b c e g i- k l f j m t Deletion from a b-tree n s u x

B+ Trees : 

B+ Trees Let “order” refer to the fixed value ‘d’. This is slightly different from “minimum degree” t in B Trees: Minimum keys per node = d Maximum keys per node = 2d B Tree with t=3 has between 2 and 5 keys per node. B+ Tree with order 2 has between 2 and 4 keys per node. B Tree with t=4 has between 3 and 7 keys per node. B+ Tree with order 3 has between 3 and 6 keys per node.

B+ Tree Basics : 

B+ Tree Basics Operations on the tree keep it balanced Minimum occupancy of each node is 50%, except for the root. Searching requires a traversal from the root to the appropriate leaf

B Tree vs B+ Tree Insertions : 

B Tree vs B+ Tree Insertions An insert in a B Tree requires you to split full nodes as you go towards the leaves. Advantage: saves a trip back up the tree to fix the tree. An insert in a B+ Tree first goes to the leaf where the object is inserted, and splits that node if it is full. This may require splitting the parent, etc, all the way up to the root. So, you go to the leaf, and make adjustments (sometimes) all the way up to the root. If the root splits, the height of the tree grows by one.

B Tree vs B+ Tree Deletions : 

B Tree vs B+ Tree Deletions Very similar to B Tree. Take key from sibling if sibling has > 2d keys. Otherwise, merge with sibling. In either case, changes to parent occur.