Construct Optimal Binary Search Tree by Using Greedy Algorithm

DOI

10.2991/icemc-16.2016.205How to use a DOI?

Keywords

Binary Search Tree; Greedy algorithm; Huffman tree; Efficiency; Complexity;

Abstract

Focus on some constructions of binary tree, there are many methods to resolve this problem. With analyzes between binary search tree and Huffman tree, we introduce information retrieval issue and compare the Huffman tree with optimal binary search tree. And we further present a method that use greedy algorithm to construct binary search tree and use C++ to realize method. Experimental provides some conclusions that greedy algorithm is more efficiency than dynamic programming algorithm.

Copyright

© 2016, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Chun Shi
AU  - Ming Zhao
AU  - Chunyu Li
AU  - Chunlei Lin
AU  - Zhengjie Deng
PY  - 2016/05
DA  - 2016/05
TI  - Construct Optimal Binary Search Tree by Using Greedy Algorithm
BT  - Proceedings of the 2016 International Conference on Education, Management and Computer Science
PB  - Atlantis Press
SP  - 1045
EP  - 1049
SN  - 1951-6851
UR  - https://doi.org/10.2991/icemc-16.2016.205
DO  - 10.2991/icemc-16.2016.205
ID  - Shi2016/05
ER  -