Downloaded 2,212 times
Uploaded byDharita Chokshi
Binary Search Tree in Data Structure
The document provides an overview of binary search trees (BST), detailing their structure, implementation, and core operations such as insertion, deletion, and traversal methods. It distinguishes between binary trees and binary search trees, emphasizing the rules that govern node value placements within a BST. Additionally, it discusses complexities involved in BST operations and mentions various types of trees, like red-black and AVL trees.
Binary Search Tree in Data Structure
- 1. Click to addTitle e-Infochips Institute of Training Research and Academics Limited Binary Search Tree Guided By:- Mrs. Darshana Mistry Presented By:- Dharita Chokshi Disha Raval Himani Patel
- 2. Outlines • Tree • Binarytree Implementation • Binary Search Tree • BST Operations • Traversal • Insertion • Deletion • Types of BST • Complexity in BST • Applications of BST
- 3. Trees Tree • Each nodecan have 0 or more children • A node can have at most one parent Binary tree • Tree with 0–2 children per node • Also known as Decision Making Tree
- 4. Trees Terminology • Root no parent • Leaf no child • Interior non-leaf • Height distance from root to leaf (H)
- 5. Why is himportant? The Tree operations like insert, delete, retrieve etc. are typically expressed in terms of the height of the tree h. So, it can be stated that the tree height h determines running time!
- 6. Binary Tree Implementation ClassNode { int data; // Could be int, a class, etc Node *left, *right; // null if empty void insert ( int data ) { … } void delete ( int data ) { … } Node *find ( int data ) { … } … }
- 7. Binary Search Tree Keyproperty is value at node • Smaller values in left subtree • Larger values in right subtree Example X > Y X < Z Y X Z
- 8. Binary Search Tree Examples Binary searchtrees Not a binary search tree 5 10 30 2 25 45 5 10 45 2 25 30 5 10 30 2 25 45
- 9. Difference between BTand BST A binary tree is simply a tree in which each node can have at most two children. A binary search tree is a binary tree in which the nodes are assigned values, with the following restrictions : 1. No duplicate values. 2. The left subtree of a node can only have values less than the node 3. The right subtree of a node can only have values greater than the node and recursively defined 4. The left subtree of a node is a binary search tree. 5. The right subtree of a node is a binary search tree.
- 10. Binary Tree SearchAlgorithm TREE-SEARCH(x,k) If x==NIL or k==x.key return x If k < x.key return TREE-SEARCH(x.left,k) else return TREE-SEARCH(x.right,k)
- 11. BST Operations Four basicBST operations 1 2 3 4 Traversal Search Insertion Deletion
- 12.
- 13. Preorder Traversal 23 1812 20 44 35 52 Root Left Right
- 14. Postorder Traversal 12 2018 35 52 44 23 Left Right Root
- 15. Inorder Traversal 12 1820 23 35 44 52 Produces a sequenced list Left Root Right
- 16. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 Inorder Traversal
- 17. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 Inorder Traversal
- 18. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 Inorder Traversal
- 19. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 Inorder Traversal
- 20. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 Inorder Traversal
- 21. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 Inorder Traversal
- 22. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 Inorder Traversal
- 23. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 Inorder Traversal
- 24. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 Inorder Traversal
- 25. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 Inorder Traversal
- 26. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 Inorder Traversal
- 27. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 Inorder Traversal
- 28. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 Inorder Traversal
- 29. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 3 Inorder Traversal
- 30. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 3 Inorder Traversal
- 31. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 3 Inorder Traversal
- 32. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 3 4 Inorder Traversal
- 33. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 3 4 Inorder Traversal
- 34. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 3 4 Inorder Traversal
- 35. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 3 4 Inorder Traversal
- 36. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 3 4 5 Inorder Traversal
- 37. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 3 4 5 Inorder Traversal
- 38. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 3 4 5 Inorder Traversal
- 39. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 3 4 5 6 Inorder Traversal
- 40. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 3 4 5 6 Inorder Traversal
- 41. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 3 4 5 6 Inorder Traversal
- 42. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 3 4 5 6 Inorder Traversal
- 43. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 3 4 5 6 8 Inorder Traversal
- 44. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 3 4 5 6 8 Inorder Traversal
- 45. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 3 4 5 6 8 Inorder Traversal
- 46. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 3 4 5 6 8 10 Inorder Traversal
- 47. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 1 2 3 4 5 6 8 10 Inorder Traversal
- 48.
- 49. 1 10 84 6 3 2 5 Binary Tree Insertion
- 50. 1 10 84 6 3 2 5 Binary Tree Insertion
- 51. 1 1 10 84 6 3 2 5 Binary Tree Insertion
- 52. 1 1 10 84 6 3 2 5 Binary Tree Insertion
- 53. 1 1 10 84 6 3 2 5 Binary Tree Insertion
- 54. 1 1 10 84 6 3 2 5 Binary Tree Insertion
- 55. 1 10 1 10 84 6 3 2 5 Binary Tree Insertion
- 56. 1 10 1 10 8 46 3 2 5 Binary Tree Insertion
- 57. 1 10 1 10 8 46 3 2 5 Binary Tree Insertion
- 58. 1 10 1 10 8 46 3 2 5 Binary Tree Insertion
- 59. 1 10 1 10 8 46 3 2 5 Binary Tree Insertion
- 60. 1 10 1 10 8 46 3 2 5 8 Binary Tree Insertion
- 61. 1 10 1 10 8 46 3 2 5 8 Binary Tree Insertion
- 62. 1 10 1 10 8 46 3 2 5 8 Binary Tree Insertion
- 63. 1 10 1 10 8 46 3 2 5 8 Binary Tree Insertion
- 64. 1 10 1 10 8 46 3 2 5 8 Binary Tree Insertion
- 65. 1 10 1 10 8 46 3 2 5 8 Binary Tree Insertion
- 66. 1 10 1 10 8 46 3 2 5 8 4 Binary Tree Insertion
- 67. 1 10 1 10 8 46 3 2 5 8 4 Binary Tree Insertion
- 68. 1 10 1 10 8 46 3 2 5 8 4 Binary Tree Insertion
- 69. 1 10 1 10 8 46 3 2 5 8 4 Binary Tree Insertion
- 70. 1 10 1 10 8 46 3 2 5 8 4 Binary Tree Insertion
- 71. 1 10 1 10 8 46 3 2 5 8 4 Binary Tree Insertion
- 72. 1 10 1 10 8 46 3 2 5 8 4 Binary Tree Insertion
- 73. 1 10 1 10 8 46 3 2 5 8 4 6 Binary Tree Insertion
- 74. 1 10 1 10 8 46 3 2 5 8 4 6 Binary Tree Insertion
- 75. 1 10 1 10 8 46 3 2 5 8 4 6 Binary Tree Insertion
- 76. 1 10 1 10 8 46 3 2 5 8 4 6 Binary Tree Insertion
- 77. 1 10 1 10 8 46 3 2 5 8 4 6 Binary Tree Insertion
- 78. 1 10 1 10 8 46 3 2 5 8 4 6 Binary Tree Insertion
- 79. 1 10 1 10 8 46 3 2 5 8 4 6 Binary Tree Insertion
- 80. 1 10 1 10 8 46 3 2 5 8 4 63 Binary Tree Insertion
- 81. 1 10 1 10 8 46 3 2 5 8 4 63 Binary Tree Insertion
- 82. 1 10 1 10 8 46 3 2 5 8 4 63 Binary Tree Insertion
- 83. 1 10 1 10 8 46 3 2 5 8 4 63 Binary Tree Insertion
- 84. 1 10 1 10 8 46 3 2 5 8 4 63 Binary Tree Insertion
- 85. 1 10 1 10 8 46 3 2 5 8 4 63 Binary Tree Insertion
- 86. 1 10 1 10 8 46 3 2 5 8 4 63 Binary Tree Insertion
- 87. 1 10 1 10 8 46 3 2 5 8 4 63 Binary Tree Insertion
- 88. 1 10 1 10 8 46 3 2 5 8 4 63 2 Binary Tree Insertion
- 89. 1 10 1 10 8 46 3 2 5 8 4 63 2 Binary Tree Insertion
- 90. 1 10 1 10 8 46 3 2 5 8 4 63 2 Binary Tree Insertion
- 91. 1 10 1 10 8 46 3 2 5 8 4 63 2 Binary Tree Insertion
- 92. 1 10 1 10 8 46 3 2 5 8 4 63 2 Binary Tree Insertion
- 93. 1 10 1 10 8 46 3 2 5 8 4 63 2 Binary Tree Insertion
- 94. 1 10 1 10 8 46 3 2 5 8 4 63 2 Binary Tree Insertion
- 95. 1 10 1 10 8 46 3 2 5 8 4 63 2 Binary Tree Insertion
- 96. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 Binary Tree Insertion
- 97. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 Binary Tree Insertion
- 98.
- 99. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 Binary Tree Deletion
- 100. 1 10 1 10 8 46 3 2 5 8 4 63 2 5 Binary Tree Deletion
- 101. 1 10 1 10 8 46 3 2 5 8 4 63 5 Binary Tree Deletion
- 102. 1 10 1 10 8 46 3 2 5 8 4 63 5 Binary Tree Deletion
- 103. 1 10 1 10 8 46 3 5 8 4 63 5 Binary Tree Deletion
- 104. 1 10 1 10 8 46 3 5 8 4 63 5 Binary Tree Deletion
- 105. 1 10 1 10 8 46 3 5 8 4 63 5 Binary Tree Deletion
- 106. 1 10 1 10 8 46 3 5 4 63 5 Binary Tree Deletion
- 107. 1 10 1 10 8 46 3 5 4 63 5 Binary Tree Deletion
- 108. 1 10 1 10 8 46 3 5 4 63 5 Binary Tree Deletion
- 109. 1 10 1 10 4 63 5 4 63 5 Binary Tree Deletion
- 110. 1 10 1 10 4 63 5 4 63 5 Binary Tree Deletion
- 111. 1 10 1 10 4 63 5 4 63 5 Binary Tree Deletion
- 112. 1 10 1 10 4 63 5 4 63 5 Binary Tree Deletion
- 113. 1 10 1 10 4 63 5 4 63 5 Binary Tree Deletion
- 114. 1 10 1 10 4 63 5 5 63 5 Binary Tree Deletion
- 115. 1 10 1 10 4 63 5 5 63 5 Binary Tree Deletion
- 116. 1 10 1 10 4 63 5 5 63 5 Binary Tree Deletion
- 117. 1 10 1 10 4 63 5 5 63 Binary Tree Deletion
- 118. 1 10 1 10 4 63 5 5 63 Binary Tree Deletion
- 119. 1 10 1 10 6 35 5 63 Binary Tree Deletion
- 120.
- 121. AVL Tree AVL treeis a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.
- 122. Red Black Tree •Every node has a color either red or black. • Root of tree is always black. • There are no two adjacent red nodes (A red node cannot have a red parent or red child). • Every path from root to a NULL node has same number of black nodes.
- 123. Splay Tree Automatically movesfrequently accessed elements nearer to the root for quick to access
- 124. Complexity in BST OperationAverage Worst Case Best Case Search O(log n) O(n) O(1) Insertion O(log n) O(n) O(1) Deletion O(log n) O(n) O(1)
- 125. Applications of BST •Used in many search applications where data is constantly entering/leaving, such as the map and set objects in many languages' libraries. • Storing a set of names, and being able to lookup based on a prefix of the name. (Used in internet routers.) • Storing a path in a graph, and being able to reverse any subsection of the path in O(log n) time. (Useful in travelling salesman problems). • Finding square root of given number • allows you to do range searches efficiently.
- 126.