Binary Trees Flashcards
Binary tree are both
1) Recursive
2) Ordered
Depth three items
1) inoreder
2) perorder
3) Postorder
Killer feature
Searching
Killer feature
Searching - 1/2 ‘s the search each pass
Binary Tree - How is data stored
Nodes (like leafs on a tree)
Binary Tree - How is data stored
Nodes (like leafs on a tree) with keys
Binary tree - Describe a full binary tree
Tree with zero or two children (no single children)
Binary tree - Describe a balanced binary tree
It has the minimum possible height
Binary tree - Breadth first
Search across the tree first (think the data is somewhere near the top)
What type of algorithms use Breadth first
shortest pass
Binary tree - depth First
Think the data is deep deep down the tree
example: maze problems
Binary Search Tree (BST) - how are nodes(keys) sorted
Nodes keys are sorted top to Bottom
all the nodes left of the parent are smaller then the parent, And all the nodes right to the parent are larger
5
/ \
3 7
/ \ / \
2 4 6 8
Also every level search eliminates half of the data
Binary Search Tree (BST) search find 4 (how many hops)
5
/ \
3 7
/ \ / \
2 4 6 8
5 4<> ?
/ \
4<> ? 3 7
/ \ / \
2 4 6 8
three hops
Binary insert - How to insert a (2)
5
/
3
1) start at 5 (it is less than 5 so it goes on the left
2) Is it great then or less then 3 (it is less then so we go down)
3) so Insert it to the empty node below 3
5
/
3
/
2
Binary insert - How to insert a (4)
5
/
3
5
/
3
/ \
2 4
Four is greater then three so go to right node
Binary insert - How to insert a (7)
5
/
3
/ \
2 4
7 is greater then 5 so branch to right
5
/ \
3 7
/ \
2 4
How to find the minimum in a binary Search Tree
easy (just go down the left side to get the minimum key value (smallest numbers are always on the left side)
5
/ \
3 7
/ \ / \
2 4 6 8
/
nulldelete from a binary Search Tree (what are the cases)
1) No Child
2) One Child
3) Two children
delete from a binary Search Tree - No Child
Just find it and set it to null
delete from a binary Search Tree - One Child
Replace the node that being deleted with the child
delete from a binary Search Tree - Two children
Most complex - convert tree to one that our node only has one child
1) find minimum on the correct side that will fit into the position
2) replace that node with the new node
3) delete the original new node
delete from a binary Search Tree - Two children (delete 5)
5
/ \
2 3
1) Go down the right side
2) find minimum value
3) Copy it to the position of the 5
4) remove duplicate
Depth first traversal - Inorder
Left first, Root, Right)
Start on Left, goto Root, Right
2,1,3
1
/ \
2 3
order = root midle
Why use Depth first traversal - Inorder
Good if inherent order in tree
example: print out all the elements in the tree
Depth first traversal - Preorder
Start at top Left and then Right
1,2,3
1
/ \
2 3
Pre = root first
Why use Depth first traversal - Preorder
Good for Copying and Expression trees
Depth first traversal - Postorder
Root goes last (bottom up,used in Delete )
Left,Right, Root
2,3,1
1
/ \
2 3
Post = root last
Run-time Binary Search Tree B-O number
find, insert, delete
O(log n)
Every time the binary tree recuses it halves the search group
1/2 1/4 1/8 1/16 …
