Binary Search Trees

Binary Search Trees

A Binary search tree is a particular binary tree such that the its elements are stored according to a less than or greater than algorithm. The item we want to insert into the tree will either go to the left of the root or to the right of the root depending on its value. is. For example, if the root of the tree is 5 and the item we wanted to insert into the tree is 10, then 10 would be inserted into the right of the tree, since 10 is greater than 5. If the item we wanted to insert is 2, then it would be inserted into the left of the tree for the same reason. (The difference being that 2 is less than 5.) Deleting a node from the binary search tree requires that, if the node has two children, then the child on the left subtree of that node will replace the node; if the node has only one child, then that child would replace that node; if the node has no children, however, then it is as simple as removing it from the tree. Much like linked lists, binary search trees were concepts I studied in high school, so most of this was review to me. However, I did gain a better understanding of the concept through the lectures.