Balanced Binary Search Trees • height is O(log n), where n is the number of elements in the tree• AVL (Adelson-Velsky and Landis) trees• red-black trees• get, put, and remove take O(log n) timeBalanced Binary Search Trees • Indexed AVL trees• Indexed red-black trees• Indexed operations also takeO(log n) timeBalanced Search Trees • weight balanced binary search trees• 2-3 & 2-3-4 trees• AA trees• B-trees• BBST • etc.AVL Tree• binary tree• for every node x, define its balance factorbalance factor of x = height of left subtree of x - height of right subtree of x• balance factor of every node x is -1, 0, or 1Balance Factors0 00010-1 010-11-1This is an AVL tree.HeightThe height of an AVL tree that has n nodes is at most 1.44 log2(n+2).The height of every n node binary tree is at least log2(n+1).AVL Search Tree0 00010-1 010-11-1107831530402025354560put(9)0 00010-1 010-11-190-10107831530402025354560put(29)0 00010010-11-1107831530402025354560290-1-1-2RR imbalance => new node is in right subtree of right subtree of blue node (node with bf = -2)put(29)0 00010010-11-110783153040253545600RR rotation.20029AVL Rotations• RR• LL• RL• LRRed Black TreesColored Nodes Definition• Binary search tree.• Each node is colored red or black.• Root and all external nodes are black.• No root-to-external-node path has two consecutive red nodes.• All root-to-external-node paths have the same number of black nodesExample Red Black Tree107815304020253545603Red Black TreesColored Edges Definition• Binary search tree.• Child pointers are colored red or black.• Pointer to an external node is black.• No root to external node path has two consecutive red pointers.• Every root to external node path has the same number of black pointers.Example Red Black Tree107815304020253545603Red Black Tree• The height of a red black tree that has n(internal) nodes is between log2(n+1) and 2log2(n+1).• java.util.TreeMap => red black treeGraphs• G = (V,E)• V is the vertex set.• Vertices are also called nodes and points.• E is the edge set.• Each edge connects two different vertices. • Edges are also called arcs and lines.• Directed edge has an orientation (u,v).u vGraphs• Undirected edge has no orientation (u,v).u v• Undirected graph => no oriented edge.• Directed graph => every edge has an orientation.Undirected Graph2381014591167Directed Graph (Digraph)2381014591167Applications—Communication Network• Vertex = city, edge = communication link.2381014591167Driving Distance/Time Map• Vertex = city, edge weight = driving distance/time.238101459116748667524453Street Map• Some streets are one way.2381014591167Complete Undirected GraphHas all possible edges.n = 1 n = 2 n = 3n = 4Number Of Edges—Undirected Graph• Each edge is of the form (u,v), u != v.• Number of such pairs in an n vertex graph is n(n-1).• Since edge (u,v) is the same as edge (v,u), the number of edges in a complete undirected graph is n(n-1)/2.• Number of edges in an undirected graph is <= n(n-1)/2.Number Of Edges—Directed Graph• Each edge is of the form (u,v), u != v.• Number of such pairs in an n vertex graph is n(n-1).• Since edge (u,v) is not the same as edge (v,u), the number of edges in a complete directed graph is n(n-1).• Number of edges in a directed graph is <= n(n-1).Vertex DegreeNumber of edges incident to vertex.degree(2) = 2, degree(5) = 3, degree(3) = 12381014591167Sum Of Vertex DegreesSum of degrees = 2e (e is number of edges)810911In-Degree Of A Vertexin-degree is number of incoming edgesindegree(2) = 1, indegree(8) = 02381014591167Out-Degree Of A Vertexout-degree is number of outbound edgesoutdegree(2) = 1, outdegree(8) = 22381014591167Sum Of In- And Out-Degreeseach edge contributes 1 to the in-degree of some vertex and 1 to the out-degree of some other vertexsum of in-degrees = sum of out-degrees = e,where e is the number of edges in the