-
Notifications
You must be signed in to change notification settings - Fork 4
BST Lab
Anthony Christe edited this page Oct 30, 2013
·
2 revisions
- Sudoku GUI posted
- Tree - A data structure which acts as a fully connected graph without loops
- Node - May contain data, has references to children nodes
- Each node may only have a single parent, but may have 0 or more children
- Edges - Link nodes together
- Root node - Node without any parent (the start of a tree)
- Leaf node - Node without children
- Inner (or interior) node - node that is not a root node or a leaf node
- Parent node - A node that references the current node
- Child node - A node that is referenced from current node
- Descendant node - Any node (including children) which descend from current node (i.e. children, grand children, etc)
- Sibling - Nodes are siblings if they have the same parent node
- Ancestor node - Nodes that come before the current node (parent, grandparent, etc)
- Height - the maximum distance of any node from the root (if a tree only has one node (the root), the height is 0
- Depth - Distance from a given node to the root of a tree
- Level - All the nodes of a tree with the same depth
- Every node may only have a maximum of two children nodes (hence the term binary)
- Full tree - Every node has either 0 or 2 children (or put another way, all nodes have 2 children except for leaf nodes)
- Perfect binary tree - Binary tree in which all leaves are at the same level
- Complete binary tree, similar to full tree, but any leaf nodes must be as left as possible in the tree
- A binary tree which keeps elements in sorted order
- Invariant: For every node, smaller values are in left subtree, larger are in right subtree (equal values are undefined and up to the implementation)
- Every insertion creates a new leaf node
- Every subtree within a BST is also a valid BST, thus a BST is a recursive structure
- Start at root and recursively compare value we're searching for against current node
- If value is less than current node, recurse on left subtree
- If value is greater than current node, recurse on right subtree
- If recursion takes you to a leaf node, and the leaf node does not contain your value, then value is not in tree
- If tree is empty, value becomes root
- Compare value to current node starting at the root.
- If value is less than current node, recursively compare on left subbtree, otherwise if the value is greater than the current node, recursively compare on right subtree
- When recursive method attempts to recurse on left or right subtree, but that subtree is null, then new node is inserted at the position with the value
- Removing an item depends on three different cases
- Simply remove the node
- Remove node and replace with child node
- Remove node and replace with either in-order predecessor or in-order successor
- In-order predecessor is the left subtree's rightmost node
- In-order successor is the right subtree's leftmost node
- Download the two classes at https://github.com/anthonyjchriste/ics211f13/tree/master/src/bst
- Complete the three private methods (marked with a TODO comment) at the bottom of BinarySearchTree.java