* @brief Removes a node from an AVL tree while maintaining balance * * @param[in] node_to_delete The node to be removed from the AVL tree * @param[in,out] ptree Pointer to the root node pointer of the AVL tree * * @note This function removes the specified node from the AVL tree and performs * necessary rebalancing operations. It handles both cases where the node * has no left ch
| 102 | * It uses a stack to track the removal path for rebalancing. |
| 103 | */ |
| 104 | void lwp_avl_remove(struct lwp_avl_struct *node_to_delete, struct lwp_avl_struct **ptree) |
| 105 | { |
| 106 | avl_key_t key = node_to_delete->avl_key; |
| 107 | struct lwp_avl_struct **nodeplace = ptree; |
| 108 | struct lwp_avl_struct **stack[avl_maxheight]; |
| 109 | uint32_t stack_count = 0; |
| 110 | struct lwp_avl_struct ***stack_ptr = &stack[0]; /* = &stack[stackcount] */ |
| 111 | struct lwp_avl_struct **nodeplace_to_delete; |
| 112 | for (;;) |
| 113 | { |
| 114 | struct lwp_avl_struct *node = *nodeplace; |
| 115 | if (node == AVL_EMPTY) |
| 116 | { |
| 117 | return; |
| 118 | } |
| 119 | |
| 120 | *stack_ptr++ = nodeplace; |
| 121 | stack_count++; |
| 122 | if (key == node->avl_key) |
| 123 | break; |
| 124 | if (key < node->avl_key) |
| 125 | nodeplace = &node->avl_left; |
| 126 | else |
| 127 | nodeplace = &node->avl_right; |
| 128 | } |
| 129 | nodeplace_to_delete = nodeplace; |
| 130 | if (node_to_delete->avl_left == AVL_EMPTY) |
| 131 | { |
| 132 | *nodeplace_to_delete = node_to_delete->avl_right; |
| 133 | stack_ptr--; |
| 134 | stack_count--; |
| 135 | } |
| 136 | else |
| 137 | { |
| 138 | struct lwp_avl_struct ***stack_ptr_to_delete = stack_ptr; |
| 139 | struct lwp_avl_struct **nodeplace = &node_to_delete->avl_left; |
| 140 | struct lwp_avl_struct *node; |
| 141 | for (;;) |
| 142 | { |
| 143 | node = *nodeplace; |
| 144 | if (node->avl_right == AVL_EMPTY) |
| 145 | break; |
| 146 | *stack_ptr++ = nodeplace; |
| 147 | stack_count++; |
| 148 | nodeplace = &node->avl_right; |
| 149 | } |
| 150 | *nodeplace = node->avl_left; |
| 151 | node->avl_left = node_to_delete->avl_left; |
| 152 | node->avl_right = node_to_delete->avl_right; |
| 153 | node->avl_height = node_to_delete->avl_height; |
| 154 | *nodeplace_to_delete = node; |
| 155 | *stack_ptr_to_delete = &node->avl_left; |
| 156 | } |
| 157 | lwp_avl_rebalance(stack_ptr, stack_count); |
| 158 | } |
| 159 | |
| 160 | /** |
| 161 | * @brief Inserts a new node into an AVL tree while maintaining balance |
no test coverage detected