平衡树：AVL树

节点定义

template<class Key, class Value>
class AVLTreeNode {
	AVLTreeNode* L = nullptr, *R = nullptr;//左右子树
	int deep;//深度
	int	lsize, rsize;//左右字数的深度
	linkNode*>* iterator;//迭代器，如果不想写无序遍历整棵树的，可以忽略
	template<class Key, class Value, class Cmp>
	friend class AVLTree;
public:
	const Key first;//键
	Value second;//值
	AVLTreeNode(const Key& key, Value& val)
		:first(key), second(val) {
		lsize = rsize = 0;
	}
 
	~AVLTreeNode() {}//注意，这边要手动清理Value的内容，这里不清理是为了安全
};

内部方法：

1：pushUp：用两个子节点的信息更新父节点的信息；

2：zig：右旋[依赖与pushUp]

3：zag：左旋[依赖与pushUp]

3：maintainNode[依赖zig/zag]：保持一个节点的平衡

4：takeNode/takeNode_recursion[依赖zig/zag]：删除给定节点

这些方法就是所有内部且不公开与客户端程序员的方法了

下面是代码：

pushUp

template<class Key, class Value, class Cmp>
void AVLTree::pushUp(AVLTreeNode*& node) {
	if (node == nullptr) return;
	if (node->L != nullptr)
		node->lsize = node->L->deep;
	else node->lsize = 0;
	if (node->R != nullptr)
		node->rsize = node->R->deep;
	else node->rsize = 0;
	node->deep = max(node->lsize, node->rsize) + 1;
}

zig

template<class Key, class Value, class Cmp>
void AVLTree::zig(AVLTreeNode*& node) {
	AVLTreeNode* l = node->L;
	if (l == nullptr) return;//如果为空，那么就不需要旋转
	node->L = l->R, l->R = node;
	pushUp(node);
	node = l;
	pushUp(node);
}

zag

template<class Key, class Value, class Cmp>
void AVLTree::zag(AVLTreeNode*& node) {
	AVLTreeNode* r = node->R;
	if (r == nullptr) return;
	node->R = r->L, r->L = node;
	pushUp(node);
	node = r;
	pushUp(node);
}

maintainNode

先判断是左偏还是右偏，然后在判断是否要用双旋

时间复杂度1

template<class Key, class Value, class Cmp>
void AVLTree::maintainNode(AVLTreeNode*& node) {
	if (node == nullptr) return;
	if (node->lsize - node->rsize > 1) {
		if (node->L->rsize > node->L->lsize) {
			zag(node->L);
		}
		zig(node);
	}
	else if (node->rsize - node->lsize > 1) {
		if (node->R->lsize > node->R->rsize) {
			zig(node->R);
		}
		zag(node);
	}
}

tackNode/tackNode_recursion

先将一个点一直左右旋转，直到为叶节点，然后删除掉，注意，我们回溯路径的时候要进行一次反向旋转，时间复杂度logn

template<class Key, class Value, class Cmp>
void AVLTree::tackNode(AVLTreeNode*& node) {
	tackNode_recursion(node);
	pushUp(node);
}
 
template<class Key, class Value, class Cmp>
void AVLTree::tackNode_recursion(AVLTreeNode*& node) {
	if (node->L == nullptr&&node->R == nullptr) {
		Delete(node);
		node = nullptr;
	}
	else {
		if (node->L != nullptr) {
			zig(node);
			tackNode_recursion(node->R);
			zag(node);
		}
		else {
			zag(node);
			tackNode_recursion(node->L);
			zig(node);
		}
	}
}

外部方法：

insert、find、remove、clear，getSize、[begin]、[end]

insert

找到位置，注意，该位置一点是叶子节点，然后沿着路径maintainNode

template<class Key, class Value, class Cmp>
void AVLTree::insert(AVLTreeNode*& node, const Key& k, Value& val) {
	static int ptr;
	if (node == nullptr) {//到空，自己创建一个
		size++;
		node = getNode(k, val);
		node->deep = 1;
		maintainNode(node);
		return;
	}
	else if (cmp(k, node->first) == 0) {//已经存在,k == root->k
		return;
	}
	else if (cmp(k, node->first) == -1) {
		insert(node->L, k, val);
	}
	else {
		insert(node->R, k, val);
	}
	pushUp(node);
	maintainNode(node);
}

remove

找到目标节点，然后tackNode，接着回溯路径maintainNode

template<class Key, class Value, class Cmp>
void AVLTree::remove(AVLTreeNode*& node, const Key& k) {
	if (node == nullptr) {
		return;//没找到
	}
	else if (cmp(k, node->first) == 0) {//找到目标节点
		tackNode(node);
	}
	else if (cmp(k, node->first) == -1) {
		remove(node->L, k);
	}
	else {
		remove(node->R, k);
	}
	pushUp(node);
	maintainNode(node);
}

clear【这里介绍Delete】

撤销一个子树[当要删除一个节点的时候且不希望删除左右子树，要记得将左右子树指针置空]，如果有迭代器，那么也要将对应节点删除

template<class Key, class Value, class Cmp>
void AVLTree::Delete(AVLTreeNode* node) {
	if (node == nullptr) return;
	Delete(node->L);
	Delete(node->R);
	size--;
	iteratorSystem.pop_node(node->iterator);
 
	delete node;
}

其他操作也都大同小异了，本菜就不介绍了，会上面那些操作也就ok了