Binary Search Trees

Сентябрь 7, 2022

Главная
Алгебра
Binary Search Trees

Содержание

2. Binary Trees Binary Search Trees Binary tree is a root left subtree (maybe empty) right subtree
3. Binary Tree Representation Binary Search Trees A B D E C F
4. Dictionary ADT Binary Search Trees Dictionary operations create destroy insert find delete Stores values associated with
5. Dictionary ADT: Used Everywhere Binary Search Trees Arrays Sets Dictionaries Router tables Page tables Symbol tables
6. Search ADT Binary Search Trees Dictionary operations create destroy insert find delete Stores only the keys
7. Dictionary Data Structure: Requirements Binary Search Trees Fast insertion runtime: Fast searching runtime: Fast deletion runtime:
8. Naïve Implementations Binary Search Trees
9. Binary Search Tree Dictionary Data Structure Binary Search Trees Binary tree property each node has ≤
10. Example and Counter-Example Binary Search Trees 3 11 7 1 8 4 5 4 18 10
11. Complete Binary Search Tree Binary Search Trees Complete binary search tree (aka binary heap): Links are
12. In-Order Traversal Binary Search Trees visit left subtree visit node visit right subtree What does this
13. Recursive Find Binary Search Trees Node * find(Comparable key, Node * t) { if (t ==
14. Iterative Find Binary Search Trees Node * find(Comparable key, Node * t) { while (t !=
15. Insert Binary Search Trees void insert(Comparable x, Node * t) { if ( t == NULL
16. BuildTree for BSTs Binary Search Trees Suppose the data 1, 2, 3, 4, 5, 6, 7,
17. Analysis of BuildTree Binary Search Trees Worst case is O(n2) 1 + 2 + 3 +
18. BST Bonus: FindMin, FindMax Binary Search Trees Find minimum Find maximum 20 9 2 15 5
19. Successor Node Binary Search Trees Next larger node in this node’s subtree 20 9 2 15
20. Predecessor Node Binary Search Trees 20 9 2 15 5 10 30 7 17 Next smaller
21. Deletion Binary Search Trees 20 9 2 15 5 10 30 7 17 Why might deletion
22. Lazy Deletion Binary Search Trees Instead of physically deleting nodes, just mark them as deleted simpler
23. Lazy Deletion Binary Search Trees 20 9 2 15 5 10 30 7 17 Delete(17) Delete(15)
24. Deletion - Leaf Case Binary Search Trees 20 9 2 15 5 10 30 7 17
25. Deletion - One Child Case Binary Search Trees 20 9 2 15 5 10 30 7
26. Deletion - Two Child Case Binary Search Trees 30 9 2 20 5 10 7 Delete(5)
27. Delete Code Binary Search Trees void delete(Comparable key, Node *& root) { Node *& handle(find(key, root));
28. Thinking about Binary Search Trees Binary Search Trees Observations Each operation views two new elements at
29. Beauty is Only Θ(log n) Deep Binary Search Trees Binary Search Trees are fast if they’re
30. Dictionary Implementations Binary Search Trees BST’s looking good for shallow trees, i.e. if Depth is small
31. Digression: Tail Recursion Binary Search Trees Tail recursion: when the tail (final operation) of a function
33. Скачать презентацию

Слайд 2

Binary Trees
Binary Search Trees
Binary tree is
a root
left subtree (maybe empty)
right

subtree (maybe empty)
Properties
max # of leaves:
max # of nodes:
average depth for N nodes:
Representation:

Слайд 3

Binary Tree Representation
Binary Search Trees
A
B
D
E
C
F

Слайд 4

Dictionary ADT
Binary Search Trees
Dictionary operations
create
destroy
insert
find
delete
Stores values associated with user-specified keys
values may

be any (homogeneous) type
keys may be any (homogeneous) comparable type

Adrien
Roller-blade demon
Hannah
C++ guru
Dave
Older than dirt
…

insert

find(Adrien)

Adrien
Roller-blade demon

Donald
l33t haxtor

Слайд 5

Dictionary ADT: Used Everywhere
Binary Search Trees
Arrays
Sets
Dictionaries
Router tables
Page tables
Symbol tables
C++ structures
…
Anywhere we need

to find things fast based on a key

Слайд 6

Search ADT
Binary Search Trees
Dictionary operations
create
destroy
insert
find
delete
Stores only the keys
keys may be any

(homogenous) comparable
quickly tests for membership
Simplified dictionary, useful for examples (e.g. CSE 326)

Adrien
Hannah
Dave
…

insert

find(Adrien)

Adrien

Donald

Слайд 7

Dictionary Data Structure: Requirements
Binary Search Trees
Fast insertion
runtime:
Fast searching
runtime:
Fast deletion
runtime:

Слайд 8

Naïve Implementations
Binary Search Trees

Слайд 9

Binary Search Tree Dictionary Data Structure
Binary Search Trees
Binary tree property
each node

has ≤ 2 children
result:
storage is small
operations are simple
average depth is small
Search tree property
all keys in left subtree smaller than root’s key
all keys in right subtree larger than root’s key
result:
easy to find any given key
Insert/delete by changing links

Слайд 10

Example and Counter-Example
Binary Search Trees
3
11
7
1
8
4
5
4
18
10
6
2
11
5
8
20
21
BINARY SEARCH TREE
NOT A
BINARY SEARCH TREE
7
15

Слайд 11

Complete Binary Search Tree
Binary Search Trees
Complete binary search tree
(aka binary heap):
Links

are completely filled, except possibly bottom level, which is filled left-to-right.

Слайд 12

In-Order Traversal
Binary Search Trees
visit left subtree
visit node
visit right subtree
What does this

guarantee with a BST?

In order listing:
2→5→7→9→10→15→17→20→30

Слайд 13

Recursive Find
Binary Search Trees
Node *
find(Comparable key, Node * t)
{
if (t

== NULL) return t;
else if (key < t->key)
return find(key, t->left);
else if (key > t->key)
return find(key, t->right);
else
return t;
}

Runtime:
Best-worse case?
Worst-worse case?
f(depth)?

Слайд 14

Iterative Find
Binary Search Trees
Node *
find(Comparable key, Node * t)
{
while (t

!= NULL && t->key != key)
{
if (key < t->key)
t = t->left;
else
t = t->right;
}
return t;
}

Слайд 15

Insert
Binary Search Trees
void
insert(Comparable x, Node * t)
{
if ( t ==

NULL ) {
t = new Node(x);
} else if (x < t->key) {
insert( x, t->left );
} else if (x > t->key) {
insert( x, t->right );
} else {
// duplicate
// handling is app-dependent
}

Concept:
Proceed down tree as in Find
If new key not found, then insert a new node at last spot traversed

Слайд 16

BuildTree for BSTs
Binary Search Trees
Suppose the data 1, 2, 3, 4,

5, 6, 7, 8, 9 is inserted into an initially empty BST:
in order
in reverse order
median first, then left median, right median, etc.

Слайд 17

Analysis of BuildTree
Binary Search Trees
Worst case is O(n2)
1 + 2 +

3 + … + n = O(n2)
Average case assuming all orderings equally likely:
O(n log n)
averaging over all insert sequences (not over all binary trees)
equivalently: average depth of a node is log n
proof: see Introduction to Algorithms, Cormen, Leiserson, & Rivest

Слайд 18

BST Bonus: FindMin, FindMax
Binary Search Trees
Find minimum
Find maximum
20
9
2
15
5
10
30
7
17

Слайд 19

Successor Node
Binary Search Trees
Next larger node
in this node’s subtree
20
9
2
15
5
10
30
7
17
How many children

can the successor of a node have?

Node * succ(Node * t) {
if (t->right == NULL)
return NULL;
else
return min(t->right);
}

Слайд 20

Predecessor Node
Binary Search Trees
20
9
2
15
5
10
30
7
17
Next smaller node
in this node’s subtree
Node * pred(Node

* t) {
if (t->left == NULL)
return NULL;
else
return max(t->left);
}

Слайд 21

Deletion
Binary Search Trees
20
9
2
15
5
10
30
7
17
Why might deletion be harder than insertion?

Слайд 22

Lazy Deletion
Binary Search Trees
Instead of physically deleting nodes, just mark them

as deleted
simpler
physical deletions done in batches
some adds just flip deleted flag
extra memory for deleted flag
many lazy deletions slow finds
some operations may have to be modified (e.g., min and max)

Слайд 23

Lazy Deletion
Binary Search Trees
20
9
2
15
5
10
30
7
17
Delete(17)
Delete(15)
Delete(5)
Find(9)
Find(16)
Insert(5)
Find(17)

Слайд 24

Deletion - Leaf Case
Binary Search Trees
20
9
2
15
5
10
30
7
17
Delete(17)

Слайд 25

Deletion - One Child Case
Binary Search Trees
20
9
2
15
5
10
30
7
Delete(15)

Слайд 26

Deletion - Two Child Case
Binary Search Trees
30
9
2
20
5
10
7
Delete(5)
Replace node with descendant whose

value is guaranteed to be between left and right subtrees: the successor

Could we have used predecessor instead?

Слайд 27

Delete Code
Binary Search Trees
void delete(Comparable key, Node *& root) {
Node

*& handle(find(key, root));
Node * toDelete = handle;
if (handle != NULL) {
if (handle->left == NULL) { // Leaf or one child
handle = handle->right;
delete toDelete;
} else if (handle->right == NULL) { // One child
handle = handle->left;
delete toDelete;
} else { // Two children
successor = succ(root);
handle->data = successor->data;
delete(successor->data, handle->right);
}
}
}

Слайд 28

Thinking about Binary Search Trees
Binary Search Trees
Observations
Each operation views two new

elements at a time
Elements (even siblings) may be scattered in memory
Binary search trees are fast if they’re shallow
Realities
For large data sets, disk accesses dominate runtime
Some deep and some shallow BSTs exist for any data

Слайд 29

Beauty is Only Θ(log n) Deep
Binary Search Trees
Binary Search Trees are

fast if they’re shallow:
perfectly complete
complete – possibly missing some “fringe” (leaves)
any other good cases?
What matters?
Problems occur when one branch is much longer than another
i.e. when tree is out of balance

Слайд 30

Dictionary Implementations
Binary Search Trees
BST’s looking good for shallow trees, i.e. if

Depth is small (log n); otherwise as bad as a linked list!

Слайд 31

Digression: Tail Recursion
Binary Search Trees
Tail recursion: when the tail (final operation)

of a function recursively calls the function
Why is tail recursion especially bad with a linked list?
Why might it be a lot better with a tree? Why might it not?

Binary Search Trees

Содержание

Binary TreesBinary Search TreesBinary tree isa rootleft subtree (maybe empty) right

Binary Tree RepresentationBinary Search TreesABDECF

Dictionary ADTBinary Search TreesDictionary operationscreatedestroyinsertfinddeleteStores values associated with user-specified keysvalues may

Dictionary ADT: Used EverywhereBinary Search TreesArraysSetsDictionariesRouter tablesPage tablesSymbol tablesC++ structures…Anywhere we need

Search ADTBinary Search TreesDictionary operationscreatedestroyinsertfinddeleteStores only the keyskeys may be any

Dictionary Data Structure: RequirementsBinary Search TreesFast insertionruntime:Fast searchingruntime:Fast deletionruntime:

Naïve ImplementationsBinary Search Trees

Binary Search Tree Dictionary Data StructureBinary Search TreesBinary tree propertyeach node

Example and Counter-ExampleBinary Search Trees31171845418106211582021BINARY SEARCH TREENOT ABINARY SEARCH TREE715

Complete Binary Search TreeBinary Search TreesComplete binary search tree(aka binary heap):Links

In-Order TraversalBinary Search Trees visit left subtree visit node visit right subtreeWhat does this

Recursive FindBinary Search TreesNode *find(Comparable key, Node * t){ if (t

Iterative FindBinary Search TreesNode *find(Comparable key, Node * t){ while (t

InsertBinary Search Treesvoidinsert(Comparable x, Node * t){ if ( t ==

BuildTree for BSTsBinary Search TreesSuppose the data 1, 2, 3, 4,

Analysis of BuildTreeBinary Search TreesWorst case is O(n2)1 + 2 +

BST Bonus: FindMin, FindMaxBinary Search TreesFind minimumFind maximum20921551030717

Successor NodeBinary Search TreesNext larger nodein this node’s subtree20921551030717How many children

Predecessor NodeBinary Search Trees20921551030717Next smaller nodein this node’s subtreeNode * pred(Node

DeletionBinary Search Trees20921551030717Why might deletion be harder than insertion?

Lazy DeletionBinary Search TreesInstead of physically deleting nodes, just mark them

Lazy DeletionBinary Search Trees20921551030717Delete(17)Delete(15)Delete(5)Find(9)Find(16)Insert(5)Find(17)

Deletion - Leaf CaseBinary Search Trees20921551030717Delete(17)

Deletion - One Child CaseBinary Search Trees209215510307Delete(15)

Deletion - Two Child CaseBinary Search Trees3092205107Delete(5)Replace node with descendant whose

Delete CodeBinary Search Treesvoid delete(Comparable key, Node *& root) { Node

Thinking about Binary Search TreesBinary Search TreesObservationsEach operation views two new

Beauty is Only Θ(log n) DeepBinary Search TreesBinary Search Trees are

Dictionary ImplementationsBinary Search TreesBST’s looking good for shallow trees, i.e. if

Digression: Tail RecursionBinary Search TreesTail recursion: when the tail (final operation)

Похожие презентации