Construct Optimal Binary Search Tree by Using Greedy Algorithm
Chun Shi, Ming Zhao, Chunyu Li, Chunlei Lin, Zhengjie Deng
Available Online May 2016.
- https://doi.org/10.2991/icemc-16.2016.205How to use a DOI?
- Binary Search Tree; Greedy algorithm; Huffman tree; Efficiency; Complexity;
- 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.
- Open Access
- This is an open access article distributed under the CC BY-NC license.
Cite this article
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 - https://doi.org/10.2991/icemc-16.2016.205 ID - Shi2016/05 ER -