The conditional PDF P(r|sm) or any monotonic function of it is usually called the likelihood function.

The conditional PDF P(r|sm) or any monotonic function of it is usually called the likelihood function.

1. UNIT IV TREES By Dr. V. NAGARAJAN Department of Electronics Engineering

2. Content Trees: Basic Tree Terminologies. Different types of Trees: Binary Tree – Threaded Binary Tree – Binary Search Tree – Binary Tree Traversals – AVL Tree. Introduction to B-Tree and B+ Tree.

3. Trees 1. Introduction to Trees A tree is a non-linear hierarchical data structure consisting of nodes connected by edges. Basic Terminologies: Root → topmost node. Parent & Child → relationship between levels. Leaf Node → node with no children. Height → longest path from root to leaf. Depth → distance of node from root. Degree → number of children of a node. Subtree → a smaller tree inside a larger tree.

4. Example

5. Why Tree is considered a non-linear data structure? The data in a tree are not stored in a sequential manner i.e., they are not stored linearly. Instead, they are arranged on multiple levels or we can say it is a hierarchical structure. For this reason, the tree is a non-linear data structure. A binary tree is a hierarchical structure where each node has at most 2 children: - Left child - Right child Special cases: - Full Binary Tree – every node has 0 or 2 children. - Complete Binary Tree – all levels filled except possibly the last. - Skewed Tree – all nodes only left or only right.

6. Problem 1: Construct a binary tree Construct a binary tree for the expression: (A + B) * (C – D) Solution: Tree representation: * / \ + - / \ / \ A B C D Preorder: * + A B - C D Inorder : A + B * C - D Postorder : A B + C D - *

7. Problem 2: Height of binary tree Find the height of the following tree: 10 / \ 20 30 / \ 40 50 Solution: Height = 3

8. Problem 3: Check if binary tree is full Example: 1 / \ 2 3 → Full binary tree ✅ 1 / 2 → Not a full binary tree ❌

9. Types of Trees General Tree Binary Tree Full Binary Tree Complete Binary Tree Perfect Binary Tree Skewed (Degenerate) Tree Threaded Binary Tree Binary Search Tree (BST) AVL Tree B-Tree B+ Tree

10. 1. General Tree A tree where each node can have any number of children. Example: Root: "Company" Child1: "HR" Child2: "Finance" Child3: "IT"

11. Problem If a general tree has 1 root and each node can have up to 3 children, what is the maximum number of nodes at level 3? Solution: At each level, nodes can triple. Level 0 → 1 node Level 1 → 3 nodes Level 2 → 3² = 9 nodes Level 3 → 3³ = 27 nodes Answer: 27 nodes.

12. 2. Binary Tree Definition: A tree where each node has at most two children (left and right) Example: A / \ B C / \ D E

13. Problem: How many nodes can a binary tree have at height 3 (perfect binary tree)? Solution: Max nodes = 2^(h+1) - 1 = 2^(3+1) - 1 = 15. Answer: 15 nodes.

14. Types of Binary Tree Full Binary Tree: Every node has 0 or 2 children. Complete Binary Tree: All levels filled except last, filled left to right. Perfect Binary Tree: All internal nodes have 2 children, all leaves at same level. Skewed Tree: Every parent has only one child.

15. 3. Threaded Binary Tree Definition: A binary tree where NULL pointers are replaced by threads pointing to in order predecessor/successor. Example: If node A has no right child, its right pointer points to inorder successor. Why do we use threaded binary trees? Solution: To perform inorder traversal without recursion/stack , saving memory and improving speed .

16. 4. Binary Search Tree (BST) Definition: A binary tree with the property: Left child < Parent < Right child. Example: 50 / \ 30 70 / \ / \ 20 40 60 80

17. Problem: Search for 40 in the BST. 50 / \ 30 70 / \ / \ 20 40 60 80 Solution: Start at root: 50 → 40 < 50 → go left. Node 30 → 40 > 30 → go right. Node 40 found .

18. 5. AVL Tree Definition: A self-balancing BST where balance factor = height(left) – height(right) is -1, 0, or 1 . Example: Insert nodes: 30, 20, 40, 10 → balanced rotations will keep the tree height small.

19. Problem: What is the balance factor of node 20 in the tree: 20 / \ 10 30 Solution: Height(left)=1, Height(right)=1 → BF = 1 - 1 = 0. Answer: 0 (balanced).

20. Problem : Height of AVL Tree What is the minimum number of nodes in an AVL tree of height h = 4 ? Solution: Formula for minimum nodes in AVL: with . Compute: Minimum nodes in AVL of height 4 = 12 .  

21. Problem: Deletion in an AVL Tree Delete key 30 from the AVL tree: 40 / \ 20 50 / \ 10 30 Delete 30 → New tree: 40 / \ 20 50 / 10 Check balance factors: Node 20 → BF = 1 (balanced). Node 40 → BF = +2 (unbalanced). Subtree type: Left-Left (LL) . Apply Right Rotation at 40. Result: 20 / \ 10 40 / \ - 50

22. Problem : Search Path Search for key 35 in the AVL tree: 30 / \ 20 40 / \ / \ 10 25 35 50 Solution: Start at root = 30. 35 > 30 → go right. At node 40. 35 < 40 → go left. At node 35 → Found! ✅Path = 30 → 40 → 35

23. Introduction to B-Tree A B-Tree is a self-balancing search tree in which data is stored in sorted order. It allows for efficient insertion, deletion, and search operations. B-Trees are widely used in databases and file systems because they provide a way to store and retrieve data efficiently in disk-based storage systems.

24. Motivation To have dynamic indexing structures that can evolve when records are added and deleted Not the case for static indexes Would have to be completely rebuilt Optimized for searches on block devices Both B trees and B+ trees are not binary Objective is to increase branching factor ( degree or fan-out) to reduce the number of device accesses

25. B trees Generalization of binary search trees Not binary trees The B stands for Bayer (or Boeing) Designed for searching data stored on block-oriented devices

26. Properties of B-Tree The key properties of a B-Tree are as follows: All leaf nodes are at the same level. - A B-Tree of order m can have at most m-1 keys and m children per node. - Nodes in a B-Tree are sorted and balanced, ensuring that the tree remains balanced after insertions and deletions. - The height of a B-Tree is kept low, making search operations efficient.

27. Binary vs. higher-order tree Binary trees: Designed for in-memory searches Try to minimize the number of memory accesses Higher-order trees: Designed for searching data on block devices Try to minimize the number of device accesses Searching within a block is cheap!

28. A very small B tree Bottom nodes are leaf nodes: all their pointers are NULL

29. In reality In tree ptr Key Data ptr In tree ptr Key Data ptr In tree ptr Key Data ptr In tree ptr Key Data ptr In tree ptr To Leaf 7 To leaf 16 To Leaf -- Null Null -- Null Null

30. Organization Each non-terminal node can have a variable number of child nodes Must all be in a specific key range Number of child nodes typically vary between d and 2 d Will split nodes that would otherwise have contained 2 d + 1 child nodes Will merge nodes that contain less than d child nodes

31. Searching the tree keys < 7 keys > 16 7 < keys < 16

32. Insertions Assume a tree where each node can contain three pointers (non represented) Step 1: Step 2: Step 3: Split node in middle 1 1 2 1 2 3 2 1 3

33. Insertions Step 4: Step 5: Split Move up 5 3 2 1 4 3 2 1 4 4 2 1 3 5

34. Insertions Step 6: Step 7: 4 2 1 3 5 6 4 2 1 3 5 6 7

35. Step 7 continued 4 2 1 3 6 4 7 4 2 1 3 6 5 7 Split Promote

36. Step 7 continued Split after the promotion 4 2 1 3 6 5 7 4 2 1 3 6 5 7

37. Two basic operations Split: When trying to add to a full node Split node at central value Promote: Must insert root of split node higher up May require a new split 7 5 6 6 5 7

38. Introduction to B+ Tree A B+ Tree is an extension of a B-Tree where all values are stored in the leaf nodes, and the internal nodes only store keys. It is used primarily for indexing and is widely employed in databases and file systems.

39. B+ trees Variant of B trees Two types of nodes Internal nodes have no data pointers Leaf nodes have no in-tree pointers Were all null!

40. Properties of B+ Tree 1. Structural Properties Root Node The root can be a leaf (when the tree is very small). Otherwise, it has at least 2 children . Internal Nodes (Index Nodes) Act as routing / index nodes , storing only keys (no actual data). Keys act as separators guiding the search. Each internal node (except root) has ⌈m/2⌉ to m children (where m = order of tree). Leaf Nodes Store the actual data (records/pointers) . All leaf nodes are linked together using pointers → supports efficient range queries . Each leaf node can hold between ⌈L/2⌉ and L keys (where L = max leaf capacity). Balanced Height The tree is always balanced → all leaves appear at the same level. Ensures O(log n) search time.

41. B+ tree nodes In tree ptr Key In tree ptr Key In tree ptr Key In tree ptr Key In tree ptr Key In tree ptr Key Data ptr Key Data ptr Key Data ptr Key Data ptr Key Data ptr Key Data ptr

42. More about internal nodes Consist of n -1 key values K 1 , K 2 , … , K n -1 ,and n tree pointers P 1 , P 2 , … , P n : < P 1 , K 1 , P 2 , K 2 , P 3 , … , P n -1 , K n -1, , P n > The keys are ordered K 1 < K 2 < … < K n -1 For each tree value X in the subtree pointed at by tree pointer P i , we have: X > K i -1 for 1 ≤ i ≤ n X ≤ K i for 1 ≤ i ≤ n - 1

43. Warning Other authors assume that For each tree value X in the subtree pointed at by tree pointer P i , we have: X ≥ K i -1 for 1 ≤ i ≤ n X < K i for 1 ≤ i ≤ n - 1 Changes the key value that is promoted when an internal node is split

44. Advantages Removing unneeded pointers allows to pack more keys in each node Higher fan-out for a given node size Normally one block Having all keys present in the leaf nodes allows us to build a linked list of all keys

45. Properties If m is the order of the tree Every internal node has at most m children. Every internal node (except root) has at least ⌈ m ⁄ 2⌉ children. The root has at least two children if it is not a leaf node. Every leaf has at most m − 1 keys An internal node with k children has k − 1 keys. All leaves appear in the same level

46. Insertions Assume a B+ tree of degree 3 Step 1: Step 2: Step 3: Split node in middle 1 1 2 1 2 3 2 1 2 3

47. Insertions Step 4: Step 5: Split Move up 5 3 2 1 2 4 3 2 1 2 4 4 2 1 2 3 4 5

48. Insertions Step 6: Step 7: 4 2 1 2 3 4 5 6 4 2 1 2 3 4 5 6 7

49. Step 7 continued 4 2 1 2 3 4 6 5 6 7 4 2 1 2 3 4 6 5 6 7 Split Promote

50. Step 7 continued Split after the promotion 4 2 1 3 6 5 7 4 2 1 3 6 5 7

51. Importance B+ trees are used by NTFS, ReiserFS, NSS, XFS, JFS, ReFS, and BFS file systems for metadata indexing BFS for storing directories. IBM DB2, Informix, Microsoft SQL Server, Oracle 8, Sybase ASE, and SQLite for table indexes

52. Example of a B-Tree Consider a B-Tree of order 3 (i.e., each node can have at most 2 keys and 3 children). Initial B-Tree with order 3: Root: [15, 20] Child 1: [5] Child 2: [10] Child 3: [25] After inserting key 18, the B-Tree might look like: Root: [10, 18, 20] Child 1: [5] Child 2: [15] Child 3: [25]

53. Problem : Insert Keys into a B-Tree of Order 3 Insert the keys 10, 20, 5, 6, 12 into an empty B-Tree of order 3 (max 2 keys per node). Solution: 1. Insert 10 → root = [10] 2. Insert 20 → root = [10, 20] (still valid). 3. Insert 5 → root = [5, 10, 20] → overflow (3 keys). - Split: middle = 10 → New root = [10] - Left child = [5], Right child = [20] → Tree: [10] / \ [5] [20] 4. Insert 6 → goes to left child [5]. → Left child = [5, 6]. → Tree: [10] / \ [5,6] [20] 5. Insert 12 → goes to right child [20]. → Right child = [12,20]. → Tree: [10] / \ [5,6] [12,20] Final B-Tree = Balanced.

54. Problem : Search in a B-Tree Given B-Tree of order 3: [20] / \ [5,10] [30, 40 ] Search for 40 . Solution: 1. Start at root [20]. - 40 > 20 → go right. 2. At [30,40]. - Found at second key. Path = 20 → (30,40) → Found.

55. Problem : Deletion in a B-Tree Delete 6 from the B-Tree: [10] / \ [5, 6 ] [12,20] Solution: 1. 6 is in left child [5,6]. 2. Delete → node becomes [5]. 3. Now [5] has only 1 key (minimum allowed for order 3 is 1). → No underflow, so valid. New Tree: [10] / \ [5] [12,20]

56. Problem: Height of a B-Tree Find the minimum and maximum number of keys in a B-Tree of order 4 (max 3 keys per node) and height 2. Solution: Max keys per node = 3. - Height = 2 → Root + Children. Maximum keys = 1 root (3 keys) + 4 children × 3 keys = 3 + 12 = 15 Minimum keys: - Root must have at least 1 key. - Each child must have ⌈m/2⌉ − 1 = ⌈4/2⌉ − 1 = 1 key. - Total = 1 + 2 children × 1 = 3 keys Min = 3, Max = 15

57. Problem : Insert into a B-Tree of Order 4 Insert keys 10, 20, 5, 6, 12, 30, 7, 17 into a B-Tree of order 4 (max 3 keys per node). Solution: 1. Insert [10,20]. 2. Insert 5 → [5,10,20]. 3. Insert 6 → [5,6,10,20] → Overflow (4 keys). - Split: middle = 6, promote to root. - Left = [5], Right = [10,20]. - Tree: [6] / \ [5] [10,20] 4. Insert 12 → goes right → [10,12,20]. 5. Insert 30 → right child [10,12,20,30] → Overflow. - Split: promote 12 → root becomes [6,12]. - Left = [10], Right = [20,30]. - Tree: [6,12] / | \ [5] [10] [20,30] 6. Insert 7 → goes to middle child [10] → becomes [7,10]. 7. Insert 17 → goes to right [20,30] → becomes [17,20,30]. ✅ Final Tree: [6,12] / | \ [5] [7,10] [17,20,30]

58. Differences Between B-Tree and B+ Tree Feature B-Tree B+ Tree Data Storage Data stored in both internal and leaf nodes Data stored only in leaf nodes Internal Nodes Store keys + data Store keys only (index) Leaf Nodes Not linked Linked list of leaf nodes Range Queries Less efficient Very efficient (sequential access) Height Slightly higher Slightly shorter (better fanout) Traversal In-order traversal needed Sequential traversal via leaf links

59. Thank You