Análise do Código de Árvores de Busca Binária e Exercícios

Estruturas de Dados II Análise do Código Árvore De Busca Binária e Exercícios Os códigos fontes em C deste material foram desenvolvidos pelo prof Dr André Kishimoto Prof Dr Ivan Carlos Alcântara de Oliveira httpsorcidorg0000000260207535 Estruturas de Dados Árvores Árvore de Busca Binária Binary Search Tree BST Conceito BST é uma árvore binária cujo o raiz armazena o elemento ID é denominada árvore de busca binária se Todo elemento armazenado na subárvore esquerda é menor que ID Nenhum elemento armazenado na subárvore direita é menor que ID As subárvores esquerda e direita também são árvores de busca binária Observe que a definição de árvore de busca binária BST é recursiva Exemplo Estruturas de Dados Árvores Árvore de Busca Binária Binary Search Tree BST Conceito Luís é o raiz desta árvore Os elementos Diogo Carlos e Feliciana pertencentes a subárvore esquerda são menores que Luís E os elementos da subárvore direita Raí Paulo Ronaldo são maiores que Luís Além disso as subárvores cujo raiz são Diogo e Raí também possuem esta característica logo esta árvore é uma árvore de busca binária BST Estruturas de Dados Árvores Árvore de Busca Binária Binary Search Tree BST Diagrama Binary Tree Binary Search Tree BST BTNode Estruturas de Dados Árvores Árvore de Busca Binária Binary Search Tree BST Exemplo F C B I G M Estruturas de Dados Árvores BST BSTjava Cama o método que retorna o menor valor da BST partindo do raiz public BTNode findMin return findMinHelpersupergetRoot Encontra o menor valor da BST a partir de um nó private BTNode findMinHelperBTNode node if node null return null else while nodehasLeftChild node nodegetLeft return node 92 21 74 133 raiz 85 38 40 35 Estruturas de Dados Árvores BST BSTjava Cama o método que retorna o maior valor da BST partindo do raiz public BTNode findMax return findMaxHelpersupergetRoot Encontra o maior valor da BST a partir de um nó private BTNode findMaxHelperBTNode node if node null return null else while nodehasRightChild node nodegetRight return node 92 21 74 133 raiz 85 38 40 35 Estruturas de Dados Árvores BST BSTjava Cama o método INTERNO que procura o predecessor do nó de ID da BST public BTNode findPredecessorString data return predecessordata false public BTNode findPredecessorIgnoreCaseString data return predecessordata true private BTNode predecessorString data boolean ignoreCase BTNode node searchdata ignoreCase return node null null predecessorHelpernode ignoreCase Considere id 85 38 92 21 74 133 35 raiz 85 Estruturas de Dados Árvores BST BSTjava Método que procura o predecessor do node da BST private BTNode predecessorHelperBTNode node boolean ignoreCase if nodehasLeftChild return findMaxHelpernodegetLeft else BTNode current node BTNode parent nodegetParent while parent null current parentgetLeft current parent parent currentgetParent return parent 38 92 21 74 133 35 raiz 85 Estruturas de Dados Árvores BST BSTjava Cama o método INTERNO que procura o sucessor do nó de ID da BST public BTNode findSuccessorString data return successordata false public BTNode findSuccessorIgnoreCaseString data return successordata true private BTNode successorString data boolean ignoreCase BTNode node searchdata ignoreCase return node null null successorHelpernode ignoreCase Considere id 38 38 92 21 74 133 35 raiz 85 Estruturas de Dados Árvores BST BSTjava Método que procura o sucessor do node da BST private BTNode successorHelperBTNode node boolean ignoreCase if nodehasRightChild return findMinHelpernodegetRight else BTNode current node BTNode parent nodegetParent while parent null current parentgetRight current parent parent currentgetParent return parent 38 92 21 74 133 35 raiz 85 Estruturas de Dados Árvores BST BSTjava Chama método que busca o nó de id informado a partir do raiz public BTNode searchString data return searchdata false public BTNode searchIgnoreCaseString data return searchdata true private BTNode searchString data boolean ignoreCase return searchHelpersupergetRoot data ignoreCase Compara duas strings com ou sem case sensitive private int diffCompareString s1 String s2 boolean ignoreCase return ignoreCase s1compareToIgnoreCases2 s1compareTos2 38 92 21 74 133 35 raiz 85 Estruturas de Dados Árvores BST BSTjava Busca o nó de id a partir do nó informado private BTNode searchHelperBTNode node String data boolean ignoreCase if node null return null int diff diffComparedata nodegetData ignoreCase if diff 0 return searchHelpernodegetLeft data ignoreCase else if diff 0 return searchHelpernodegetRight data ignoreCase else return node 38 92 21 74 133 35 raiz 85 Estruturas de Dados Árvores BST BSTjava Chama o método interno que insere um novo nó na BST contendo id e data public void insertString data insertdata false public void insertIgnoreCaseString data insertdata true private void insertString data boolean ignoreCase supersetRootinsertHelpersupergetRoot null data ignoreCase Inserir o 38 92 21 40 74 133 35 raiz 38 Estruturas de Dados Árvores BST BSTjava Método interno que insere um nó de ID private BTNode insertHelperBTNode node BTNode parent String data boolean ignoreCase if node null return new BTNodedata parent int diff diffComparedata nodegetData ignoreCase if diff 0 nodesetLeftinsertHelpernodegetLeft node data ignoreCase else if diff 0 nodesetRightinsertHelpernodegetRight node data ignoreCase else Nessa implementação não é permitida a inserção de duplicatas na BST return node 92 21 40 74 133 35 raiz 38 38 92 21 74 133 35 raiz 40 Estruturas de Dados Árvores BST BSTjava Chama o método interno que remove um novo nó na BST de id public void removeString data removedata false public void removeIgnoreCaseString data removedata true private void removeString data boolean ignoreCase supersetRootremoveHelpersupergetRoot data ignoreCase Estruturas de Dados Árvores BST BSTjava Chama o método interno que remove um novo nó na BST de id private BTNode removeHelperBTNode node String data boolean ignoreCase if node null return null int diff diffComparedata nodegetData ignoreCase if diff 0 nodesetLeftremoveHelpernodegetLeft data ignoreCase else if diff 0 nodesetRightremoveHelpernodegetRight data ignoreCase else node removeNodenode ignoreCase return node Estruturas de Dados Árvores BST BSTjava Método que atualiza os ponteiros do node removido private BTNode removeNodeBTNode node boolean ignoreCase if nodeisLeaf return null if nodehasLeftChild return nodegetRight else if nodehasRightChild return nodegetLeft else BTNode predecessor predecessornodegetData ignoreCase nodesetDatapredecessorgetData nodesetLeftremoveHelpernodegetLeft predecessorgetData ignoreCase return node