Sorting of common data structures and algorithms in the iOS Standard Library

🌿 binary sort tree

The standard implementation of a binary sort tree is a balanced binary tree. Binary sorting trees are mainly used to solve the problems of efficient insertion, efficient retrieval and sorting. The system provides four functions of searching, adding, deleting and traversing nodes of binary sort tree respectively.

The binary sorting tree implemented in iOS is not a balanced binary tree, so the time complexity of retrieval may not be O(logN). Here is the utmost contempt! But implementations on other UNIX systems are correct.

For the data structure of binary sort tree nodes, the system provides a template:

typedef struct node { char *key; // The first data member must be of pointer type! struct node *llink; Struct node *rlink; // subtree} node_t;Copy the code

To implement the binary sorting tree, we need to define the data structure of the nodes ourselves, because all the parameters of the nodes in the following function are void*. So the internal implementation doesn’t care what the structure looks like, but it must conform to the format of the template above.

Header file: #include

Platform: BSD Unix.

1. Search and add

Function signature:

// Find the node, and return NULL if no node is found. void *tfind(const void *key, void *const *rootp, int (*compar) (const void *key1, const void *key2)); // Find the node and add it to the tree if it cannot be found. void *tsearch(const void *key, void **rootp, int (*compar) (const void *key1, const void *key2));Copy the code

Parameters:

Key :[in] What to find or insert

Rootp :[in/out] a pointer to the binary root node pointer. The reason for this output is that to construct a balanced binary tree, the root node may change. If you want to create the first node, you can pass a pointer to a null pointer as input and output.

Compar :[in] node function comparator, this comparator is of the following format:

/* @key1: the keyword passed in by the function. @key2: the key of the node in the tree. Note that this parameter is not the node pointer of the tree, but the key data member of the node. @returnInt compar(const void *key1, const void *key2); const void *key2; const void *key2;Copy the code

Return :[out] For tfind returns a node pointer if the corresponding node is found in the tree, or NULL if not. For tsearch, if the corresponding node is found in the tree, the node pointer is returned; if not, a new node is created and the key to be searched is used as the key attribute of the newly inserted node, and the newly created node is returned.

Description:

These two functions are responsible for lookup and insert operations, respectively. The memory allocation and construction of tree nodes are done by the system.

2. Delete the

Function signature:

void * tdelete(const void *restrict key, void **restrict rootp, int (*compar) (const void *key1, const void *key2));

Copy the code

Parameter: key:[in] Key attribute of the node to be deleted. Rootp: the root node of the [in/out] tree. The root node of the tree is adjusted as nodes are removed to ensure balance, so the value of the pointer is passed. Compar :[in] node function comparator. Return :[out] Returns a pointer to the parent node of the deleted node, the root node itself if the deleted node is the root node, or NULL if the key to be deleted is not in the tree.

Description The system is responsible for the creation and destruction of node memory. Therefore, after a tree node is deleted, the memory of the tree node will be destroyed and cannot be accessed any more. Otherwise, the system will crash.

3. The traverse

Function signature:

void twalk(const void *root, void (*action) (const void *node, VISIT order, int level));

Copy the code

Parameters:

Root :[in] indicates the pointer to the root node of the tree. Because traversal doesn’t adjust the root of the tree.

A tree has three traversal modes: pre-traversal, mid-traversal and post-traversal. Because the system does not know what you want to do with the traversal nodes, it implements the traversal of nodes by providing a callback function. The format of this callback function is as follows:

@node: the node to traverse. @order: The order to traverse. This VISIT is an enumeration type. @level: indicates the tree level of the node being traversed. The level starts at 0 and corresponds to the level of the root node. void action(const void *node, VISIT order, int level);Copy the code

Description:

As can be seen above, to achieve traversal, we must provide a callback to the action function. In the action function, we can achieve various traversals by judging the order parameter of type VISIT. VISIT is defined as follows:

typedef	enum {
	preorder,
	postorder,
	endorder,
	leaf
} VISIT;
Copy the code

When order is preorder or LEAF, the system will perform a pre-order traversal, when order is Postorder or LEAF, and when order is endOrder or LEAF, the system will perform a post-order traversal, The leaf traversal that the system will perform when the value of order is LEAF. The following code demonstrates the handling of traversal.

void action(const void *node, VISIT order, int level)
{
      if(the order = = preorder | | order = = leaf) {/ / preorder traversal}if(the order = = postorder | | order = = leaf) {/ / sequence traversal}if(the order = = endorder | | order = = leaf) {/ / after sequence traversal}if(order == leaf) {// only leaf}}Copy the code

The sample code

Typedef struct _node {char *key; // Define a tree node type. // The contents of the tree node. struct _node *left; struct _node *right; }node_t; // The tree sort comparator function int bintreecompar(const char *key1, const char *key2) {returnstrcmp(key1, key2); } // tree traversal function, where the preceding traversal, according to the tree node ascending output. void action(node_t *node, VISIT order, int level) {if (order == preorder || order == leaf)
     {
          printf("node's key = %s\n", node->key);
     }
}

void main() { node_t *root = NULL; // Define the root node of the tree, which is initially empty. // Add // look at the rules passed here for the root argument, since each insertion may change the value of the root node. node_t *p1 = tsearch("Bob", &root, bintreecompar); We do not need to be responsible for the destruction of the node object, but rather destroy it by calling tdelete. NSAssert(strcmp(p1->key,"Bob") = = 0, @"oops!");
    node_t *p2 = tsearch("Alice", &root, bintreecompar);
    node_t *p3 = tsearch("Max", &root, bintreecompar);
    node_t *p4 = tsearch("Lucy", &root, bintreecompar); // node_t *p = tfind("Lily", &root, bintreecompar);
    NSAssert(p == NULL, @"oops!");
    p =  tfind("Lucy", &root, bintreecompar); NSAssert(p ! = NULL, @"oops!"); // delete p = tdelete("Jone", &root, bintreecompar);
    NSAssert(p == NULL, @"oops!");
    p = tdelete("Lucy", &root, bintreecompar); NSAssert(p ! = NULL, @"oops!"); // Walk through the tree twalk(root, action); }Copy the code