Binary Search Trees - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Binary Search Trees. Доклад-сообщение содержит 32 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1

Описание слайда:

Binary Search Trees SDP4

Слайд 2

Описание слайда:

Binary 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

Слайд 4

Описание слайда:

Dictionary ADT 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

Слайд 5

Описание слайда:

Dictionary ADT: Used Everywhere 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 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)

Слайд 7

Описание слайда:

Dictionary Data Structure: Requirements Fast insertion runtime: Fast searching runtime: Fast deletion runtime:

Слайд 8

Описание слайда:

Naïve Implementations

Слайд 9

Описание слайда:

Binary Search Tree Dictionary Data Structure 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

Слайд 11

Описание слайда:

Complete Binary Search Tree 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 visit left subtree visit node visit right subtree What does this guarantee with a BST?

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

Iterative Find 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 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 }

Слайд 16

Описание слайда:

BuildTree for BSTs 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 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 Find minimum Find maximum

Слайд 19

Описание слайда:

Successor Node Next larger node in this node’s subtree

Слайд 20

Описание слайда:

Predecessor Node

Слайд 21

Описание слайда:

Deletion

Слайд 22

Описание слайда:

Lazy Deletion 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

Слайд 24

Описание слайда:

Deletion - Leaf Case

Слайд 25

Описание слайда:

Deletion - One Child Case

Слайд 26

Описание слайда:

Deletion - Two Child Case

Слайд 27

Описание слайда:

Delete Code

Слайд 28

Описание слайда:

Thinking about 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 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 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 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 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