Binary Search Trees Flashcards
Binary Search Tree (BST)
A BST is an arrangement of node labels used to search for items of a type T for which a total preorder on T has been defined.
Total Preorder of T
A binary relation on T that is total, reflexive, and transitive
Binary Relation of T
A potential relationship between two items of a mathematical type T that may or may not hold. This relationship can be defined by a boolean function R.
Total binary relation of T
The binary relation R is total whenever: for all x, y: T, (R(x, y) or R(y, x)) (In simple words: A binary relation is said to be “total” if for ALL values x and y, “x is related to y” OR “y is related to x”)
(E.g. - say you go to a family gathering where there are no “friends”, hence everyone at the gathering is physically related to each other. In this case, you could pick any 2 people, and the relationship “is relative of” would be TRUE - you are a relative of your sister, your sister is a relative of your cousin, and so on. This is an example of a total binary relation on that particular data type T for the people in the family gathering)
Reflexive binary relation of T
The binary relation R is reflexive whenever: for all x: T, (R(x, x))
(In simple words: A binary relation is reflexive if for ALL elements x of a mathematical type T, “x is related to ITSELF”)
(E.g. - Are you a relative of yourself? You as an individual are familially related to yourself, so the statement can be held TRUE).
Transitive binary relation of T
The binary relation R is transitive whenever: for all x, y, z: T, (if R(x, y) and R(y, z) then R(x, z))
(In simple terms: A binary relation is transitive if for all elements x, y, and z of a mathematical type T, if x is related to y AND y is related to z, THEN x is related to z)
(E.g. - If you are a relative of your sister, and your sister is a relative of your cousin, then you are a relative of your cousin)
Why/how is binary search faster than linear search?
In binary search, the user needs to compare the item to be searched to the root of the tree, and iff the root is not equal to the item, search “either” the left or the right subtree, but not both. This whole process takes much lesser time than linear search, where the user might have to look at all the items, which would be equivalent to searching BOTH subtrees.
How to apply recursion when searching through a binary tree?
Disassemble the original binary tree, search in one of the subtrees, and then re-assemble the original tree before returning the answer.
Difference between preorder traversal and total preorder?
Preorder traversal refers to a traversal order where the root of a binary tree is visited before the left and right subtrees, whereas total preorder refers to a binary relation on the type of the binary tree, say, T, that is referred to when performing a binary search on the tree.
What simplifications are being used in this class for BSTs? (Note: these simplifications do not hold up for all BSTs)
The mathematical type of the BST is integer (T = integer), the total preorder of node labels is “less than or equal to” (<=), no 2 nodes in a BST have the SAME label.
Is strictly less than (<) a total preorder?
No! It does not satisfy reflexivity (x < x is FALSE).
