-
a binary tree is built out of ______
each _____ has one _____ and two ____ which are :
nodes, node, value, links, left child and right child.
-
The tree itself has a reference to
the root node.
-
order property of a binary tree:
for every node: all left
and all right
all left descendants have a smaller value,and
all right descendants have a larger value.
-
binary tree:
to search for a value you start at the
If the current node's value is correct:
Otherwise:
Base case:
It is similar to:
root
return true.
recursively search the left or right subtree (just one!)
if the tree is empty(null), return false.
binary search.
-
what is a leaf:
a tree node that has no children.
-
BST Opeartions
how is insertion:
When we reach a null reference, replace it with the new node.
-
What is a balanced bst?
if each node has about as many left descendants as right.
-
BST operation
how is deletion
do a search to find the node. Then three cases:
No children: replace parent's link with null
One child: replace parent's link with the child.
Two children: Find the previous node (rightmost descendant of left child) or the next node (leftmost descendant of right child). Swap its value with this node's, then recursively remove that previous or next node.
-
For a BST operations: the complexity depends on:
balanced tree:
unbalanced tree:
building a balanced bst:
building an unbalanced bst
O(h) where his the height.
In a balanced tree, O(h) is O(logn).
In an unbalanced tree, it could be as bad as O(n).
Building a balanced BST is O(nlogn).
Building an unbalanced BST could be as bad as O(n2).
-
BST, create an add method in recursive:
private BSTNode<T> recAdd(E element, BSTNode<T> tree)
- private BSTNode<T> recAdd(T element, BSTNode<T> tree)
- // Adds element to tree; tree retains its BST property.
- {
- if (tree == null)
- // Addition place found
- tree = new BSTNode<T>(element);
- else if (element.compareTo(tree.getInfo()) <= 0)
- // Add in the left subtree
- tree.setLeft(recAdd(element, tree.getLeft()));
- else
- // Add in the right subtree
- tree.setRight(recAdd(element, tree.getRight()));
- return tree;
- }
- public void add (T element)
- // Adds element to this BST. The tree retains its BST property.
- {
- root = recAdd(element, root);
- }
-
for a bst, create the size mehtod
print int recSize(BSTNode<T> tree)
- private intrecSize(BSTNode<T> tree)
- // Returns the number of elements in tree.
- {
- if (tree == null)
- return 0;
- else
- return recSize(tree.getLeft()) + recSize(tree.getRight()) + 1;
- }
-
for size methosd is it better recursion or iteration.
Is the depth of recursion relatively shallow?
Is the recursive solution shorter or clearer than the nonrecursiveversion?
Is the recursive version much less efficient than the nonrecursiveversion?
Yes
Yes
No
This is a good use of recursion.
-
what are two important points about recursion with trees.
Always check for the empty tree first.
Leaf nodes do not need to be treated as separate cases.
-
How are the BST traversals
Pre-order traversal
In-order traversal
post-order traversal
Pre-order traversal: root -> left subtree -> right subtree
In-order traversal: left subtree -> root -> right subtree
Post-order traversal: left subtree -> right subtree -> root
-
BST create the contains method
private boolean recContains(T element, BSTNode<T> tree)
- private booleanrecContains(T element, BSTNode<T> tree)
- // Returns true if tree contains an element e such that
- // e.equals(element), otherwise returns false.
- {
- if (tree == null)
- return false; // element is not found
- else if (element.compareTo(tree.getInfo()) < 0)
- // Search in the left subtree
- return recContains(element, tree.getLeft());
- else if (element.compareTo(tree.getInfo()) > 0)
- // Search in the right subtree
- return recContains(element, tree.getRight());
- else
- return true; // element is found
- }
- public boolean contains (T element)
- // Returns true if this BST contains an element e such that
- // e.equals(element), otherwise returns false.
- {
- return recContains(element, root);
- }
-
why is the remove method the most complicated of the binary search tree operations:
We must ensure that when we remove an element, the binary search tree property is maintained.
-
BST create the remove method:
private BSTNode<T> recRemove(T element, BSTNode<T> tree)
- private BSTNode<T> recRemove(T element, BSTNode<T> tree)
- // Removes an element e from tree such that e.equals(element)
- // and returns true; if no such element exists returns false.
- {
- if (tree == null)
- found = false;
- else if (element.compareTo(tree.getInfo()) < 0)
- tree.setLeft(recRemove(element, tree.getLeft()));
- else if (element.compareTo(tree.getInfo()) > 0)
- tree.setRight(recRemove(element, tree.getRight()));
- else
- {
- tree = removeNode(tree);
- found = true;
- }
-
what are the three cases for the removeNode operation:
Removing a leaf (no children): removing a leaf is simply a matter of setting the appropriate link of its parent to null
Removing a node with only one child: make the reference from the parent skip over the removed node and point instead to the child of the node we intend to remove.
Removing a node with two children: replaces the node's info with the info from another node in the tree so that the search property is retained -then remove this other node.
-
what happens if the binary search tree is not balanced.
if we perform a worst-case analysis assuming a completely skewed tree, the efficiency benefits of the binary search tree disappear.
The time required to perform the contains, get, add, and removeoperations is now O(N), just as it is for the linked list
-
How to balance a binary search tree?
Save the tree information in an array;
Insert the information from the array back into the tree.
First insert the "middle" item of the inOrderarray;
Then insert the left half of the array using the same approach;
Then insert the right halfof the array using the same approach.
-
A full binary tree is a
A complete binary tree is a
binary tree in which all of the leaves are on the same level and every nonleaf node has two children.
binary tree that is either full or full through the next-to-last level, with the leaves on the last level as far to the left as possible.
|
|
