2-3 Tree, Everything you need to know

Postado por em

  1. 1. 2-3 TREE Estrutura de Dados II Team: Augusto Teixeira Carlos Littbarski Jardel Rodrigues Victor Apuena Professor: Alandson Meireles
  2. 2. History TREE 2-3 WAS THE FIRST MULTIPATHS TREE, INVENTED BY J. E. HOPCROFT IN 1970. 2-3 trees are an isometry of AA trees, which means that they are equivalent data structures. In other words, for all 2-3 tree, there exists at least one AA tree with data elements in the same order. 2-3 trees are balanced, meaning that each right, center and left subtree contains the same or close to the same amount of data. John E. Hopcroft
  3. 3. Characteristics - ARE TREES EASY TO SCHEDULE - ARE MULTIVITIES TREES - IT'S NOT A BINARY TREE - TREES 2-3 ARE SIMILAR TO TREES 2-3-4. - 2-3 SAY ABOUT THE QUANTITY OF CHILDREN THAT THE TREE CAN HAVE (AS WELL AS IN 2-3-4) - PERFECTLY BALANCED
  4. 4. Advantagens Perfectly balanced tree Quick search Easy implementation Delayed removal Disadvantages
  5. 5. Propriedades - Each node contains one or two keys; - Each inner node has two children if it has one key, or three if it has two keys; - All the leaves are on the same level. - All data is sorted NODE WITH 1 SON a a b P Q NODE WITH 2 SONS P Q R
  6. 6. INSETION
  7. 7. Insertion: Empty Tree Add‘B’
  8. 8. Insertion: Empty Tree b If the Tree is empty: Create a node and add the value to the node Rule #1
  9. 9. Insert: Node 1-key node b Add ‘A’ a
  10. 10. Insert: Node 1-key node b Otherwise, locate the node to which the value belongs. If the node has only 1 value, add the value on the node. a Rule #2 Rula #3 Insert key in the node always in an orderly fashion.
  11. 11. Insert: 2-key node a b c Add ‘C’
  12. 12. Insert: 2-key node c If the leaf node has more than two values, divide the node and promote the median of the three values for the parent. a b Regra #4 Number of keys burst Promote the median Break the knot and make the call
  13. 13. Insert: 2-key node ca b Key > BKey < B We with 1 key should always have 2 children
  14. 14. Insert: Rules c Insert “D” a b
  15. 15. Insert: Rules c Insert “E” a b d e
  16. 16. Insert: Rules ca b d e If the leaf node has more than two values, divide the node and promote the median of the three values for the parent.Rule #4
  17. 17. Insert: Rules ca b d e - Each inner node has two children if it has one key, or three if it has two keys;
  18. 18. Insert: Rules: Regras ca b d e Nºs > BNºs < B keys > B & < D
  19. 19. Let's see if we understand everything?
  20. 20. Empty tree. Enter # 50
  21. 21. Insert #1 50
  22. 22. Insert #25 1 50
  23. 23. Insert #25 1 50 25
  24. 24. Node full! 1 5025
  25. 25. # 25 Promoted | Balanced Tree 1 50 25
  26. 26. Insert #35 1 50 25
  27. 27. Insert #40 1 35 25 50 40
  28. 28. Node full! 1 35 25 5040
  29. 29. #40 Promoted 1 4025 5035
  30. 30. 1 4025 5035 Balanced Tree????????
  31. 31. 1 4025 5035 No!
  32. 32. #Broken property 1 4025 5035 - Node with 2 keys must have 3 children
  33. 33. Node (35,50) Split 1 4025 5035
  34. 34. Balanced tree! Enter # 15 1 4025 5035
  35. 35. 1 35 25 50 40 Okay! Insert #10 15 10
  36. 36. 1 35 25 50 40 Node full! 1510
  37. 37. 1 35 25 50 40 Limit burst! AGAIN!!! 15 10
  38. 38. 25 4010 If the parent then has three values, continue to divide and promote, forming a new root node if necessary Rule #5 1 35 5015 Limit burst! AGAIN!!!
  39. 39. 25 40 Mama's lovely thing !!! 10 1 35 5015
  40. 40. Enough right? Let's go to the next! 1 35 25 50 40 15 10
  41. 41. SEARCH
  42. 42. 2-3 Tree ▪ Simple Node: ▪ Contains a key and two links; A left link to a 2-3 tree that has keys smaller than the node key; And a direct link to a 2- 3 tree that has larger braces;
  43. 43. 2-3 Tree ▪ Double Node: ▪ Contains two keys and three links: a left link to a 2-3 tree that has smaller keys; And a middle link to a 2-3 tree that has keys between the two keys of the node; And a direct link to a 2-3 tree that has larger braces;
  44. 44. Search in a tree 2-3 - It always starts at the root; - If the searched item is not in the root, it identifies the child node of the root in which it can be and continues to this node; - If the item has a value greater than the root, go to the right of the tree, otherwise go to the left; - The process repeats itself until the item is found;
  45. 45. Search example Tree 2-3 3 30 29 5010 20 12 18 40 43 7060 Searching the 18
  46. 46. 3 30 29 50 12 18 10 20 40 43 7060 Search example Tree 2-3 Searching the 18
  47. 47. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 18
  48. 48. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 18
  49. 49. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 18
  50. 50. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 18
  51. 51. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 18
  52. 52. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 18
  53. 53. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 18
  54. 54. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 65
  55. 55. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 65
  56. 56. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 65
  57. 57. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 65
  58. 58. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 65
  59. 59. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 65
  60. 60. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 65
  61. 61. 3 30 29 5010 20 12 18 40 43 7060
  62. 62. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 43
  63. 63. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 43
  64. 64. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 43
  65. 65. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 43
  66. 66. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 43
  67. 67. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 43
  68. 68. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 43
  69. 69. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 43
  70. 70. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 3
  71. 71. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 3
  72. 72. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 3
  73. 73. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 3
  74. 74. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 3
  75. 75. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 3
  76. 76. 3 30 29 5010 20 12 18 40 43 7060 Search example Tree 2-3 Searching the 3
  77. 77. REMOVAL
  78. 78. Removing a tree 2-3 - Removing an item from a tree 2-3 is approximately the reverse of the insertion process; - To remove an item, we must first look for it; - If the item to be removed is on a sheet with two items; - We simply exclude it; - We remove it by changing it from the trees;
  79. 79. Removing #45 - Find #45 1 35 25 60 10 6545 40 50 15
  80. 80. Removing #45 1 35 25 60 10 6545 40 50 15
  81. 81. Removing #45 1 35 25 6015 10 6550 40 50
  82. 82. Removing #45 1 35 25 6015 10 6550 40 60
  83. 83. Removing #45 1 35 25 15 10 6550 40 60
  84. 84. Removing #45 - procurar número 40 1 35 25 15 10 6550 40 60
  85. 85. Removing #45 1 35 25 15 10 6550 40 60
  86. 86. Removing #45 1 35 25 15 10 6550 35 60
  87. 87. Removing #45 1 25 15 10 6550 35 60
  88. 88. After removing #45 1 25 15 10 6535 60 50
  89. 89. Removing #1 - Find #1 1 25 15 10 6535 60 50
  90. 90. 1 25 15 10 6535 60 50 Removing #1
  91. 91. 25 15 10 6535 60 50 Removing #1
  92. 92. 25 10 6535 60 50 15 Removing #1
  93. 93. 25 10 6535 60 50 15 Removing #1
  94. 94. 25 10 6535 60 5015 Removing #1
  95. 95. - Find #10 25 10 6535 60 5015 Removing #10
  96. 96. 25 10 6535 60 5015 Removing #10
  97. 97. 25 6535 60 5015 After Remove #10
  98. 98. 25 6535 60 5015 Removing #35
  99. 99. 25 6535 60 5015 Removing #35
  100. 100. 25 65 60 5015 Removing #35
  101. 101. 25 65 60 5015 Removing #60
  102. 102. 25 65 60 5015 Removing #60
  103. 103. 25 65 65 5015 Removing #60
  104. 104. 25 65 5015 Removing #60
  105. 105. 25 655015 Removing #60
  106. 106. 25 655015 Removing #60
  107. 107. 25 655015 Removing #60
  108. 108. 25 5015 Removing #60
  109. 109. 25 5015 Removing #50
  110. 110. 25 5015 Removing #50
  111. 111. 25 15 Removing #50
  112. 112. 2515 After Remove #50
  113. 113. 2515 Removing #25
  114. 114. 15 Removing #15
  115. 115. Empty Tree
  116. 116. REFERÊNCIAS USP - “Instituto de Matemática e Estatística”. Disponível em: https://www.ime.usp.br/~gold/cursos/2002/mac2301/aulas/b-arvore/ LAFORE - ESTRUTURA DE DADOS E ALGORÍTMOS EM JAVA - 2ª EDIÇÃO WIKIPEDIA - https://pt.wikipedia.org/wiki/%C3%81rvore_2-3 Gross, R. Hernández, J. C. Lázaro, R. Dormido, S. Ros (2001). Estructura de Datos y Algoritmos Prentice Hall Ellio B. Koffman Paul A. T. Olfgang (2006) : Objetos, Abstração, Estruturas de dados e projeto usando C++
  117. 117. Thank you very much!!!

Comentários

Postar um comentário