Trees, Binary Trees and Binary Search Trees
Trees, Binary Trees, and Binary Search Trees
Trees Linear access time of linked lists is prohibitive Does there exist any simple data structure for which the running time of most operations(search insert, delete) is o(log N)? Trees Basic concepts Tree traversal Binary tree Binary search tree and its operations
2 Trees Linear access time of linked lists is prohibitive Does there exist any simple data structure for which the running time of most operations (search, insert, delete) is O(log N)? Trees Basic concepts Tree traversal Binary tree Binary search tree and its operations
Tr ees a tree T is a collection of nodes T can be empty (recursive definition) If not empty, a tree T consists of c a(distinguished)node r( the root B and zero or more nonempty sub-trees T1, T2, .. Tk root T1 T T3 T4 T Figure 4.1 Generic tree
3 Trees A tree T is a collection of nodes T can be empty (recursive definition) If not empty, a tree T consists of a (distinguished) node r (the root), and zero or more nonempty sub-trees T1 , T2 , ...., Tk
Tree can be viewed as a nested lists list of lists of lists Tree is also a graph
4 Tree can be viewed as a ‘nested’ lists: list of lists of lists … Tree is also a graph …
Some terminologies Figure 4.2 A tree Child and Parent Every node except the root has one parent a node can have a zero or more children Leaves Leaves are nodes with no children Sibling nodes with same parent
5 Some Terminologies Child and Parent Every node except the root has one parent A node can have a zero or more children Leaves Leaves are nodes with no children Sibling nodes with same parent