Scribd
Upload
3 views5 pages

Unit2 Daa

The document provides an overview of various tree data structures, including Red-Black Trees, B-Trees, Binomial Heaps, Fibonacci Heaps, and Skip Lists, detailing their properties, insertion and deletion algorithms, and time complexities. Red-Black Trees are highlighted for their self-balancing properties and efficiency in data operations, while B-Trees are noted for their use in databases. The document also discusses the structure and operations of Skip Lists, emphasizing their probabilistic nature for efficient searching.

Uploaded by

Sunil Kumar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
3 views5 pages

Unit2 Daa

The document provides an overview of various tree data structures, including Red-Black Trees, B-Trees, Binomial Heaps, Fibonacci Heaps, and Skip Lists, detailing their properties, insertion and deletion algorithms, and time complexities. Red-Black Trees are highlighted for their self-balancing properties and efficiency in data operations, while B-Trees are noted for their use in databases. The document also discusses the structure and operations of Skip Lists, emphasizing their probabilistic nature for efficient searching.

Uploaded by

Sunil Kumar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
‘Red Black Tree “a Red-lack Tree Is a seifbalancing binary search tee (8ST) ‘used in comauter science for efficient data storageand retrieval. “Each node in a Red-Black Tee has an extra property, which is @ color, either red or black, which helps maintain balanced tree properties. Properties of RB Tee Each nodes red or black. ‘The roat and all NIL leaves are black. tak child ened < right chile (EST property. [No red nodehas a red child. |All paths trom any node to its leaves have the same number of black nades. teens ‘Why do we use RE Tree |e) Red-Black Trees keep insertion, deletion, and lookup efficient ‘with Oflogn) time complexity due to self-balancing. “@ Ideal for scenarios with frequent insertions and deletions, Ike databases and file systems. Node Structure Of RB Tree \@ Each node has value, color (RED of BLACK) eft (left child, right {ight child), and parent (parent node). insertion algorthmyoperation of RB Tee “o nsert as ina regular BST: ‘+ Insert the newnodeas @ red node, fllowing standard BST insertion rules. “+ FicRed Black Violations: ‘tthe parant i blade No action is neadad (ll properties are satisfied). 4 tthe parant i rea: © Case: the undecred: © Reeolor the parent and uncleto black and the _prandparentto red. © Move upto the grandparent and repeat the process if needed © Cased: the unde fs black: © tenew node's na “agra” configuration (itt rght or righ-e, rotate to make ita staight configuration efteft o right-igt)- = Perform a rotation around the grandparent to fix ‘we wesstructue. © Recolor nodes as needed to maintain the ed Black properties. “o-Enaure the Raat is Blac: ‘Aer ll adjustments set the root node to black fis not already. Seen ‘ned lock Mees nae oe gotien ue: como re odescan stand exo cach ‘tet Raparentyreiwety Bld col, ond he rej con Rance Chat mach an!" Insertion in RB Tree [ Example] Paw ve oe os Compleaity & Inuzrtion: Oftagn) on average, Ola) in theswarst case. (unbalanced wee) ‘+ Search: Oflogn) on average, Ofn) in the worst case. Deletion in Red -Black Tree (0 perations/Algorithen) ‘© Case 1: Ifthe nade to deletels a red leaf just deleteit. ‘© Case 2:1f Is the root, delete itand make the new root black, Cae}: Dertege era (© Case 3:18 sibling and its children are black: ‘© Remove DB and makethe sibling ed, (# If 085 parents black, make its; otherwise, make it black. ex om Cue 4085 stings re ‘© Swap colors af theparent and sibling. ‘¢_Powte towards 0a, then recheck the cases. Sy geay ~ 4+ cae 5108 sibtngis back, wth aback ar ed anda ved ‘nant chile “+ Seap colors of thesibling andits re child. |# Rotate the sibling away from D8, then goto Case6. ‘© Case 6: 1f 085 siblingis black, with a ved far chil ‘© Swap colors af theparent and sibling. |# Rotate towards D8, make the far child black, and remove Deletion in Rb Tree [Example] (e AGteeisa self-balancing tee data structure that maintains sorted data and allows searches, sequential access, insertions, ‘and deletions in logarithmic time. ‘# Every node has at most children. '* Every node, except forthe root and the leaves, has at least m2] chitaren. '@Theroot node has at least two children untess itis aleat. (© All leaves appearon the samelevel_ '* Anon-leaf node with k-children contains k-2 keys. Node Structure ‘+ STRUCTURE Node: keys (array of values) children (array of child pointers), sheaf (boolean) Insertion Algorithm/Operation in 8-Tree + Tee isematy: '¢) Create a oot andinsert the key. “* Find the Target Node: '¢ Traverse to the appropriate leaf node for insertion, “e Node is Full: '¢ Insert key in sorted order, then split: © Move the middlekey up wo the parent. © Unftkays became the eft child right keys Became the right chit “# Node is Not Full © Insert key in sorted orc. Insertion in &-Tree [ Example. order 3] Seen The dace wets eet: ‘©The minimum ounber of ys ocd con havest- 1 (©The mmamar numer ofteysa ode nave 2 * t= ‘Fhe minimum eurnbe of cua a ew root nade can have (© Te maamam aumoerofcntoree a nae coe have? t Deletion in B-Tree [Operations/Algorithen) ‘© Case E Deleting axey in a Leaf Node No violation of minimum keys: Simply remave the key. (© Violation af rinimum keys: Barrow from a sibling (left. or right). neither siblinghas enough keys, merge with a sibling. ‘© Case m Deleting a Key in an internal Node (* Replace within-order predecessor (if lefechildnas ‘suficient keys) ‘= Replace within-order successor (if right child has. ‘sufficient keys) (+ Ifachild has minimum keys: Merge the let and right ‘children yemove keys fromthe parent. (© Case mt Shrinking Tee Height |S After deleting from internal node: Ifthe parent nade has, ‘fewer than theminimum keys, borrow fram a sibling or marge the node with its sibling and adjust thereat. complexity 1 Search Oogn) ‘Quanta 215,256 Binomial Heap 4 Abjnomial heaps a sorted data structure supporting ficient {insertion and deletion in amortized time. ‘© Inconsists af acallection of binceial wees. Insertion: Oflogn) Deletion: 0(108n) Properties ofa Binomial Tee (6): '@ Number of nodes: 2° + Height © Nodes at depth |: Cikj) (for 1-0...) ‘= oot degree: k (with children being By..:,..60 [feamleft 10 ight) (Cases in Union Heap ‘© Different degrees: Move to thenext node. '@ Teee same degrees: Move to thenext node. + Twosame degrees: ‘© If ke/fx) ckeyjnedt x], makenext x child of x. + If keys) >keyinect x], makex child of next x. Insertion Algorithm / Operation of Binomial Heap '@ Create a New Node:Make a new binomial heap, H”,thathas just ‘one node with the valueta be inserted, '@) Merge Heaps:Combine with the existing heap H ‘+ During the merge: ‘© Align woos by order. '¢ ftwo trees navethe same order, link them together to create @ tee ofthe next higher order. + Repeat untl theres only one reef each orderiathefinal heap. “+ Link Tees: When linking two trees of the sarme order, makethe ‘woo with thesmatler root key the roat ofthe combined tae to beep the min-heap property. |e Update Root List:Encure the final heap has only onetree of each oder. ‘nsertion Example dolort 8! “Foaort g3* @S Sor oe soa} tot Souer} 048 Sgesa gep doterd 45 C22, tt Pee °ese treed Go tated @®. a Cea ee “wom [Deletion Algorithm/ Operations in Binomial Heap fonction DELETE_HAN())> di Step &: ruinNode = FIND_MIN_NGOE(H) Uf Step 2: Reverse the childven of ‘children = REVERSE|minhiode chil Ui Seep Acaharge ts sewecsed aAdoG a with We shag ME H=UNION(H,childeen) ‘Deletion Example : we 6 see bathe bp be vepetianh ty ‘complexity + TieComplesiy: O(nlogn) Spice Complexity: O(n) Fibonacci Heap 4 Afibonacti Heap is a data structure that extends the concent of ‘2 binary heap andbinomal hp to support ecient mergingot heaps 4 Tis primarily used to optinizeijtstras Algorithm and Pins Algoethm. Properties ofa Rbonacc Heap ® Itis a set of min heap-ordered trees. (Le. The parent is always ‘smaller than the children.) 4+ -Aposmer is maintained atthe minimum element node. lconsists af a set of marked nodes. (Decrease key operation) ‘The tees within a Fibonacci heap ave unordered but rooted, @—o 9. o—o e205 eo © oS &: parent € pointer te parent nese (NULL fost) rild € pointer te ane of its children ing (creulardou hy inked list ‘Add newNade to the oat list of H= 1 MminNode | NULL Set'minNode =newNode Extrad Minimum Function ExtactMin(FibHeap H): 2eHaminNede Wz NUL: Forebch child of emave xfrom t's child list ‘Add x19 the root list of H Setxparent= NULL Revove from the root let FH Mr=eigne Set minNode =NULL fhe Set minNode =[Link] ConsolidateiH) Decrement W nodeCount by 2 Return zhkey ‘maxbegree € floorilog2/H nadeCount) +1 ‘Geate an array Aofsize maxDegree initialized to NULL Fac each root node w in the rt is: xew depres © degree While Aldegree) ¢ NULL ye Aldesree) Trckey> vikey ‘Snap wand y Unk yiox Aldegree) € NULL degree © degree +1 Aldegree) €x Himintlode © NULL Foreach entryin & WAG] + NULL: ‘dd Ali) to the root list af If MaminNode is NULLO* AB] ey Set H mintoge =A\4) (ensures the minimum node of te new heaps the smal the twa heaps.) 3. Merge the mot ists of Mi and H2: “Append HZ roat list ta M1's root it: Update W's root list te this combined list. [Link] the number of nodes: Min =Min +H2n (sum of the nodes in i and H2) 5 Delete Hi and M2 te free memary (opsenal)- 6. Return the new heap H. tof Decrease Key Function DecreateveyFibHeap H. Mode x nt newt: ryrernreres Throw enor Rew teyis greater than cuen ey? aiey=newtey Te tperen hye MOLL and hey they paren) asenaingcuty A ikey

You might also like