What is a tree



Trees

What is a tree??

LINK/EDGE

Element/NODE

Other parts of a tree

|Other parts of a tree |

|root |internal nodes |leafs |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

|path |descendants | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

Length of a tree

|Determining the Length of a Tree |

|Height | |Level |

|1 | |0 |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

|2 | |1 |

|3 | |2 |

Relationships of a tree - Part 1

“A” – no parents

“A” - 2 children “K” and “Q”

“K” – Parent is “A” “Q” – Parent is “A”

“K” - 1 child “Z”

“Z” – Parent is “K”

“Z” – no children Z’s ancestors are “K” and “A”

Relationships of a tree - Part 2

None None

K Q

A A

Z None

K Parent

None Left Child

Parent

Right Child

Other Info on Trees

• Trees are SHALLOW – they can hold many nodes with very few levels

• A height of 21 can hold 1048575 nodes

2height -1 = How many TOTAL nodes can he held by this tree

• Tree is inherently recursive structure, because each node in a tree can itself be viewed as the root of a smaller tree.

Types of Trees

• also called classification

• Binary

o has only AT MOST 2 children

o used in Binary Search

o used in Tree Traversals (covered later)

o built (usually) in order

• Regular Binary // ex. Which-Way books

o has only 2 children

o may have a link back up to the parent

o may be built OUT of order

o or data inside each node has a pattern

o each like (left and right) is traveled depending on choice

▪ yes = left link

▪ no = right link

• Regular Tree

o may have MANY links to MANY kids!!!

• B- Trees

o Tailored toward applications where tree doesn’t fit in memory

o operations much faster than disk accesses

o want to limit levels of tree (because each new level requires a disk access)

o keep root and top level in memory

o An Alternative to BSTs

o Up until now we assumed that each node in a BST stored the data.

o What about having the data stored only in the leaves?

o The internal nodes just guide our search to the leaf which contains the data we want.

o We’ll restrict this discussion of such trees to those in which all leaves are at the same level.

| Figure 1 - A BST with data stored in the leaves |

|[pic] |

Red-Black Trees

• A red-black tree is a binary search tree in which:

o Every node is colored either Red or Black.

o Each NULL pointer is considered to be a Black “node”.

o If a node is Red, then both of its children are Black.

o Every path from a node to a NULL contains the same number of Black nodes.

o By convention, the root is Black

• The black-height of a node, X, in a red-black tree is the number of Black nodes on any path to a NULL, not counting X.

[pic]

o A Red-Black Tree with NULLs shown

o Black-Height of the tree (the root) = 3

Black-Height of node “X” = 2

• Splay Trees

o Problems with BSTs

o Because the shape of a BST is determined by the order that data is inserted, we run the risk of trees that are essentially lists

o

is a self-adjusting binary search tree with the special feature that recently accessed elements are quick to access again.

o The basic idea of the splay tree is that every time a node is accessed, it is pushed to the root by a series of tree rotations. This series of tree rotations is knowing as “splaying”.

Representing a Tree

• There are two ways to represent trees

o Linked Lists

▪ use links to connect to the other nodes in the tree

o Array

▪ much like Heap Sort algorithm

|Representing a Tree |

|Linked List | |Array |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| |“Helter Skelter” | |

| | | |

| | | |

| | |[0] |

| | |[1] |

| | |[2] |

| | |[3] |

| | |[4] |

| | |[5] |

| | |[6] |

| | | |

| | |7 |

| | |5 |

| | |1 |

| | |2 |

| | |3 |

| | | |

| | |6 |

| | | |

| | | |

| | | |

| | |// it is possible to have an empty element |

// draw indices OVER middle tree

|DATA |

|parent->link |

|left->link |

|right->link |

Draw the tree from the given info.

|5 |

|9 |

|7 |

|1 |

|6 |

|3 |

|4 |

|8 |

|0 |

| |

|Array-> |

|Tree |Linked List // draw boxes and links |

| | |

| | |

| | |

| | |

| | |

|9 |

|5 |

|6 |

| |

|7 |

| |

|1 |

| |

| |

|2 |

|6 |

| |

| |

|8 |

|4 |

| |

|Tree |Linked List |

| | |

| | |

| | |

| | |

| | |

