Home PageTitle PageContentsJJ IIJ IPage 1 of 14Go BackFull ScreenCloseQuitTrees, Binary Trees and TriesDynamic, nonlinear data structure are often useful in pruning informationA tree (a connected graph with no cycles) is a graph theoretical notionA graph G = (V, E) is a finite collection of vertices V and edges E• Usually n = kV k, and m = kEk• Digraph: E is a binary relation on V . Self loops are allowed. 0 ≤ m ≤n2andPv∈Vin − deg(v) = m• Undirected graph, or simply graph: E is a set of unordered pairs ofdistinct vertices. 0 ≤ m ≤n2∈ O(n2) andPv∈Vdeg(v) = 2mTries are tree like structure whose shape is dependent on the space in whichdata lives, rather than the data itself (for example, points in a two dimensionalworld)Binary trees are subtly different from trees and are used extensivelyHome PageTitle PageContentsJJ IIJ IPage 2 of 14Go BackFull ScreenCloseQuitAn Introduction to TriesName comes from retrieval, pronounced “trys”Can be used to implement a dictionary D on keys which are strings on analphabet. Indeed• Size of data structure is O(s) where s is the number of words in thedictionary• Inserts and deletes take time proportional to the length of the largeststring in D• Search time is O(m) where m is the length of the query stringAlso support prefix matching: Given a string X, find all strings in D thatcontain X as a prefixApplications: command completion, supporting (after preprocessing) wordmatches (find words in an article), Internet routingBasic computer data structure: Rooted ordered treeHome PageTitle PageContentsJJ IIJ IPage 3 of 14Go BackFull ScreenCloseQuitSimple TriesLet S be a set of s stringsfrom an alphabet Σ suchthat no string in S is aprefix of another string.A simple trie for S is anordered tree T with thefollowing properties1. Each node of T except the root is labeled with a character of Σ2. The ordering of the children of an internal node of T is determined bythe canonical ordering of Σ3. T has s external nodes, each associated with a string of S such that theconcatenation of the labels of the nodes on the path from the root to anexternal node v of T yields the appropriate string.Home PageTitle PageContentsJJ IIJ IPage 4 of 14Go BackFull ScreenCloseQuitSimple Trie ImplementationInternal nodes have anywhere between 1 and d children. The convention isto have a special marker character (. or Λ) in the alphabetImpl 1: Array allocated at each nodeImpl 2: First-child, next-siblingSpace hungry: If the s strings sum to length n, worst case number of nodesis O(n). Incremental construction costs O(dn). Operations costs O(dm)Home PageTitle PageContentsJJ IIJ IPage 5 of 14Go BackFull ScreenCloseQuitCompressed or Patricia TriesMain idea: Each internal node has at least two childrenIn a pessimistic version storestring at each node AND posi-tion on which the node discrim-inates (useful for supporting dy-namic inserts and deletes)Alternatively, store the index ofthe character position on whichthat node discriminates, not theentire string.Either way, number of nodes is proportional to the number of strings, not tothe sum of the lengths.Home PageTitle PageContentsJJ IIJ IPage 6 of 14Go BackFull ScreenCloseQuitSearching Patricia TriesSearch is easy (even if we don’t store the string in the nodes)• If an internal node has index i and the ith character of the search key isthe jth possible symbol, follow the jth pointer from that node• Upon reaching an external node, compare with the string stored. (Thisstep is necessary; the algorithm optimistically assumes that matches havehappened at all internal nodes. stickwould be confused with stock)• If the search key has fewer than i characters, it is not in the trieprefixQuery(x) is also implemented easily. Idea: If the search termi-nates at an internal node v, return all external nodes stored in the subtreerooted at vFor a random set of input data, the average height is O(logdn)Home PageTitle PageContentsJJ IIJ IPage 7 of 14Go BackFull ScreenCloseQuitThe Search Algorithm for Compressed Triesclass TrieNode {int p o s i t i o n ; TrieNode [ ] poi n t e r s ; S t r ing data ;/ / next index to match , p o i n t e r s based on al ph ab et}TrieNode f in d ( s t r i n g x , TrieNode v ) {i f ( v = = n u l l ) return v ;else {Boolean fullMatch = match ( x , v . data ) ;/ / t rue i f v . data i s s u b s t r i n g of xi f ( ! fullMatch ) {o u t p u t P a r t i a l ( x , v . data ) ;/ / als o a v a i l a b l e a t t h i s p oi nt Y1 ( Y2 ) ,/ / the p a rt of v . data t h a t matched ( didn ’ t )/ / s i m i l a r l y X2 ( not matched p a r t of X)/ / We need t hes e fo r i n s e r t !return v ;}Home PageTitle PageContentsJJ IIJ IPage 8 of 14Go BackFull ScreenCloseQuitSearch Algorithm Continuedelse {/ / All of v . data matched f u l l y or p a r t l y Xoutput ( v . data ) ;i f ( i s E x t e r n a l ( v ) ) return v ;/ / als o a v a i l a b l e ( p o ssi b l y nu l l ) X2 r e s t of Xelse {st ri pX (X , v . p o s i t i o n ) ;/ / remove p a r t s of X we don ’ t care about ./ / Dereference the r i g h t p o in t e ri f ( v [ x [ 1 ] ] = = n ul l ) / / nowhere to goreturn v ; / / remember we have X2 to r e t u r nelse f ind ( x , v [ x [ 1 ] ] ) ;}}}}The insert algorithm uses the status of the match step, as well as strings X2,Y1, Y2.Home PageTitle PageContentsJJ IIJ IPage 9 of 14Go BackFull ScreenCloseQuitPatricia Insert ExampleHome PageTitle PageContentsJJ IIJ IPage 10 of 14Go BackFull ScreenCloseQuitThe Insert Algorithmi n s e r t ( s t r i n g x , TrieNode r ) {v = f ind ( x , r ) ;i f ( v = = n u l l ) . . . / / s p e c i a l casei f ( fullMatch ) {i f ( X2 == n u l l ) return ;w = new TrieNode ( ) ;w. data = X2 ; w. p o s i t i o n = pos (X2 , x ) ;w. p o i n t e r s = n i l ; w. pa re nt = v ;v . c h i l d [X2 [ 1 ] ] = w;}else {u = …