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