|Array( |

|Tree |Linked List |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

Binary Tree Traversals

• the process of “visiting” or performing some operations on, each node of a tree is called TREE TRAVERSAL

• a traversal is to process each node ONCE

• There are 3 commonly used to traversals

o preorder

o inorder

o postorder

o they differ in the sequence in which the nodes are visited

• PREORDER/PREFIX

1. process root first

2. if (left child present, and not visited already) move to left, restart with Step 1 at new node

3. if (right child present, and not visited already) move to right, restart with Step 1 at new node

4. Else, go back up to parent, and start at step 3

▪ overall, the algorithm reaches the root first

• INORDER/INFIX

1. if (left child present, and not visited already) move to left, restart with Step 1 at new node

2. process root

3. if (right child present, and not visited already) move to right, restart with Step 1 at new node

4. Else go back up to parent, and start at step 2

• POSTORDER/POSTFIX

1. if (left child present, and not visited already) move to left, restart with Step 1 at new node

2. if (right child present, and not visited already) move to right, restart with Step 1 at new node

3. Else process root, go back to parent, and start at step 2

▪ overall, the algorithm reaches the root LAST

Practicing Tree Traversals

• Guarantees that we will visit EACH node at least once

o No man left behind!!!

• Always start at the root

| |Inorder |// I will do, you do next 5 |

| | | |

| |(L, P, R) | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| |Preorder | |

| | | |

| |(P, L, R) | |

| |Postorder | |

| | | |

| |(L, R, P) | |

| |Inorder | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| | | |

| |Preorder | |

| |Postorder | |

Hints on Building Trees

• UNLIKE LINKED LISTS, YOU MUST HAVE A GAME PLAN!!

• The FIRST node is always the simplest since there are no other nodes

• The rest of the nodes placed, must be traveled to the precise location needed, then placed

• Just like Linked Lists, remember to assign your links

o most will be set to NULL (left and right)

o link from Parent to new node

o link from new node to Parent

The Game plans

• “Helter Skelter”

o Place them ANYWHERE you want

• BST

o Order by some type of logic

▪ A < Z

▪ 0 < 100

o Also considers the ORDER items was received (and placed) in tree

• Full

o Fill each LEVEL one at a time

Creating a Binary Search Tree

• in a Binary Search Tree

o items to the left are smaller in value

o items to the right are larger in value

|Simple Binary Tree |Complex Binary Tree |

| |[pic] |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

Adding a Node to a Binary tree

• remember game plan!!

|Drawing what adding should do |

|First Node (M) |Adding another (T) |Adding another (Z) |

| | | |

| | | |

| | | |

|Adding another (B) |Adding another (F) |Adding another (A) |

| | | |

| | | |

| | | |

| | | |

| | | |

|Placing a Node |

|// place the nodes in a binary search tree in the order given | |

| | |

|8,1,0,9,6,5,3,7,4 | |

| | |

| | |

| | |

|5,9,1,8,0,6,7,3,4 | |

| | |

| | |

| | |

|8,0,1,6,9,3,4,7,5 | |

| |// what TRAVERSAL algorithm will display ALL of these trees in numerical order?? |

BST- Binary Search Trees

• use divide and conquer methods for searching, deleting, inserting, etc…

• what makes a binary tree

o nodes have no more than 2 children

o all nodes have data placed inside

o for any node, the element in the node is larger than all elements in the node’s right subtree, and smaller than all elements in this node’s left subtree

o smallest and largest elements in a tree are easy to find

▪ for the smallest, keep going right, until no longer possible, or until left is the only option

▪ for the largest, keep going left, until no longer possible, or until right is the only option

o 2 types of Binary Trees

▪ Full Binary Tree – EVERY leaf has the same depth, and every non-leaf has 2 children

▪ Complete Binary Tree – Take a FULL binary tree, and start adding new leaves at a new depth from left to right. All of the new leaves are at the same depth

• we will use linked lists for all functions instead of arrays

o easy to create

o easy to locate a target

o easy to add/insert, or deletes a node

• step by step psuedocode to find data in a BST

1. determine what the target is

2. start at the top of the tree, the “root”

3. compare target to the root

a. if target == root, target has been found

b. if target < root, left child becomes the root (repeat step 3)

c. if target > root, right child becomes the root (repeat step 3)

• number of times we check the root will always be less that the height of the tree

|Simple Binary Tree Search Example |

|target is red |target is red |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

|target is red |NEW target is red |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

A look at the BinarySearchTree code

• Yes, we are STILL in trees, but using Binary theory to add and find nodes in a tree (game plan)

• Notice looks A LOT like Linked Lists

o why we cover it FIRST!!!

Draw what the EMPLOYEE NODE looks like?

What are the names of the links for EMPLOYEE?

In BinarySearchTree, what are the names of some BASIC nodes?

In BinarySearchTree, find the “Add” function, what links does it use?

• Look at FIRST “insert” function

o notice it looks at name in order to PLACE or MOVE either to left or right

o notice in a loop since we may have to travel for a while to get to our correct spot to add

Traveling through a Binary tree

• let use the infix algorithm

|Drawing what traveling should do |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

|Coding |

|Psuedocode |Code |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

Other items needed

• a class for the node we are creating

• the Linked/Binary Tree class should be GENERIC

• we will need a comparator

|Completing our first Tree implementation |

|Code for the node |

|use Employee from previous material |

|Binary Tree class |

|public class BinarySearchTree |

|{ |

|// what items should go here?? |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

|} |

|Comparator |

| |

| |

| |

| |

| |

| |

| |

| |

Other functions that would be worth while

• Search function

o find a person within that tree

o use the binary search method

▪ (after target determined)

▪ define middle

▪ is middle == target

▪ go left or right

• Remove function

o much like the reheapify function

o find our target

▪ use the search algorithm above

o restructure the tree

▪ THIS CAN BE COMPLICATED!!

-----------------------

6

8

0

2

1

9

5

6

7

2

3

6

7

5

1

2

3

6

5

1

7

Z

K

Q

A

Z

K

Q

A

A

K

Q

F

Z

A

K

Q

F

Z

A

K

Q

F

Z

A

K

Q

F

Z

A

K

Q

F

Z

A

K

Q

F

Z

Z

F

K

Q

A

A

Q

K

M

N

S

Z

P

E

E

P

Z

S

N

M

K

Q

A

E

P

Z

S

N

M

K

Q

A

E

P

Z

S

N

M

K

Q

A

E

P

Z

S

N

M

K

Q

A

E

P

Z

S

N

M

K

Q

A

2

3

6

5

1

7

4

8

0

2

1

9

5

6

7

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download