Binary Search Tree order of insert when we have an estimate ahead of time












3















I am currently reading "Algorithms Fourth Edition" by Robert Sedgewick and Kevin Wayne. I have question about:




3.2.5 Suppose that we have an estimate ahead of time of how often search keys are to be accessed in a BST, and the freedom to insert items in any order that we desire. Should the keys be inserted into the tree in increasing order, decreasing order of likely frequency of access, or some other order? Explain your answer.




Obviously, the perfect situation is to have at root the item that is most accessed, then at its direct ancestors, the next items in terms of frequency of access and so on and so on.
However, this is BST and as such we have to insert them according to its specifics.
Shall I consider in this task all the combinations?



For example, if we have items 1 (accessed 1000 times), 2 (999 times) and 3 (999). The tree with root 2 and ancestors 1 and 3 is the best solution I think.
Its sounds logical to me, to strive to have balanced tree. However this again depends on the input. If we have smallest item accessed 10 000 times and next 10 items accessed only once, then the smallest shall be root and the tree will not
be perfectly balanced.



I will also appreciate guidance, not direct answers.






algorithm search binary-search-tree







share|improve this question




















  • 2





    probably related to static optimal binary search tree

    – juvian
    Nov 24 '18 at 21:20











  • Thanks @juvian, optimal BST is exactly what I was searching for.

    – John
    Dec 5 '18 at 20:14
















3















I am currently reading "Algorithms Fourth Edition" by Robert Sedgewick and Kevin Wayne. I have question about:




3.2.5 Suppose that we have an estimate ahead of time of how often search keys are to be accessed in a BST, and the freedom to insert items in any order that we desire. Should the keys be inserted into the tree in increasing order, decreasing order of likely frequency of access, or some other order? Explain your answer.




Obviously, the perfect situation is to have at root the item that is most accessed, then at its direct ancestors, the next items in terms of frequency of access and so on and so on.
However, this is BST and as such we have to insert them according to its specifics.
Shall I consider in this task all the combinations?



For example, if we have items 1 (accessed 1000 times), 2 (999 times) and 3 (999). The tree with root 2 and ancestors 1 and 3 is the best solution I think.
Its sounds logical to me, to strive to have balanced tree. However this again depends on the input. If we have smallest item accessed 10 000 times and next 10 items accessed only once, then the smallest shall be root and the tree will not
be perfectly balanced.



I will also appreciate guidance, not direct answers.






algorithm search binary-search-tree







share|improve this question




















  • 2





    probably related to static optimal binary search tree

    – juvian
    Nov 24 '18 at 21:20











  • Thanks @juvian, optimal BST is exactly what I was searching for.

    – John
    Dec 5 '18 at 20:14














3












3








3








I am currently reading "Algorithms Fourth Edition" by Robert Sedgewick and Kevin Wayne. I have question about:




3.2.5 Suppose that we have an estimate ahead of time of how often search keys are to be accessed in a BST, and the freedom to insert items in any order that we desire. Should the keys be inserted into the tree in increasing order, decreasing order of likely frequency of access, or some other order? Explain your answer.




Obviously, the perfect situation is to have at root the item that is most accessed, then at its direct ancestors, the next items in terms of frequency of access and so on and so on.
However, this is BST and as such we have to insert them according to its specifics.
Shall I consider in this task all the combinations?



For example, if we have items 1 (accessed 1000 times), 2 (999 times) and 3 (999). The tree with root 2 and ancestors 1 and 3 is the best solution I think.
Its sounds logical to me, to strive to have balanced tree. However this again depends on the input. If we have smallest item accessed 10 000 times and next 10 items accessed only once, then the smallest shall be root and the tree will not
be perfectly balanced.



I will also appreciate guidance, not direct answers.






algorithm search binary-search-tree







share|improve this question
















I am currently reading "Algorithms Fourth Edition" by Robert Sedgewick and Kevin Wayne. I have question about:




3.2.5 Suppose that we have an estimate ahead of time of how often search keys are to be accessed in a BST, and the freedom to insert items in any order that we desire. Should the keys be inserted into the tree in increasing order, decreasing order of likely frequency of access, or some other order? Explain your answer.




Obviously, the perfect situation is to have at root the item that is most accessed, then at its direct ancestors, the next items in terms of frequency of access and so on and so on.
However, this is BST and as such we have to insert them according to its specifics.
Shall I consider in this task all the combinations?



For example, if we have items 1 (accessed 1000 times), 2 (999 times) and 3 (999). The tree with root 2 and ancestors 1 and 3 is the best solution I think.
Its sounds logical to me, to strive to have balanced tree. However this again depends on the input. If we have smallest item accessed 10 000 times and next 10 items accessed only once, then the smallest shall be root and the tree will not
be perfectly balanced.



I will also appreciate guidance, not direct answers.






algorithm search binary-search-tree




algorithm search binary-search-tree






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 24 '18 at 20:47









user2864740

43.7k670148




43.7k670148










asked Nov 24 '18 at 20:41









JohnJohn

515




515








  • 2





    probably related to static optimal binary search tree

    – juvian
    Nov 24 '18 at 21:20











  • Thanks @juvian, optimal BST is exactly what I was searching for.

    – John
    Dec 5 '18 at 20:14














  • 2





    probably related to static optimal binary search tree

    – juvian
    Nov 24 '18 at 21:20











  • Thanks @juvian, optimal BST is exactly what I was searching for.

    – John
    Dec 5 '18 at 20:14








2




2





probably related to static optimal binary search tree

