Midterm Flashcards
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.
