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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Binary Search Trees, слайд №1Binary Search Trees, слайд №2Binary Search Trees, слайд №3Binary Search Trees, слайд №4Binary Search Trees, слайд №5Binary Search Trees, слайд №6Binary Search Trees, слайд №7Binary Search Trees, слайд №8Binary Search Trees, слайд №9Binary Search Trees, слайд №10Binary Search Trees, слайд №11Binary Search Trees, слайд №12Binary Search Trees, слайд №13Binary Search Trees, слайд №14Binary Search Trees, слайд №15Binary Search Trees, слайд №16Binary Search Trees, слайд №17Binary Search Trees, слайд №18Binary Search Trees, слайд №19Binary Search Trees, слайд №20Binary Search Trees, слайд №21Binary Search Trees, слайд №22Binary Search Trees, слайд №23Binary Search Trees, слайд №24Binary Search Trees, слайд №25Binary Search Trees, слайд №26Binary Search Trees, слайд №27Binary Search Trees, слайд №28Binary Search Trees, слайд №29Binary Search Trees, слайд №30Binary Search Trees, слайд №31Binary Search Trees, слайд №32
Скачать
Вы можете ознакомиться и скачать презентацию на тему Binary Search Trees. Доклад-сообщение содержит 32 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


Binary Search Trees SDP4
Описание слайда:
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:
Описание слайда:
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
Описание слайда:
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
Описание слайда:
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
Описание слайда:
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)
Описание слайда:
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:
Описание слайда:
Dictionary Data Structure: Requirements Fast insertion runtime: Fast searching runtime: Fast deletion runtime:

Слайд 8


Naïve Implementations
Описание слайда:
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
Описание слайда:
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
Описание слайда:
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.
Описание слайда:
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?
Описание слайда:
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; }
Описание слайда:
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; }
Описание слайда:
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 }
Описание слайда:
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.
Описание слайда:
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
Описание слайда:
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
Описание слайда:
BST Bonus: FindMin, FindMax Find minimum Find maximum

Слайд 19


Successor Node Next larger node in this node’s subtree
Описание слайда:
Successor Node Next larger node in this node’s subtree

Слайд 20


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

Слайд 21


Deletion
Описание слайда:
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)
Описание слайда:
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
Описание слайда:
Lazy Deletion

Слайд 24


Deletion - Leaf Case
Описание слайда:
Deletion - Leaf Case

Слайд 25


Deletion - One Child Case
Описание слайда:
Deletion - One Child Case

Слайд 26


Deletion - Two Child Case
Описание слайда:
Deletion - Two Child Case

Слайд 27


Delete Code
Описание слайда:
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
Описание слайда:
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
Описание слайда:
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!
Описание слайда:
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?
Описание слайда:
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
Описание слайда:
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

Скачать

Теги Binary Search Trees
Похожие презентации
Mypresentation.ru
Загрузить презентацию