学步园

/* SplayTree.c -- 自顶向下伸展树实现文件 */<br /> #include "SplayTree.h"</p> <p>/* 外部变量引用 */</p> <p>extern Node * NullNode ;</p> <p>/* 局部函数声明 */</p> <p>static Node * singleRotateWithLeft (Node * const position) ;<br /> static Node * singleRotateWithRight (Node * const position) ;<br /> static void upDataLeftSubTreeCount (Node * const headerRight) ;<br /> static void upDataRightSubTreeCount (Node * const headerLeft) ;<br /> static Node * splay (Node * root, const Item * const pi) ;<br /> static void release (Node * const root) ;</p> <p>/* 接口函数定义 */</p> <p>BOOL Create_S (SplayTree * const pst)<br /> {<br /> NullNode = (Node *) malloc (sizeof (Node)) ;<br /> if (NULL == NullNode)<br /> return FALSE ;<br /> *pst = (struct splayTree *) malloc (sizeof (struct splayTree)) ;<br /> if (NULL == *pst)<br /> {<br /> free (NullNode) ;<br /> NullNode = NULL ;<br /> return FALSE ;<br /> }<br /> else<br /> {<br /> NullNode -> left = NullNode -> right = NullNode ;<br /> NullNode -> leftSubTreeCount = NullNode -> rightSubTreeCount = 0 ;<br /> (*pst) -> root = NullNode ;<br /> (*pst) -> current = 0 ;<br /> return TRUE ;<br /> }<br /> }</p> <p>BOOL IsEmpty_S (const SplayTree * const pst)<br /> {<br /> if (NullNode == (*pst) -> root)<br /> return TRUE ;<br /> else<br /> return FALSE ;<br /> }</p> <p>BOOL Insert_S (const SplayTree * const pst, const Item * const pi)<br /> {<br /> static Node * newNode = NULL ;<br /> Node * root ;</p> <p> /* If it had tried to insert a item that has been inserted to the tree just now, */<br /> /* it won't need allocate memory space. */<br /> if (NULL == newNode)<br /> {<br /> newNode = (Node *) malloc (sizeof (Node)) ;<br /> if (NULL == newNode)<br /> return FALSE ;<br /> }<br /> newNode -> item = *pi ;</p> <p> if (NullNode == (*pst) -> root)<br /> {<br /> newNode -> left = newNode -> right = NullNode ;<br /> newNode -> leftSubTreeCount = newNode -> rightSubTreeCount = 0 ;<br /> (*pst) -> root = newNode ;<br /> }<br /> else<br /> {<br /> (*pst) -> root = splay ((*pst) -> root, pi) ;<br /> root = (*pst) -> root ;<br /> if (*pi < root -> item)<br /> {<br /> newNode -> leftSubTreeCount = root -> leftSubTreeCount ;<br /> newNode -> left = root -> left ;<br /> root -> leftSubTreeCount = 0 ;<br /> root -> left = NullNode ;<br /> newNode -> rightSubTreeCount = root -> rightSubTreeCount + 1 ;<br /> newNode -> right = root ;<br /> (*pst) -> root = newNode ;<br /> }<br /> else if (*pi > (*pst) -> root -> item)<br /> {<br /> newNode -> rightSubTreeCount = root -> rightSubTreeCount ;<br /> newNode -> right = root -> right ;<br /> root -> rightSubTreeCount = 0 ;<br /> root -> right = NullNode ;<br /> newNode -> leftSubTreeCount = root -> leftSubTreeCount + 1 ;<br /> newNode -> left = root ;<br /> (*pst) -> root = newNode ;<br /> }<br /> else<br /> /* Already in the tree. */<br /> return FALSE ;<br /> }</p> <p> /* So next insert will call malloc. */<br /> newNode = NULL ;</p> <p> (*pst) -> current++ ;<br /> return TRUE ;<br /> }</p> <p>Node * Retrieve_S (const SplayTree * const pst)<br /> {<br /> if (IsEmpty_S (pst))<br /> return NULL ;<br /> else<br /> return (*pst) -> root ;<br /> }</p> <p>BOOL Find_S (const SplayTree * const pst, const Item * const pi)<br /> {<br /> splay ((*pst) -> root, pi) ;<br /> if (*pi == (*pst) -> root -> item)<br /> return TRUE ;<br /> else<br /> return FALSE ;<br /> }</p> <p>Node * FindKthMin_S (const SplayTree * const pst, int k)<br /> {<br /> Node * scan ;</p> <p> if (k > (*pst) -> current || k <= 0)<br /> return NULL ;<br /> scan = (*pst) -> root ;</p> <p> while (1)<br /> {<br /> if (scan -> leftSubTreeCount + 1 == k)<br /> break ;<br /> else if (scan -> leftSubTreeCount >= k)<br /> scan = scan -> left ;<br /> else<br /> {<br /> k = k - scan -> leftSubTreeCount - 1 ;<br /> scan = scan -> right ;<br /> }<br /> }<br /> /* Not must to do. */<br /> (*pst) -> root = splay ((*pst) -> root, &scan -> item) ;</p> <p> return scan ;<br /> }</p> <p>Node * FindKthMax_S (const SplayTree * const pst, int k)<br /> {<br /> Node * scan ;</p> <p> if (k > (*pst) -> current || k <= 0)<br /> return NULL ;<br /> scan = (*pst) -> root ;</p> <p> while (1)<br /> {<br /> if (scan -> rightSubTreeCount + 1 == k)<br /> break ;<br /> else if (scan -> rightSubTreeCount >= k)<br /> scan = scan -> right ;<br /> else<br /> {<br /> k = k - scan -> rightSubTreeCount - 1 ;<br /> scan = scan -> left ;<br /> }<br /> }<br /> (*pst) -> root = splay ((*pst) -> root, &scan -> item) ;</p> <p> return scan ;<br /> }</p> <p>Node * FindMin_S (const SplayTree * const pst)<br /> {<br /> Node * scan = (*pst) -> root ;</p> <p> while (scan -> left != NullNode)<br /> scan = scan -> left ;</p> <p> return scan ;<br /> }</p> <p>Node * FindMax_S (const SplayTree * const pst)<br /> {<br /> Node * scan = (*pst) -> root ;</p> <p> while (scan -> right != NullNode)<br /> scan = scan -> right ;</p> <p> return scan ;<br /> }</p> <p>BOOL Delete_S (const SplayTree * const pst, const Item * const pi)<br /> {<br /> Node * root ;</p> <p> if (IsEmpty_S (pst))<br /> return FALSE ;<br /> (*pst) -> root = splay ((*pst) -> root, pi) ;<br /> root = (*pst) -> root ;<br /> if (*pi == root -> item)<br /> {<br /> /* Found it! */<br /> if (NullNode == root -> left)<br /> (*pst) -> root = root -> right ;<br /> else<br /> {<br /> (*pst) -> root = root -> left ;<br /> /* To set (*pst) -> root -> right = NullNode. */<br /> (*pst) -> root = splay ((*pst) -> root, pi) ;<br /> (*pst) -> root -> right = root -> right ;<br /> }<br /> free (root) ;<br /> (*pst) -> current-- ;<br /> return TRUE ;<br /> }<br /> else<br /> return FALSE ;<br /> }</p> <p>void Traversal_S (const Node * const pr, void (* pfun) (const Node * const pn))<br /> {<br /> if (pr != NullNode)<br /> {<br /> Traversal_S (pr -> left, pfun) ;<br /> (* pfun) (pr) ;<br /> Traversal_S (pr -> right, pfun) ;<br /> }<br /> }</p> <p>void Release_S (const SplayTree * const pst)<br /> {<br /> release ((*pst) -> root) ;<br /> free (*pst) ;<br /> free (NullNode) ;<br /> }</p> <p>/* 局部函数定义 */</p> <p>static Node * singleRotateWithLeft (Node * const position)<br /> {<br /> Node * child ;</p> <p> child = position -> left ;<br /> position -> leftSubTreeCount = child -> rightSubTreeCount ;<br /> position -> left = child -> right ;<br /> child -> rightSubTreeCount = position -> leftSubTreeCount + position -> rightSubTreeCount + 1 ;<br /> child -> right = position ;</p> <p> return child ;<br /> }</p> <p>static Node * singleRotateWithRight (Node * const position)<br /> {<br /> Node * child ;</p> <p> child = position -> right ;<br /> position -> rightSubTreeCount = child -> leftSubTreeCount ;<br /> position -> right = child -> left ;<br /> child -> leftSubTreeCount = position -> leftSubTreeCount + position -> rightSubTreeCount + 1 ;<br /> child -> left = position ;</p> <p> return child ;<br /> }</p> <p>static void upDataLeftSubTreeCount (Node * const headerRight)<br /> {<br /> if (headerRight != NullNode)<br /> {<br /> if (headerRight -> left != NullNode)<br /> {<br /> upDataLeftSubTreeCount (headerRight -> left) ;<br /> headerRight -> leftSubTreeCount = headerRight -> left -> leftSubTreeCount + headerRight -> left -> rightSubTreeCount + 1 ;<br /> }<br /> else<br /> headerRight -> leftSubTreeCount = 0 ;<br /> }<br /> }</p> <p>static void upDataRightSubTreeCount (Node * const headerLeft)<br /> {<br /> if (headerLeft != NullNode)<br /> {<br /> if (headerLeft -> right != NullNode)<br /> {<br /> upDataRightSubTreeCount (headerLeft -> right) ;<br /> headerLeft -> rightSubTreeCount = headerLeft -> right -> leftSubTreeCount + headerLeft -> right -> rightSubTreeCount + 1 ;<br /> }<br /> else<br /> headerLeft -> rightSubTreeCount = 0 ;<br /> }<br /> }</p> <p>/* NullNode -> leftSubTreeCount = NullNode -> rightSubTreeCount = 0. */<br /> static Node * splay (Node * root, const Item * const pi)<br /> {<br /> Node header ;<br /> Node * left_tree_max, * right_tree_min ;</p> <p> header.left = header.right = NullNode ;<br /> left_tree_max = right_tree_min = &header ;<br /> NullNode -> item = *pi ;</p> <p> while (*pi != root -> item)<br /> {<br /> if (*pi < root -> item)<br /> {<br /> if (*pi < root -> left -> item)<br /> root = singleRotateWithLeft (root) ;<br /> if (NullNode == root -> left)<br /> break ;<br /> /* Link right. */<br /> right_tree_min -> left = root ;<br /> right_tree_min = root ;<br /> root = root -> left ;<br /> }<br /> else<br /> {<br /> if (*pi > root -> right -> item)<br /> root = singleRotateWithRight (root) ;<br /> if (NullNode == root -> right)<br /> break ;<br /> /* Link left. */<br /> left_tree_max -> right = root ;<br /> left_tree_max = root ;<br /> root = root -> right ;<br /> }<br /> }<br /> /* Reassemble. */<br /> left_tree_max -> right = root -> left ;<br /> right_tree_min -> left = root -> right ;<br /> root -> left = header.right ;<br /> root -> right = header.left ;<br /> upDataLeftSubTreeCount (root -> right) ;<br /> upDataRightSubTreeCount (root -> left) ;<br /> if (root -> left != NullNode)<br /> root -> leftSubTreeCount = root -> left -> leftSubTreeCount + root -> left -> rightSubTreeCount + 1 ;<br /> else<br /> root -> leftSubTreeCount = 0 ;<br /> if (root -> right != NullNode)<br /> root -> rightSubTreeCount = root -> right -> leftSubTreeCount + root -> right -> rightSubTreeCount + 1 ;<br /> else<br /> root -> rightSubTreeCount = 0 ;</p> <p> return root ;<br /> }</p> <p>static void release (Node * const root)<br /> {<br /> if (root != NullNode)<br /> {<br /> release (root -> left) ;<br /> release (root -> right) ;<br /> free (root) ;<br /> }<br /> }