inserção árvore Splay
https://stackoverflow.com/questions/2008630
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Passando por alguns exercícios para aprimorar minhas habilidades de árvore binária, decidi implementar uma árvore splay, conforme descrito na Wikipedia:. Splay árvore
Uma coisa que eu não estou recebendo é a parte sobre a inserção.
Ele diz:
Em primeiro lugar, buscamos x na árvore splay. Se x não existir, então não vai encontrá-lo, mas seu nó pai y. Em segundo lugar, realizar uma operação de splay em y que irá mover y à raiz da árvore splay. Em terceiro lugar, inserir os novos x nó como raiz de uma maneira apropriada. Desta forma, quer y é deixado ou criança direita da nova raiz x.
A minha pergunta é esta: O texto acima parece excessivamente concisa em comparação com os outros exemplos no artigo, por que isso? Parece que há algumas armadilhas deixadas de fora aqui. Por exemplo, depois splaying o nó y até a raiz, não posso cegamente substituir raiz com x, e tack y sobre x como qualquer criança para a esquerda ou direita.
Vamos assumir o valor ainda não existir na árvore.
Eu tenho esta árvore:
10
/ \
5 15
/ \ \
1 6 20
e eu quero inserir 8. Com a descrição acima, vou encontrando a 6 nós, e em uma árvore binária normal, 8 seria acrescentado como uma criança direita do 6-nó, no entanto aqui eu primeiro tenho para afunilar o 6-node até root:
6
/ \
5 10
/ \
1 15
\
20
então qualquer um destes dois são manifestamente errada:
8 8
\ /
6 6
/ \ / \
5 10 5 10
/ \ / \
1 15 1 15
\ \
20 20
6 is not greater than 8 10 is not less than 8
parece-me que a única maneira de fazer o espalhamento primeiro, e depois adicionando corretamente o novo valor como root significaria que tenho de verificar os seguintes critérios (para adicionar o nó splayed como o filho esquerdo do novo root) :
- o nó I espalhados à raiz é menor do que a nova raiz (6 <8)
- a criança mais à direita do nó I espalhados à raiz também é menor do que a nova raiz (20 8)
No entanto, se eu fosse para dividir o nó I abertos, tomando a criança direita e anexando-o como o filho direito do novo nó, gostaria de obter isto:
8
/ \
6 10
/ \
5 15
/ \
1 20
Mas, se esta alteração simples sempre vai me dar uma árvore correto? Estou tendo um tempo difícil chegar com um exemplo, mas isso poderia levar ao seguinte:
- O novo valor que deseja adicionar é maior do que a raiz temporária (o nó I espalhados à raiz), mas também mais elevada do que a criança mais à esquerda do filho direito da raiz temporário?
Ie. uma árvore que seria basicamente parecido com este após splaying, mas antes de substituir a raiz?
10
/ \
5 15
/ \
11 20
e eu quero adicionar 13, o que tornaria a nova árvore como esta:
13
/ \
10 15
/ / \
5 11 20 <-- 11, on the wrong side of 13
ou pode isso nunca acontecer?
A minha segunda pergunta é a seguinte: não seria muito mais fácil simplesmente reescrever a operação da seguinte forma:
Em primeiro lugar, buscamos x na árvore splay. Se x não existir, então não vai encontrá-lo, mas seu nó pai y. Então nós adicionar o novo nó ou como uma criança para a esquerda ou direita do nó pai. Em terceiro lugar, realizar uma operação de splay no nó nós adicionamos que irá mover o novo valor à raiz da árvore splay.
ênfase minha para mostrar o que eu mudei.
Solução
Eu não vejo como o problema que você descreve pode acontecer. Se você deseja inserir 13 nesta árvore que você primeiro tem que descobrir onde ele seria:
10
/ \
5 15
/ \
11 20
De 10 de você ir para a direita, a partir de 15 de você ir para a esquerda, de 11 de você ir para a direita ... e então você não tem mais elementos. Se 13 tinha sido na árvore, teríamos encontrado-lo como uma criança direito de 11. Assim, de acordo com a regra que realizar uma operação de splay no dia 11 que irá mover 11 para a raiz da árvore splay:
11
/ \
10 15
/ \
5 20
Em seguida, adicionar 13 como a nova raiz, com 11 como o filho esquerdo:
13
/ \
11 15
/ \
10 20
/
5
Agora, não há nenhum problema.
Em primeiro lugar, buscamos x na árvore splay. Se x não existir, então não vai encontrá-lo, mas seu nó pai y. Em seguida, adicionar o novo nó ou como uma criança para a esquerda ou direita do nó pai. Em terceiro lugar, realizar uma operação de splay no nó nós adicionamos que irá mover o novo valor para a raiz da árvore splay.
Isso parece-me que ele iria trabalhar muito, mas se eu fosse você, eu tinha acabado de tentar implementar a versão como descrito na Wikipedia desde muitas pessoas testei isso e ele já está bem documentada.
Outras dicas
"Splay Tree" imediatamente me fez lembrar de um artigo no CUJ eu li um tempo atrás, que você pode encontrar algumas dicas lá: Implementação Splay Árvore em C ++ .
Em terceiro lugar, inserir o novo nó x como root de forma adequada. Desta forma, quer y é deixado ou criança direita da nova raiz x.
Sim, mas esta nova raiz x tem que ter 2 filhos, é por isso que esta frase pode parecer confuso.
o novo nó seria adicionado à árvore como uma árvore de busca binária normal. Em seguida, o novo nó seria espalhado para ser a raiz ou o primeiro nível da raiz. Além disso, quando inserir um novo nó, precisamos encontrar o local para colocá-lo, por isso fazemos um achado. E todas as operações, incluindo achado em um disparador árvore splay uma operação splay. Pode ser é por isso que o artigo da Wikipedia descreve-o assim. Eu só inserir o novo nó e splay-lo. De qualquer forma, a árvore se torna mais equilibrado do que era. funciona muito bem aqui
