Who doesn’t like binary search trees, or BSTs? They are my favorite data structures. According to Wikipedia, a binary search tree is “a binary tree data structure which has the following properties:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- The left and right subtree each must also be a binary search tree.
- There must be no duplicate nodes” (1).
The reason that I like binary search trees is that you can search a binary search tree for a specific key with a recursive algorithm. There are many examples of operations that are used for binary search trees, but here is one from Wikipedia that shows the search operation (1):
function Find(key, root):
current-node := root
while current-node is not Null do
if current-node.key = key then
return current-node
else if key < current-node.key then
current-node := current-node.left
else
current-node := current-node.right
Of course, there are other algorithms that are based in the BSTs, such as insertion, deletion, traversal, and sort.
These algorithms are used to form an abstract of sets, multisets, and associative arrays in the binary search tree.
There is no need to tell that we computer science/computer engineering/software engineering majors in San Jose State University understand the knowledge of binary search trees in various programming languages, especially Java.
To wrap it up, my main reason for liking binary search trees is that I understand the algorithms very well and enjoy the practices of depth-first traversal: in-order, preorder, and postorder.
Works Cited
19 October 2013. Web. 1 November 2013. <http://en.wikipedia.org/wiki/Binary_search_tree>
Hi, Mari,
ReplyDeleteIt is nice to meet you here. Your post lets me review BSTs again.
BSTs are amazing roles in data structures family. Most of software engineers that I know like them. They use recursive algorithm to implement their operations like insertion, deletion and traversal. By the way, recursive algorithm is also my favor which always use less codes to finish complicated function. I heard from my friends it is very possible that the questions about BSTs will be asked in future job interviews.
It is a good post. You simply show the readers the definition of BSTs and their operations And your example makes your argument clear. I like it.
Mari,
ReplyDeleteExcellent post!
1) #iLoveBinarySearchTrees
2) #iLoveYourBlog
Jokes aside, i love the overall transition and theme of your blog. The blog flows very well and effectively shows your take on BST's and Data Structures in general. Your Subpoints and keys make it easier for amateurs to at least get an overview of BST's.
Overall, the blog is very informative, and technical.
Good Job!
- Tushar
Hey Mari,
ReplyDeleteGreat post on what BSTs are and why it's just an awesome data structure. Using the example code to describe the core structure was an interesting way approach and goes well with the additional concise bits of information on the functionality required of BSTs.
Hi Mari!
ReplyDeleteYours is the only blog I've seen that's supplemented a post with code (or pseudocode). I've always thought it was best to see an algorithm in pseudocode, since otherwise you can kinda' get that feeling of "...but how do I actually /write/ that...?" Yours (along with the picture) made everything very clear.
Even better than a binary tree is a balanced tree (which, if I remember right, come in about a million flavors). Since the path stays at its minimum possible value ( lg(n) ), search time is minimized.