CP114 Lecture Notes - Lecture 11: Init, Binary Tree, The Algorithm
Document Summary
You have a root at the beginning which is always the first element you add. It"s prett(cid:455) si(cid:373)ple actuall(cid:455: if value < node, then value goes to the left, else to the right, if a spot is available that value becomes a node in that part of the tree. O think of it like this (below): get the root node. If there is no node, the search fails. Search the tree: compare the node value to the key: If the key and node value match, the search ends successfully. If the key < the node value, search the left subtree of the node. If the key > the node value, search the right subtree of the node. Remember that we can treat each node as the root of its own tree. The following diagram shows the route through the tree taken to search for the value 8:
