Binary Tree Representation Of 2-3-4 TreesRepresentation Of 4-nodeRepresentation Of 3-nodeRepresentation Of 2-nodeExampleProperties Of Binary Tree RepresentationRed Black TreesSlide 82-3-4 & Red-Black EquivalenceRed Black TreeTop-Down InsertRoot Is A 4-node4-node Left Child Of 2-node4-node Left Child Of 3-nodeSlide 154-node Middle Child Of 3-nodeSlide 174-node Right Child Of 3-nodeTop-Down DeleteRed-Black AnalysisBinary Tree Representation Of 2-3-4 Trees•Problems with 2-3-4 trees.•2- and 3-nodes waste space.•Overhead of moving pairs and pointers when changing among 2-, 3-, and 4-node use.•Represented as a binary tree for improved space and time performance.2-3-4 node structureLC P1 LMC P2 RCRMC P3Representation Of 4-nodex y za b cdab c dzyxRepresentation Of 3-nodex ya bcab cyxabyxcorRepresentation Of 2-nodeaxbxabExample107815304020253545603Properties Of Binary Tree Representation•Nodes and edges are colored.The root is black.Nonroot black node has a black edge from its parent.Red node has a red edge from its parent.•Can deduce edge color from node color and vice versa.•Need to keep either edge or node colors, not both.Red 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 nodesRed 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.2-3-4 & Red-Black Equivalence107815304020253545603Red Black Tree•The height of a red black tree that has n (internal) nodes is between log2(n+1) and 2log2(n+1).•C++ STL implementation•java.util.TreeMap => red black treeTop-Down Insert•Mimic 2-3-4 top-down algorithm.•Split 4-nodes on the way down.Root Is A 4-nodex y za b cdxyzab c dab c dzyxab c dzyx4-node Left Child Of 2-nodew x ya b cdze wzyab c dxezwyxa b c dezwyxa b c de4-node Left Child Of 3-nodev w xa b cdfzyevxabc dw y zfeyvxwa b c dze fyvxwa b c dze f4-node Left Child Of 3-nodev w xa b cdfzyevxabc dw y zfeyvxwa bzefcdyvxwa b c dze f4-node Middle Child Of 3-nodevwyxb czafdexwvyadb czefw x yb c defzvawab cfyd ev x z4-node Middle Child Of 3-nodedzwyxb cvafexwvyadb czefw x yb c defzvawab cfyd ev x z4-node Right Child Of 3-node•One orientation of 3-node requires color flip.•Other orientation requires RR rotation.Top-Down Delete•Mimic 2-3-4 top-down delete.•Color flip followed by possible rotation.Red-Black Analysis•Expect less memory required than by 2-3-4 representation.4-nodes take less space in 2-3-4 mode2- and 3-nodes do better in red-black tree•Less time required by 4-node splits when red-black representation is used.•O(log n) rotations per