Inserção em Árvore AVL x Árvore SBB

Abstract. The use of binary trees to search is a good practice, but this tree not always perform as expected, to take full advantage of a binary tree that can provide it needs to be balanced, as it would do is not always a perfect balance of a tree ,this article aims to describe the AVL trees and SBB trees and its insertion methods, showing the main features of each of the models as alternatives for balancing the tree and tries to make a comparison of both methods showing the pros and cons of using of each.

Resumo. O uso de árvores binárias para busca é uma boa prática, mas nem sempre essa árvore tem o desempenho esperado, para tirar todo o proveito que uma árvore binária pode oferecer ela …exibir mais conteúdo…

A complexidade de inserção para a árvore AVL, média e pessimista é O(log n) [SZWARCFITER, 1994].

Figura 6 – Exemplo de balanceamento de um nodo

3. Árvore SBB:

A árvore SBB é uma estrutura binária de busca que diferente de outras árvores trabalha com dois tipos de apontadores, os verticais e os horizontais, sendo que os verticais simbolizam a descida de um nível da árvore e os horizontais que os elementos estão no mesmo nível, como pode ser visto na Figura 3, por isso uma árvore SBB possui duas alturas, a altura H que representa o número de apontadores verticais da raiz para um nó externo e a altura K que representa o maior número de apontadores entre a raiz e um nodo externo, K é maior que H sempre que existir um apontador horizontal na árvore. A árvore tem algumas restrições, sempre o número de apontadores verticais entre