【数据结构英文课件】MULTIWAYTREES.pptVIP

? A node with one entry remains unchanged. Red-Black Trees as Binary Search Trees ? A red-black tree is a binary search tree, with links colored red or black, obtained from a B-tree of order 4 by the above conversions. ? Searching and traversal of a red-black tree are exactly the same as for an ordinary binary search tree. Insertion and deletion, require care to maintain the underlying B-tree structure. ? Each node of a red-black tree is colored with the same color as the link immediately above it. We thus need keep only one extra bit of information for each node to indicate its color. The Black Condition Every simple path from the root to an empty subtree goes through the same number of black nodes. ? We adopt the convention that the root is colored black and all empty subtrees (corresponding to NULL links) are colored black. The B-tree requirement that all its empty subtrees are on the same level becomes: ? To guarantee that no more than three nodes are connected by red links as one B-tree node, and that nodes with three entries are a balanced binary tree, we require: The Red Condition If a node is red, then its parent exists and is black. ? We can now define: Definition A red-black tree is a binary search tree in which each node has either the color red or black and that satisfies the black and red conditions. ?If count is nonzero then the node has count+1 children. ? branch[0] points to the subtree containing all records with keys less than that in data[0]. ?For 1 ? position ? count-1, branch[position] points to the subtree with keys strictly between those in the subtrees pointed to by data[position-1] and data[position]. ?branch[count] points to the subtree with keys greater than that of data[count-1]. 参看“幻灯片25”中文定义。 5. Searching and insertion pg.539 template class Record, int order Error_code B_treeRecord, order:: search_tree(Record target) { B_nodeRecord, order *sub_root=root; while(sub_root != NULL) { int position;