Length

The number of arcs traversed.

Height

The maximum path length from that node to a left node.

Has Height 0

Leaf Node

Nodes with no children

Leaf Nodes

Nodes with Children

Interior Nodes

Each node has at most two children. Children are either left or right.

Binary Tree

We will store our binary trees in instances of struct Node.

Each node will have a value, and a left and right child, as opposed to the next and prev pointers of the DLink. struct Node { TYPE value; struct Node * left; struct Node * right; }

4 Traversals

Used to examine every node in a tree in sequence.

Preorder Traversal

Examine a node first, then left children, then right children

Inorder Traversal

Examine left children, then a node, then right children

Postorder Traversal

Examine left children, then right children, then a node

Levelorder

Examine all nodes of depth n first, then nodes depth n+1, etc

Most useful Traversal in practice

Inorder

Euler tour

Traversal of a tree… Like a walk around the perimeter of a binary tree.

Fast addition of new elements, search time, and removal.

Skip List

Skip Lists

Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

Skip Lists

Skip lists are linked lists that allow you to skip to the correct node. The performance bottleneck inherent in a sequential scan is avoided, while insertion and deletion remain relatively efficient. Average search time is O (lg n ). Worst-case search time is O ( n ), but is extremely unlikely.

Disadvantage of Skip List

The one disadvantage of the skip list is that it uses about twice as much memory as needed by the bottommost linked list.

Binary Search Tree

A binary search tree is a binary tree that has the following additional property: for each node, the values in all descendants to the left of the node are less than or equal to the value of the node, and the values in all descendants to the right are greater than or equal.

Height-balanced binary tree

–Depth of all leaf nodes differ by at most 1 –With height h, contains between 2 h -1 and 2 h nodes

Full BInary Tree

A binary tree in which all of the leaves have the same height and every internal node has two childeren

Complete Binary Tree

a full tree up to the second last level with the last level of leaves being filled in from left to right (if last level is completely filled, the tree is full) height h –> between 2^(h-1) and 2^h - 1 nodes

Binary Search Tree (BST)

* For each node in tree * All data in left subtree is less * All data in right subtree is greater Does not allow for duplicates * If necessary add “or equal to” to ONE of above lines Shape doesn’t matter - can be anywhere from full to linear

balanced tree

a tree in which the height of the subtrees are about equal

g

Length

The number of arcs traversed.

g

Height

The maximum path length from that node to a left node.

g

Has Height 0

Leaf Node

g

Nodes with no children

Leaf Nodes

g

Nodes with Children

Interior Nodes

g

Each node has at most two children. Children are either left or right.

Binary Tree

g

We will store our binary trees in instances of struct Node.

Each node will have a value, and a left and right child, as opposed to the next and prev pointers of the DLink. struct Node { TYPE value; struct Node * left; struct Node * right; }

g

4 Traversals

Used to examine every node in a tree in sequence.

g

Preorder Traversal

Examine a node first, then left children, then right children

g

Inorder Traversal

Examine left children, then a node, then right children

g

Postorder Traversal

Examine left children, then right children, then a node

g

Levelorder

Examine all nodes of depth n first, then nodes depth n+1, etc

g

Most useful Traversal in practice

Inorder

g

Euler tour

Traversal of a tree… Like a walk around the perimeter of a binary tree.

g

Fast addition of new elements, search time, and removal.

Skip List

g

Skip Lists

Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

g

Skip Lists

Skip lists are linked lists that allow you to skip to the correct node. The performance bottleneck inherent in a sequential scan is avoided, while insertion and deletion remain relatively efficient. Average search time is O (lg n ). Worst-case search time is O ( n ), but is extremely unlikely.

g

Disadvantage of Skip List

The one disadvantage of the skip list is that it uses about twice as much memory as needed by the bottommost linked list.

g

Binary Search Tree

A binary search tree is a binary tree that has the following additional property: for each node, the values in all descendants to the left of the node are less than or equal to the value of the node, and the values in all descendants to the right are greater than or equal.

g

Height-balanced binary tree

–Depth of all leaf nodes differ by at most 1 –With height h, contains between 2 h -1 and 2 h nodes

g

Full BInary Tree

A binary tree in which all of the leaves have the same height and every internal node has two childeren

g

Complete Binary Tree

a full tree up to the second last level with the last level of leaves being filled in from left to right (if last level is completely filled, the tree is full) height h –> between 2^(h-1) and 2^h - 1 nodes

g

Binary Search Tree (BST)

* For each node in tree * All data in left subtree is less * All data in right subtree is greater Does not allow for duplicates * If necessary add “or equal to” to ONE of above lines Shape doesn’t matter - can be anywhere from full to linear

g

balanced tree

a tree in which the height of the subtrees are about equal