Tài liệu, ebook Cơ Sở Dữ Liệu

Summary In this talk, we introduced the idea of balance – We require O(ln(n)) run times – Balance will ensure the height is (ln(n)) There are numerous definitions: – AVL trees use height balancing – Red-black trees use null-path-length balancing – BB(a) trees use weight balancing

20 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1356 | Lượt tải: 2

Applications One application of an 26-ary trees is a trie where the root represents the start of each valid word, and the different sub-trees represent next letters in valid words – Consider the words in the phrase “The fable then faded from my thoughts and memory.” – All 26 sub-trees are only shown for the root node, but all nodes have 26...

20 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1248 | Lượt tải: 1

Array storage Question: why not store any tree as an array using breadth-first traversals? – There is a significant potential for a lot of wasted memory Consider this tree with 12 nodes would require an array of size 32 – Adding a child to node K doubles the required memory

21 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1406 | Lượt tải: 3

Applications Perfect binary trees are considered to be the ideal case – The height and average depth are both (ln(n)) We will attempt to find trees which are as close as possible to perfect binary trees

20 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1508 | Lượt tải: 1

Summary In this talk, we introduced binary trees – Each node has two distinct and identifiable sub-trees – Either sub-tree may optionally be empty – The sub-trees are ordered relative to the other We looked at: – Properties – Applications

32 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1314 | Lượt tải: 2

Summary This topic covered two types of traversals: – Breadth-first traversals – Depth-first traversals – Applications – Determination of how to structure a depth-first traversal

25 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1353 | Lượt tải: 1

Summary In this topic, we have looked at one implementation of a general tree: – store the value of each node – store all the children in a linked list – not an easy (Q(1)) way to access children – if we use an array, different problems.

21 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1371 | Lượt tải: 1

Summary In this topic, we have: – Introduced the terminology used for the tree data structure – Discussed various terms which may be used to describe the properties of a tree, including: • root node, leaf node • parent node, children, and siblings • ordered trees • paths, depth, and height • ancestors, descendants, and subtrees – We looke...

42 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1432 | Lượt tải: 1

Summary We have considered the implementation of linked lists in C++ – Aspects of the Node class – Accessors and mutators – The implementation of various member functions – Stepping through a linked list – Defining the copy and assignment operator – Defining move constructors and move assignment operators – Discussed efficiencies

147 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1467 | Lượt tải: 3

Summary In this topic, we have introduced the more general deque abstract data structure – Allows insertions and deletions from both ends of the deque – Internally may be represented by either a doubly-linked list or a twoended array More important, we looked at the STL and the design pattern of an iterator

34 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1399 | Lượt tải: 1