COMP 352 Lecture Notes - Lecture 23: Avl Tree, Time Complexity, Directed Graph

• School: Concordia University
• Department: Computer Sci.
• Course: COMP 352
• Professor: T B A

Document Summary

Make a rotation one time after rotation the b goes on top (parent) Parent of b becomes left child and the other becomes right child. Time complexity is o(logn) which is the height. Go up the tree until you find the node with an imbalance. The child with the maximum height will be node y. Both child of y with the same height you take the right node and call it x. Then you do an in order traversal and the order of the visit will be a,b,c e. g. 47, 50, 52 is a,b, c respectively. Hash will not be in the exam - but should read in the book (it has a faster search) V is a set of nodes, called vertices. E is a collection of pairs of vertices, called edges. Vertices and edges are positions and store elements. Path such all its vertices and edges are distinct. Each edge is preceded and followed by its endpoints.