CSE 331: Binary Search Trees

0.0(0)
studied byStudied by 0 people
0.0(0)
full-widthCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/27

encourage image

There's no tags or description

Looks like no tags are added yet.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

28 Terms

1
New cards
2
New cards
3
New cards
4
New cards
5
New cards
Leaf
A tree node with no children
6
New cards
Internal Node
A node with at least one child
7
New cards
Root
The one tree node with no parent (the "top" node). If the root has no children, and therefore is the tree's only node, the root is a leaf. Otherwise the root is an internal node.
8
New cards
Parent
A node with a child that is that child's parent.
9
New cards
A nodes ancestors
include the nodes parent, the parent's parent, etc., up to the tree's root
10
New cards
A nodes descendants
include the node's children, the children's children, etc.
11
New cards
edge
the link from anode to a child
12
New cards
A node's depth
the number of edges on the path from the root to the node.
13
New cards
tree level
what all nodes with the same depth form
14
New cards
Binary Tree Subtree
any node X in the tree, and all of X's descendants.
15
New cards
What are trees commonly used to represent?
Hierarchical data. A tree can represent files and directories in a file system, since a file system is a hierarchy.
16
New cards
Binary Space Partitioning (BSP)
a technique of repeatedly separating a region of space into two parts and cataloging objects contained within the regions
17
New cards
BST Ordering Property
each node's key is > all keys in the node's left subtree and < all keys in the node's right subtree
18
New cards
BST node's successor
the node that comes after in the BST ordering
19
New cards
BST node's predecessor
the node that comes before in the BST ordering
20
New cards
BST worst case
requires H + 1 comparisons, meaning O(H) comparisons, where H is the tree height
21
New cards
A complete tree's height
H = log base 2 of N (+! if. not perfect and in worst case)
22
New cards
How does BSTInsertNode() traverse?
It traverses the tree from the root to a leaf node to find the insertion location.
23
New cards
BSTInsertKey() Best Case
O(log N)
24
New cards
BSTInsertKey() WorstCase
O(N)
25
New cards
BST remove operation
removes the first-found matching node, restructuring the tree to preserve the BST ordering property
26
New cards
Inorder traversal algorithm
visits all nodes in tree once and performs an operation on each node. Visits all nodes in a BST from smallest to largest.
27
New cards
What does postorder traversal do?
adds the keys to keyList after the two recursive calls. Visits all the tree's leaves first and the root last.
28
New cards
What does preorder traversal do?
It matches the insertion order. It can be used to duplicate a BST.