Tài liệu, ebook Công Nghệ Thông Tin

Tìm kiếm trên BST Chọn hướng tìm theo tính chất của BST: So sánh với node gốc, nếu đúng thì tìm thấy Tìm bên nhánh trái (hay phải) nếu khóa cần tìm nhỏ hơn (hay lớn hơn) khóa của node gốc Giống phương pháp tìm kiếm nhị phân Thời gian tìm kiếm Tốt nhất và trung bình: O(lg n) Tệ nhất: O(n)

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

Domain Relational Calculus (1)  The formal specification of the domain calculus was proposed after the development of the QBE language and system.  Domain calculus differs from tuple calculus in the type of variables used in formulas: the variables range over single values from domains of attributes.  To form a relation of degree n for a q...

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

 Step 9: Mapping of Union Types (Categories)  Create a new relation S for the category with a primary key.  Include any attributes of the category in S.  If superclasses have different keys:  Include a new key attribute, called surrogate key, as foreign key in each relation of the superclasses.  These foreign keys reference to the prima...

59 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1757 | Lượt tải: 0

Physical database design  The process of producing a description of the implementation of the database on secondary storage.  Describes the base relations, file organizations, and indexes design used to achieve efficient access to the data, and any associated integrity constraints and security measures.

48 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1703 | Lượt tải: 0

Exercise 3 (2)  Attic keeps track of its clients through the assigning of client numbers. They also keep track of clients’ names and addresses.  When Attic sells an item to a client, they need to keep track of the actual selling price, the date of the sale, and the sales tax.  When Attic buys an item, they wish to track the purchase cost, c...

61 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1826 | Lượt tải: 0

Problems with ER Models (2)  Fan Trap  Where a model represents a relationship between entity types, but pathway between certain entity occurrences is ambiguous.  Usually: two or more 1:N relationships fan out from the same entity.  Chasm Trap  Where a model suggests the existence of a relationship between entity types, but pathway do...

73 trang | Chia sẻ: vutrong32 | Ngày: 17/10/2018 | Lượt xem: 1491 | Lượt tải: 0

AVL Trees as Arrays? We previously saw that: – Complete tree can be stored using an array using Q(n) memory – An arbitrary tree of n nodes requires O(2n) memory Is it possible to store an AVL tree as an array and not require exponentially more memory?

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

Summary In this topic, we covered binary search trees – Described Abstract Sorted Lists – Problems using arrays and linked lists – Definition a binary search tree – Looked at the implementation of: • Empty, size, height, count • Front, back, insert, erase • Previous smaller and next larger objects

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

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: 1142 | 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: 1043 | Lượt tải: 1