readme.txt

提供了rbtree ttree avltree list hashtable等常用容器的算法,代码经过uclinux + arm44b0平台验证

//					*/
//
//					/* 根据逻辑,以下条件必然成立 */
//					assert(node->base.right && node->base.right->left);
//
//					/* 作一次旋转,完成转化工作 */
//					__rotate_right((bstree_node_t **)&avl_tree->root, node->base.right->left);
//
//					/*
//					* 重新计算L与C的高度 从图看出C,B,D这三分支是不受旋转影响的
//					* R的高度减1
//					* A的高度加1
//					*/
//					assert(node->base.right);
//					assert(node->base.right->right);
//
//					((myavltree_node_t *)(node->base.right->right))->height --;
//					((myavltree_node_t *)(node->base.right))->height ++;
//
//					assert(avltree_left_height((myavltree_node_t *)(node->base.right->right)) + 1 == ((myavltree_node_t *)(node->base.right->right))->height ||
//						avltree_right_height((myavltree_node_t *)(node->base.right->right)) + 1 == ((myavltree_node_t *)(node->base.right->right))->height);
//					assert(avltree_left_height(((myavltree_node_t *)(node->base.right))) + 1 == ((myavltree_node_t *)(node->base.right))->height ||
//						avltree_right_height(((myavltree_node_t *)(node->base.right))) + 1 == ((myavltree_node_t *)(node->base.right))->height);
//
//					/* 重新计算left_lh与left_rh */
//					right_lh = avltree_left_height((myavltree_node_t *)node->base.right);
//					right_rh = avltree_right_height((myavltree_node_t *)node->base.right);
//				}
//
//				assert(right_rh >= right_lh);
//
//				/*
//				* 情况1:左子树的左分支比右分支高1层
//				*      node                     R           
//				*      / \                     /  \
//				*     L   R                node    C
//				*         /\        -->     / \   / \
//				*        A  C              L   A  B  D
//				*          / \
//				*         B   D
//				*/
//
//				/*
//				* 情况2: 左子树的左右分支一样高 视同情况1 注意R此时长高了一层
//				*      node                      R
//				*      / \                     /  \
//				*     L   R                node     C
//				*        / \        -->   / \      /  \
//				*       A   C            L   A     E   F
//				*      / \ / \              / \
//				*     B  D E  F            B   D
//				*/
//
//				/* 做一次旋转即可完成工作 */
//				__rotate_left((bstree_node_t **)&avl_tree->root, node->base.right);
//
//				/* 此时node重新指向R */
//				node = (myavltree_node_t *)node->base.parent;
//
//				assert(node && node->base.left);
//
//				((myavltree_node_t *)(node->base.left))->height = avltree_cal_height((myavltree_node_t *)node->base.left);
//				//if(right_lh == right_rh)
//				node->height = avltree_cal_height(node);
//				//else
//
//				/* 根据逻辑得出,此条件必成立 */
//				assert(node->height == (avltree_left_height(node) + 1) ||
//					node->height == (avltree_right_height(node) + 1) );
//
//				assert(avltree_left_height((myavltree_node_t *)(node->base.left)) + 1 == ((myavltree_node_t *)(node->base.left))->height ||
//					avltree_right_height((myavltree_node_t *)(node->base.left)) + 1 == ((myavltree_node_t *)(node->base.left))->height);
//			}
//		}
//
//		/*
//		* 重新计算节点的高度,指针回溯
//		*/
//		node = (myavltree_node_t *)node->base.parent;
//	}
//}
//
///**
// * @brief 删除指定节点node
// */
//static __INLINE__ void avltree_del(myavltree_t * avl_tree, myavltree_node_t * node)
//{
//	/* 回溯平衡的起始节点 */
//	myavltree_node_t * node_balance = node;
//
//	/* 要销毁的节点 */
//	myavltree_node_t * node_replace = node;
//
//	assert(node && avl_tree);
//
//	/*
//	* 如果删除的是"内部节点",通过寻找对应替代节点,转化为删除"外部节点"
//	*
//	*      root
//	*      /  \
//	*     ?    del_node --> 要删除的节点
//	*          / \
//	*         ?   ?
//	*        / \
//	*       ?   x ---> 替代节点
//	*
//	* 删除del_node这个节点,最终可以转化为删除x节点
//	*/
//
//	if(node->base.left && node->base.right)
//	{
//		node_replace = (myavltree_node_t *)node->base.left;
//
//		/*
//		* 寻找左子树的最"右"边的节点,作为替代节点
//		*/
//		while(node_replace->base.right)
//			node_replace = (myavltree_node_t *)(node_replace->base.right);
//	}
//
//	if(node_replace->base.parent)
//		node_balance = (myavltree_node_t *)node_replace->base.parent;
//	else
//	{
//		/*
//		* 说明node是根节点
//		*/
//		assert(node == avl_tree->root);
//		assert(NULL == node->base.left || NULL == node->base.right);
//
//		if(node->base.left)
//			avl_tree->root = (myavltree_node_t *)node->base.left;
//		else
//			avl_tree->root = (myavltree_node_t *)node->base.right;
//
//		if(avl_tree->root)
//			avl_tree->root->base.parent = NULL;
//		return;
//	}
//
//	/*
//	* 如果需要用替代节点
//	*/
//	if(node_replace != node)
//	{
//		/*
//		* node的父节点指向node_replace
//		*/
//		if(node->base.parent)
//		{
//			if((bstree_node_t *)node == node->base.parent->left)
//				node->base.parent->left = (bstree_node_t *)node_replace;
//			else
//				node->base.parent->right = (bstree_node_t *)node_replace;
//		}
//		else/* 说明要删除的是根节点 */
//		{
//			avl_tree->root = node_replace;
//		}
//
//		/*
//		* node左孩子的父节点指针指向指向node_replace(如果node_replace不是node的左孩子)
//		*/
//		assert(node->base.left);
//		if(node_replace != (myavltree_node_t *)node->base.left)
//			node->base.left->parent = (bstree_node_t *)node_replace;
//		else
//			node_balance = node_replace;
//
//		/*
//		* node右孩子的父节点指向指向node_replace
//		*/
//		assert(node->base.right && node_replace != (myavltree_node_t *)node->base.right);
//		node->base.right->parent = (bstree_node_t *)node_replace;
//
//		/*
//		* 如果node_replace的左孩子存在,令它指向node_replace->base.parent(即node_balance)
//		*/
//		if(node_replace->base.left)
//			node_replace->base.left->parent = (bstree_node_t *)node_balance;
//
//		/*
//		* node_replace的左孩子挂到node_replace的父节点相应的位置
//		*/
//		assert(NULL == node_replace->base.right);
//		assert(node_replace->base.parent);
//		if((bstree_node_t *)node_replace == node_replace->base.parent->left)
//			node_replace->base.parent->left = node_replace->base.left;
//		else
//			node_replace->base.parent->right = node_replace->base.left;
//
//		/*
//		* 给node_replace的左右孩子以及父节点重新赋值
//		*/
//		node_replace->base.left = node->base.left;
//		node_replace->base.right = node->base.right;
//		node_replace->base.parent = node->base.parent;
//
//		node_replace->height = node->height;
//	}
//	else
//	{
//		if(node->base.left)
//		{
//			if(node->base.parent)
//			{
//				if((bstree_node_t *)node == node->base.parent->left)
//					node->base.parent->left = node->base.left;
//				else
//					node->base.parent->right = node->base.left;
//			}
//			else/* 说明要删除的是根节点 */
//			{
//				avl_tree->root = (myavltree_node_t *)node->base.left;
//			}
//
//			node->base.left->parent = node->base.parent;
//		}
//		else if(node->base.right)
//		{
//			if(node->base.parent)
//			{
//				if((bstree_node_t *)node == node->base.parent->left)
//					node->base.parent->left = node->base.right;
//				else
//					node->base.parent->right = node->base.right;
//			}
//			else/* 说明要删除的是根节点 */
//			{
//				avl_tree->root = (myavltree_node_t *)node->base.right;
//			}
//
//			node->base.right->parent = node->base.parent;
//		}
//		else if(node->base.parent)
//		{
//			if((bstree_node_t *)node == node->base.parent->left)
//				node->base.parent->left = NULL;
//			else
//				node->base.parent->right = NULL;
//		}
//	}
//
//	assert(node_balance != node);
//	assert(node_balance);
//
//	avltree_balance(avl_tree, node_balance);
//}
//