Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Binary Tree

No description
by

Irene Yoon

on 28 May 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Binary Tree

Binary Search Tree
Root pointer - points to top node (root)
Each node contains:
Left/right pointers - point to subtrees
Data value of Comparable type
Leaf - node with both pointers set to null
Siblings - nodes that come from the same parent node
Depth
Node - number of edges from node to root
Height
Node - number of edges from deepest leaf
Tree - max distance from deepest leaf to root leaf
Level
Node - height
Tree - height of deepest leaf
Parts
Types
Binary Tree Implementation
BinarySearchTree class
private Node root
add(Comparable obj)
find(Comparable obj)
remove(Comparable obj)
print()
Node class
public Comparable data
public Node left, right
addNode(Node newNode)
printNodes()
Left tree values < parent node value
Right tree values > parent node value
add(Comparable obj)
Run time of binary search algorithms
Binary Expression Trees
Shows order the operations must be done
Traversal
Three kinds
1011010101
Filled up from left to right
Every node has either two or no pointers
A
B
Which one is the binary search tree?
If you find a non-null node reference
if the value > your value, look to left child
else look to right child
Else replace it with your value
Where would "L" go?
remove(Comparable obj)
One Child
Find the node you want to remove
Make the parent node reference point to the child node
Two Children
Replace the node you want to remove with the node with the next largest value
Look through left nodes until you find the largest one
Delete that node and place its value into the node you want to remove
Inorder
Preorder
Postorder
Parent -> left -> right
Left -> parent -> right
Left -> right -> parent
Balanced Tree
Perfect Tree
Complete Tree
Each node has same number of left and right descendants
If root is not 'null':

Traverse left subtree inorder

Visit root

Traverse right subtree inorder
Using inorder traversal, what is the result of this expression?
find(Comparable obj)
Applications
while node reference is not null
Compare data to obj
if data = obj, return true
if data < obj, compare data of left node
if data < obj, compare data of right node
Work Cited
Barron's AP Computer Science Levels A and AB. 4th ed. Hauppauge: Barron's, 2007. Print.

Horstmann, Cay S., and Cay S. Horstmann. Java Concepts for AP Computer Science. Hoboken, NJ: J. Wiley & Sons, 2008. Print.

http://www.cs.bu.edu/teaching/c/tree/binary/

http://www.geeksforgeeks.org/applications-of-tree-data-structure/

http://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html


What is a binary tree?
Binary Trees are data structures that are hierarchical data structures.
Binary Search Trees
Search application with constantly leaving/entering data (map & set objects in language libraries)

Binary Space Partition
Used in 3D games to determine what objects need to be rendered

Binary Trees
High-width router for storing router tables
Hash Trees
P2P programs and specialized image


Heaps
- heap sort
- implementing Dijkstra's algorithm
- efficient priority queues
- routers
- A*(path finding algorithm for AI app)

Huffman Coding Tree (Chip Uni)
compression algorithms (.jpeg and .mp3)
GGM Trees
Creates trees of pseudo-random numbers in cryptographic applications
Syntax Trees
Used in compilers and calculators for parse expressions
Treap
Randomized data structure used in wireless and network communication
Tree Node Implementation
Implementation of classes

private Object value

private TreeNode left, right


public TreeNode(Object initValue)

public TreeNode(Object initValue, TreeNode initLeft, TreeNode initRight)


Private Instance Variables
Methods
If root is not 'null':

Visit root

Traverse left subtree preorder

Traverse right subtree preorder
If root is not 'null':

Traverse left subtree postorder

Traverse right subtree postorder

Visit root

Recursive Tree Algorithms
infix : A+B

Prefix : +ab

postfix : AB+
4 * 3 + 2 / 1 - 2 + 6 = 18
Full transcript