Discussions
Categories
Programmers Heaven
Home
›
C and C++
Optimal Binary Tree
fawadalam
October 2002
in
C and C++
Can someone explain me the Optimal Binary Tree algorithm or can someone give me the code for an optimal binary Tree.
Comments
Josh Code
October 2002
: Can someone explain me the Optimal Binary Tree algorithm or can someone give me the code for an optimal binary Tree.
:
The binary tree is used to search a sorted list for an item.
The list must already be sorted, for it to work.
[b]I'll explain what basically happens:[/b]
You start with a sorted list and a value that you want to find in that list.
There are variables to store the upper and lower boundaries of the search.
Initially the boundries start at the first index and end at the last index of the list.
Each pass of a loop, the boudries become half of their previous difference.
The average of the upper and lower boundary is averaged to get an item to compare with the search value.
If the search value is equal to the item, the search is complete becuase you've found what you were looking for.
If the search value is greater, the item must be above this item so lowerbound is set to the average, upperbound remains the same.
If the search value is less than the item, upperbound is set to the average, lower bound stays the same.
if upperbound = lowerbound, the loop is to exit because the item can't be found in the list.
After these conditions are complete is the end of the loop.
Here is a site with some code for you:
http://www.csm.astate.edu/~rossa/datastruc/optimal.html
Sign In
or
Register
to comment.
Howdy, Stranger!
It looks like you're new here. If you want to get involved, click one of these buttons!
Sign In
Register
Categories
Recent Discussions
Categories
140.8K
All Categories
103.6K
Programming Languages
6.4K
Assembler Developer
401
Assembly Code Share
239
Getting started in assembly
4.6K
x86 Assembly
1.9K
Basic
97
Qbasic
39.9K
C and C++
5.6K
Beginner C/C++
330
C/C++ on Linux/Unix
450
C/C++ Windows API
522
C++ Builder
253
C++ Game Development
3.3K
C++ MFC
103
C++.NET
210
Embedded C/C++
404
Visual C++
2.9K
C#
7.9K
Delphi and Kylix
334
Advanced Delphi
360
Delphi beginners
4
Haskell
9.7K
Java
56
Enterprise JavaBeans
1.3K
Java Beginners
304
Java Server Pages
4.1K
Pascal
1.3K
Perl
11
Perl 6
2K
PHP
546
Python
37
Ruby
4.4K
VB.NET
258
Advanced VB.Net
1.6K
VBA
20.9K
Visual Basic
767
Access databases and VB
831
Advance Visual Basic
1.2K
Beginner VB
2.6K
Game programming
315
Console programming
90
DirectX Game dev
1
Minecraft
112
Newbie Game Programmers
2
Oculus Rift
9K
Applications
1.8K
Computer Graphics
279
3D Graphics
129
DirectX
125
OpenGL
740
Computer Hardware
9
Cooling & Overclocking
3.4K
Database & SQL
1.1K
Access
91
ADO Programming
288
MySQL
358
Oracle
440
SQL-Server
535
Electronics development
1.6K
Matlab
628
Sound & Music
25
DirectSound
257
XML Development
3.3K
Classifieds
200
Co-operative Projects
198
For sale
190
FreeLance Software City
1.9K
Jobs Available
603
Jobs Wanted
209
Wanted
2.9K
Microsoft .NET
1.8K
ASP.NET
1.1K
.NET General
22
.NET WEB-Services
129
.NET WinForms
14
.NET XML
50
ADO.NET
144
C# & VB.NET School Support
3.4K
Miscellaneous
4
Join the Team
354
Comments on this site
69
Computer Emulators
2.1K
General programming
187
New programming languages
621
Off topic board
200
Mobile & Wireless
72
Android
126
Palm Pilot
338
Multimedia
154
Demo programming
184
MP3 programming
6.9K
Operating Systems & Platforms
0
Bash scripts
27
Cloud Computing
1
Witsbits Go Cloud
365
Embedded / RTOS
53
FreeBSD
1.7K
LINUX programming
1
Awk scripting
332
Linux Support
0
Sed scripting
370
MS-DOS
0
Shell scripting
321
Windows CE & Pocket PC
4.1K
Windows programming
177
COM/DCOM
61
Networking And Security
17
Windows 2003 Server
6
Windows Vista
176
Windows XP
941
Software Development
417
Algorithms
68
Object Orientation
24
RUP & UML
92
Project Management
95
Quality & Testing
268
Security
63
Evil Scripting
81
Hacking
7.7K
WEB-Development
1.8K
Active Server Pages
61
AJAX
4
Bootstrap Themes
55
CGI Development
28
ColdFusion
224
Flash development
1.4K
HTML & WEB-Design
1.4K
Internet Development
131
Mobile Internet & Messaging
211
Wireless development
2.2K
JavaScript
37
JQuery
304
WEB Servers
153
Apache
79
IIS
150
WEB-Services / SOAP
In this Discussion
October 2002
Josh Code
Discussions
Categories
Sign In
Comments
:
The binary tree is used to search a sorted list for an item.
The list must already be sorted, for it to work.
[b]I'll explain what basically happens:[/b]
You start with a sorted list and a value that you want to find in that list.
There are variables to store the upper and lower boundaries of the search.
Initially the boundries start at the first index and end at the last index of the list.
Each pass of a loop, the boudries become half of their previous difference.
The average of the upper and lower boundary is averaged to get an item to compare with the search value.
If the search value is equal to the item, the search is complete becuase you've found what you were looking for.
If the search value is greater, the item must be above this item so lowerbound is set to the average, upperbound remains the same.
If the search value is less than the item, upperbound is set to the average, lower bound stays the same.
if upperbound = lowerbound, the loop is to exit because the item can't be found in the list.
After these conditions are complete is the end of the loop.
Here is a site with some code for you:
http://www.csm.astate.edu/~rossa/datastruc/optimal.html