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
6 More Terminologies Path A sequence of edges Length of a path number of edges on the path Depth of a node length of the unique path from the root to that node Height of a node length of the longest path from that node to a leaf all leaves are at height 0 The height of a tree= the height of the root the depth of the deepest leaf Ancestor and descendant If there is a path from n1 to n2 Proper ancestor and proper descendant of n1 n1 is an ancestor of n2. n2 is a descendant
6 More Terminologies Path A sequence of edges Length of a path number of edges on the path Depth of a node length of the unique path from the root to that node Height of a node length of the longest path from that node to a leaf all leaves are at height 0 The height of a tree = the height of the root = the depth of the deepest leaf Ancestor and descendant If there is a path from n1 to n2 n1 is an ancestor of n2, n2 is a descendant of n1 Proper ancestor and proper descendant
Example: UNIX Directory fuss mark* alex* bill* book course junk junk work* course+ chI.r ch2. r ch3. r cop3530* cop3212 fal198* spr99* sum99* fa!98* fa99米 yl.T syl. r grades progl r prog2 r prog2 r progl r grades Figure 4.5 UNIX directory
7 Example: UNIX Directory
Tree Operations Traversal, the most important we will not implement a general tree, so wont discuss Search Insertion Deletion
8 Tree Operations Traversal, the most important we will not implement a general ‘tree’, so wont discuss Search Insertion Deletion
Tree Traversal Used to print out the data in a tree in a certain order Pre-order traversal Print the data at the root Recursively print out all data in the leftmost subtree Recursively print out all data in the rightmost subtree
9 Tree Traversal Used to print out the data in a tree in a certain order Pre-order traversal Print the data at the root Recursively print out all data in the leftmost subtree … Recursively print out all data in the rightmost subtree
A drawing of tree with two pointers Struct TreeNode i double elementi // the data TreeNode* child; / FIRST child go to the next generation TreeNode* next;// next SIBLING: go to the same generation
10 A drawing of tree with two pointers … Struct TreeNode { double element; // the data TreeNode* child; // FIRST child : go to the next generation TreeNode* next; // next SIBLING : go to the same generation }