– juvian
Nov 24 '18 at 21:20





probably related to static optimal binary search tree

– juvian
Nov 24 '18 at 21:20













Thanks @juvian, optimal BST is exactly what I was searching for.

– John
Dec 5 '18 at 20:14





Thanks @juvian, optimal BST is exactly what I was searching for.

– John
Dec 5 '18 at 20:14












1 Answer
1






active

oldest

votes


















1














Check out this article:



Data structures and their algorithms



It goes in depth on this exact thought.






share|improve this answer
























  • Thanks for the provided material. It seems optimal BST is what I was searching for.

    – John
    Dec 5 '18 at 20:13











Your Answer






StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53462185%2fbinary-search-tree-order-of-insert-when-we-have-an-estimate-ahead-of-time%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









1














Check out this article:



Data structures and their algorithms



It goes in depth on this exact thought.






share|improve this answer
























  • Thanks for the provided material. It seems optimal BST is what I was searching for.

    – John
    Dec 5 '18 at 20:13
















1














Check out this article:



Data structures and their algorithms



It goes in depth on this exact thought.






share|improve this answer
























  • Thanks for the provided material. It seems optimal BST is what I was searching for.

    – John
    Dec 5 '18 at 20:13














1












1








1







Check out this article:



Data structures and their algorithms



It goes in depth on this exact thought.






share|improve this answer













Check out this article:



Data structures and their algorithms



It goes in depth on this exact thought.







share|improve this answer












share|improve this answer



share|improve this answer










answered Nov 26 '18 at 18:52









Ben TildenBen Tilden

496




496













  • Thanks for the provided material. It seems optimal BST is what I was searching for.

    – John
    Dec 5 '18 at 20:13



















  • Thanks for the provided material. It seems optimal BST is what I was searching for.

    – John
    Dec 5 '18 at 20:13

















Thanks for the provided material. It seems optimal BST is what I was searching for.

– John
Dec 5 '18 at 20:13





Thanks for the provided material. It seems optimal BST is what I was searching for.

– John
Dec 5 '18 at 20:13


















draft saved

draft discarded




















































Thanks for contributing an answer to Stack Overflow!


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53462185%2fbinary-search-tree-order-of-insert-when-we-have-an-estimate-ahead-of-time%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







-

Popular posts from this blog

Lallio

Image
Coordenadas: 45° 40' N 9° 38' E Lallio      Comuna    Lallio Localização de Lallio na Itália Coordenadas 45° 40' N 9° 38' E Região Lombardia Província Bérgamo Área - Total 2 km² Altitude 216 m População  - Total 3 826     • Densidade 1 913 hab./km² Outros dados Comunas limítrofes Bergamo, Dalmine, Stezzano, Treviolo Código ISTAT 016123 Código cadastral E422 Código postal 24040 Prefixo telefônico 035 Website www.comune.lallio.bg.it Lallio é uma comuna italiana da região da Lombardia, província de Bérgamo, com cerca de 3.826 habitantes. Estende-se por uma área de 2 km², tendo uma densidade populacional de 1913 hab/km². Faz fronteira com Bergamo, Dalmine, Stezzano, Treviolo. [ 1 ] [ 2 ] [ 3 ] Demografia | Variação demográfica do município entre 1861 e 2011 [ 3 ] Fonte : Istituto Nazionale di Statistica (ISTAT) - Elabor...
Read more

Futebolista

Image
Ronaldo primeiro jogador a ser eleito por três vezes o melhor jogador do mundo pela FIFA. Ronaldinho Gaúcho atuando pelo Barcelona onde foi duas vezes eleito o melhor jogador do mundo pela FIFA. Kaká atuando pelo Milan onde foi eleito em 2007 o melhor jogador do mundo pela FIFA. Lothar Matthäus primeiro jogador a ser eleito o melhor jogador do mundo pela FIFA em 1991 pela Inter de Milão. Neymar durante partida contra a Escócia, em 27 de março de 2011. Crianças praticando futebol. Robinho, futebolista brasileiro, em 15 de novembro de 2006. Atletas do Chelsea, da Inglaterra. A venda de camisas com nome e número dos jogadores é uma grande fonte de arrecadação. Jürgen Klinsmann atuou como jogador e foi treinador da Alemanha. Estádio de futebol, principal local onde laboram os jogadores. O jogador de futebol , ou Futebolista , é um atleta profissional de futebol, e cuja prática do desporto coletivo é fundamental. Estes trabalhadores sã...
Read more

Jornalista

Image
Uma repórter de televisão segurando um microfone na frente de um cinegrafista. Fotojornalistas no Campeonato Mundial de Atletismo 2013 Uma repórter entrevistando Boris Johnson, Prefeito de Londres. Jornalista é o profissional formado em Jornalismo. É a pessoa responsável pela apuração, investigação e apresentação de notícias, reportagens, entrevistas ou distribuição de notícias ou outra informação de interesse coletivo. O trabalho do jornalista é chamado jornalismo. Um jornalista pode trabalhar com questões gerais ou especializar-se em determinadas áreas. No entanto, a maioria dos jornalistas tendem a se especializar, e cooperando com outros jornalistas, produzir publicações que abrangem muitos tópicos. [ 1 ] Por exemplo, um jornalista esportivo cobre notícias dentro do mundo dos esportes, mas este jornalista pode ser uma parte de um jornal que cobre diversos temas. O exercício do Jornalismo é privativo de jornalista. Entre as áreas em que o jornalista trabalha estão o...
Read more