Презентация на тему Binary Search Trees

Презентация на тему Презентация на тему Binary Search Trees, предмет презентации: Информатика. Этот материал содержит 32 слайдов. Красочные слайды и илюстрации помогут Вам заинтересовать свою аудиторию. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций ThePresentation.ru в закладки!

Слайды и текст этой презентации

Слайд 1
Текст слайда:

Binary Search Trees

SDP4


Слайд 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:

A

B

D

E

C

F

H

G

J

I


Слайд 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

4

12

10

6

2

11

5

8

14

13

7

9


Слайд 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.

7

17

9

3

15

5

8

1

4

6


Слайд 12
Текст слайда:

In-Order Traversal

Binary Search Trees

visit left subtree
visit node
visit right subtree

What does this guarantee with a BST?

20

9

2

15

5

10

30

7

17

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;
}

20

9

2

15

5

10

30

7

17

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;
}

20

9

2

15

5

10

30

7

17


Слайд 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)

20

9

2

15

5

10

30

7

17


Слайд 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?


Слайд 32
Текст слайда:

Making Trees Efficient: Possible Solutions

Binary Search Trees

Keep BSTs shallow by maintaining “balance”
AVL trees

… also exploit most-recently-used (mru) info
Splay trees

Reduce disk access by increasing branching factor
B-trees


Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика