tailieunhanh - Thuật toán Algorithms (Phần 21)

Tham khảo tài liệu 'thuật toán algorithms (phần 21)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | BALANCED TREES 193 The slant of each 3-node is determined by the dynamics of the algorithm to be described below. There are many red-black trees corresponding to each 2-3-4 tree. It would be possible to enforce a rule that 3-nodes all slant the same way but there is no reason to do so. These trees have many structural properties that follow directly from the way in which they are defined. For example there are never two red links in a row along any path from the root to an external node and all such paths have an equal number of black links. Note that it is possible that one path alternating black-red be twice as long as another all black but that all path lengths are still proportional to A striking feature of the tree above is the positioning of duplicate keys. On reflection it is clear that any balanced tree algorithm must allow records with keys equal to a given node to fall on both sides of that node otherwise severe imbalance could result from long strings of duplicate keys. This implies that we can t find all nodes with a given key by repeated calls to the searching procedure as in the previous chapter. However this does not present a real problem because all nodes in the rooted at a given node with the same key as that node can be found with a simple recursive procedure like the treeprint procedure of the previous chapter. Or the option of requiring distinct keys in the data structure with linked lists of records with duplicate keys could be used. One very nice property of red-black trees is that the treesearch procedure for standard binary tree search works without modification except for the problem with duplicate keys discussed in the previous paragraph . We ll implement the link colors by adding a boolean field red to each node which is true if the link pointing to the node is red false if it is black the treesearch procedure simply never examines that field. That is no overhead is added by the balancing mechanism to the time taken by the fundamental .