Loading [MathJax]/jax/input/TeX/jax.js
文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
首页
学习
活动
专区
圈层
工具
MCP广场
返回腾讯云官网
社区首页 >专栏 >【C++】AVL树

【C++】AVL树

作者头像
zxctscl
发布于 2024-12-04 00:13:34
发布于 2024-12-04 00:13:34
15100
代码可运行
举报
文章被收录于专栏：zxctscl个人专栏zxctscl个人专栏
运行总次数：0
代码可运行
关联问题
换一批

个人主页 ： zxctscl 如有转载请先通知

1. 底层结构

前面对map/multimap/set/multiset进行了简单的介绍: 【C++】map和set ，在其文档介绍中发现，这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。

2. AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年 发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

因为有些节点的数量，像2和4，做不到高度差相等，所以规则就退而求其次，左右高度差不超过1。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树： 它的左右子树都是AVL树 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) 平衡因子并不是必须的，只是它的一种实现方式。

平衡因子=右子树高度-左子树高度

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在

O(log2n)

，搜索时间复杂度O(

log2n

)。

3. AVL树节点的定义

AVL树节点的定义：

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
template<class T>
struct AVLTreeNode
{
	AVLTreeNode(const T& data)
		: _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr)
		, _data(data), _bf(0)
	{}
	AVLTreeNode<T>* _pLeft; // 该节点的左孩子
	AVLTreeNode<T>* _pRight; // 该节点的右孩子
	AVLTreeNode<T>* _pParent; // 该节点的双亲
	T _data;
	int _bf; // 该节点的平衡因子
};

4. AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么 AVL树的插入过程可以分为两步：

  1. 按照二叉搜索树的方式插入新节点
  2. 调整节点的平衡因子（更新插入节点的祖先节点的平衡因子） （1）插入到父亲的左边，父亲平衡因子减减 （2）插入到父亲的右边，父亲平衡因子加加 （3）如果父亲节点的平衡因子等于0，父亲所在子树高度不变，不再继续往上更新，插入结束。 （4）如果父亲的平衡因子是1或者-1，父亲所在子树高度变了，继续往上更新 （5）如果父亲的平衡因子是2或者-2，父亲所在子树已经不平衡了，需要旋转处理。 更新中不可能出现其它值，插入之前树是AVL树，平衡因子是-1 0 1，加加减减最多出现（3）（4）（5）情况。

插入一个节点，先判断，如果root为空，就先插入第一个节点：

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

用cur指向root，插入比root大往右走，是比较pair的first，比root小往左走：

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);

		if (parent->_kv.first <kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

但是这里是三叉链，这里得和父亲链接起来：cur->_parent = parent; 这里得更新平衡因子：插入到父亲的左边，父亲平衡因子减减；插入到父亲的右边，父亲平衡因子加加；平衡因子等于0，父亲所在子树高度不变，更新结束。平衡因子是1或者-1，父亲所在子树高度变了，继续往上更新，父亲的平衡因子是2或者-2，父亲所在子树已经不平衡了

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
	while (parent)
		{
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				// 更新结束
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				// 继续往上更新
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				// 当前子树出问题了，需要旋转平衡一下


				break;
			}
			else
			{
				// 理论而言不可能出现这个情况
				assert(false);
			}
		}

5. AVL树的旋转

这里用抽象图来代表某一类： abc代表高度为h的AVL子树：

在a这里插入新节点，a的高度变化从h变成h+1，就会把30的平衡因子更新为-1；

具象图：

  1. h==0： 30这里新增一个节点。
  1. h==1： 在20的左边或者右边新增都会引发旋转
  1. h==2 高度为2的AVL树有三种：

b和c是x/y/z中的任意一种 a只能是z这种情况，如果a是x这种情况：

那么当a插入一个节点，像下面这样，高度不变，就不会往上更新：

如果长这样：它自己就不旋转了：

所以a一定就是下面这种形状，插入一个节点才会引发旋转:

当h==2时候，a插入一个节点，就会引发旋转

b和c三种形状都可以，而插入可以选择4个节点中任何一个，所以

  1. h==3 高度为3最满的就是下面这样，4个节点可能是满的C44，四个节点中任意选三，四个节点中任意选两个，四个节点中任意选一个，这些都可能是高度为h的情况。光树就可能有15种。

a如果是下面这种情况：就有8种插入新节点的可能：

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构， 使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

  1. 新节点插入较高左子树的左侧—左左：右单旋(左边高，往右边压）

b变成60的左边，30<b子树<60<c子树

所以当h==1时候，也是同样的右边压

旋转后的a c位置没变，把60变到30右边，b变到60左边：

此时代码就是：

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;

		Node* ppNode = parent->_parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}

			subL->_parent = ppNode;
		}

		parent->_bf = subL->_bf = 0;
	}
  1. 新节点插入较高右子树的右侧—右右：左单旋

现在右边高，让subRL变成30的右边，30<b<60<c：

右边高，左边旋：

代码和右单旋类似：

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		subR->_left = parent;
		Node* ppNode = parent->_parent;

		parent->_parent = subR;

		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_right == parent)
			{
				ppNode->_right = subR;
			}
			else
			{
				ppNode->_left = subR;
			}
			subR->_parent = ppNode;
		}

		parent->_bf = subR->_bf = 0;
	}

像下面这样的情况，发现右边高，就左单旋，而出来结果导致左边高，再右单旋，发现结果和刚开始一样。

上面这个图并不是纯粹的右边高，它是右边高，左边高，不像纯粹的右边高（下面图这样）：

这不是单纯的右边高，右边高，左边高

以8为旋转点，进行右边单旋啊，经过这个单旋，变成单纯的右边高。在意parent为旋转点进行左单选：

  1. 新节点插入较高左子树的右侧—左右：先左单旋再右单旋

将双旋变成单旋后再旋转，即：先对30进行左单旋，然后再对90进行右单旋，旋转完成后再 考虑平衡因子的更新。

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		int bf = subLR->_bf;

		RotateL(parent->_left);
		RotateR(parent);

		if (bf == -1)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 1)
		{
			subLR->_bf = 0;
			subL->_bf = -1;
			parent->_bf = 0;
		}
		else if (bf == 0)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}

	}
  1. 新节点插入较高右子树的左侧—右左：先右单旋再左单旋

总结： 假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑

  1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR 当pSubR的平衡因子为1时，执行左单旋 当pSubR的平衡因子为-1时，执行右左双旋
  2. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL 当pSubL的平衡因子为-1是，执行右单旋 当pSubL的平衡因子为1时，执行左右双旋 旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新
代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

		RotateR(subR);
		RotateL(parent);

		subRL->_bf = 0;
		if (bf == 1)
		{
			subR->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
		}
		else
		{
			parent->_bf = 0;
			subR->_bf = 0;
		}
	}

6. AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

  1. 验证其为二叉搜索树 如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
  2. 验证其为平衡树 （1）每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子) （2）节点的平衡因子是否计算正确
代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
	  int _Size(Node* root)
	{
		return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;
	}


		int _Height(Node* root)
		{
			if (root == nullptr)
				return 0;
			/*int leftHeight= _Height(root->_left);
			int rightHeight = _Height(root->_right);*/

			return max(_Height(root->_left), _Height(root->_right)) + 1;
		}

		bool _IsBalance(Node* root)
		{
			if (root == nullptr)
				return true;

			int leftHeight = _Height(root->_left);
			int rightHeight = _Height(root->_right);

			if (abs(leftHeight - rightHeight) >= 2)//不平衡
			{
				cout << root->_kv.first << endl;
				return false;
			}
			
			// 顺便检查一下平衡因子是否正确
			if (rightHeight - leftHeight != root->_bf)
			{
				cout << root->_kv.first << endl;
				return false;
			}

			return _IsBalance(root->_left)
				&& _IsBalance(root->_right);
		}

测试用例：

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
void TestAVLTree2()
{
	const int N = 100000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
		//cout << v.back() << endl;
	}

	size_t begin2 = clock();
	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
		//cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	}
	size_t end2 = clock();

	cout << "Insert:" << end2 - begin2 << endl;
	//cout << t.IsBalance() << endl;

	cout << "Height:" << t.Height() << endl;
	cout << "Size:" << t.Size() << endl;

	size_t begin1 = clock();
	// 确定在的值
	for (auto e : v)
	{
		t.Find(e);
	}

	// 随机值
	/*for (size_t i = 0; i < N; i++)
	{
		t.Find((rand() + i));
	}*/

	size_t end1 = clock();

	cout << "Find:" << end1 - begin1 << endl;
}

AVL树的性能： AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即

log2(N)

。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

7. AVLTree.h

代码语言：javascript
代码运行次数：0
运行
AI代码解释
复制
#pragma once
#include<assert.h>
#include<vector>


template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;

	int _bf;  // balance factor

	AVLTreeNode(const pair<K, V>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _bf(0)
	{}
};

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	// logN
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		//...
		// 更新平衡因子
		while (parent)
		{
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				// 更新结束
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				// 继续往上更新
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				// 当前子树出问题了，需要旋转平衡一下
				if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				else if(parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}

				break;
			}
			else
			{
				// 理论而言不可能出现这个情况
				assert(false);
			}
		}


		return true;
	}



	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;
	}


	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}


	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;

		Node* ppNode = parent->_parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}

			subL->_parent = ppNode;
		}

		parent->_bf = subL->_bf = 0;
	}


	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		subR->_left = parent;
		Node* ppNode = parent->_parent;

		parent->_parent = subR;

		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_right == parent)
			{
				ppNode->_right = subR;
			}
			else
			{
				ppNode->_left = subR;
			}
			subR->_parent = ppNode;
		}

		parent->_bf = subR->_bf = 0;
	}

	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

		RotateR(subR);
		RotateL(parent);

		subRL->_bf = 0;
		if (bf == 1)
		{
			subR->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
		}
		else
		{
			parent->_bf = 0;
			subR->_bf = 0;
		}
	}

	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		int bf = subLR->_bf;

		RotateL(parent->_left);
		RotateR(parent);

		if (bf == -1)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 1)
		{
			subLR->_bf = 0;
			subL->_bf = -1;
			parent->_bf = 0;
		}
		else if (bf == 0)
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	bool IsBalance()
	{
		return _IsBalance(_root);
	}

	int Height()
	{
		return _Height(_root);
	}

	int Size()
	{
		return _Size(_root);
	}


private:
  	  int _Size(Node* root)
	{
		return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;
	}

		int _Height(Node* root)
		{
			if (root == nullptr)
				return 0;
			/*int leftHeight= _Height(root->_left);
			int rightHeight = _Height(root->_right);*/

			return max(_Height(root->_left), _Height(root->_right)) + 1;
		}

		bool _IsBalance(Node* root)
		{
			if (root == nullptr)
				return true;

			int leftHeight = _Height(root->_left);
			int rightHeight = _Height(root->_right);

			if (abs(leftHeight - rightHeight) >= 2)//不平衡
			{
				cout << root->_kv.first << endl;
				return false;
			}
			
			// 顺便检查一下平衡因子是否正确
			if (rightHeight - leftHeight != root->_bf)
			{
				cout << root->_kv.first << endl;
				return false;
			}

			return _IsBalance(root->_left)
				&& _IsBalance(root->_right);
		}


		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}

			_InOrder(root->_left);
			cout << root->_kv.first << ":" << root->_kv.second << endl;
			_InOrder(root->_right);
		}
private:
	Node* _root = nullptr;
};

void TestAVLTree1()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	AVLTree<int, int> t1;
	for (auto e : a)
	{
		t1.Insert({ e,e });
		/*cout <<"Insert"<<e<<"->" << t1.IsBalance() << endl;*/
	}

	t1.InOrder();
	cout << t1.IsBalance() << endl;
}

void TestAVLTree2()
{
	const int N = 100000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
		//cout << v.back() << endl;
	}

	size_t begin2 = clock();
	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
		//cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	}
	size_t end2 = clock();

	cout << "Insert:" << end2 - begin2 << endl;
	//cout << t.IsBalance() << endl;

	cout << "Height:" << t.Height() << endl;
	cout << "Size:" << t.Size() << endl;

	size_t begin1 = clock();
	// 确定在的值
	for (auto e : v)
	{
		t.Find(e);
	}

	// 随机值
	/*for (size_t i = 0; i < N; i++)
	{
		t.Find((rand() + i));
	}*/

	size_t end1 = clock();

	cout << "Find:" << end1 - begin1 << endl;
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-12-03，如有侵权请联系 cloudcommunity@tencent.com 删除
搜索
c++
int
parent
root

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

搜索
c++
int
parent
root
评论
登录后参与评论
暂无评论
登录 后参与评论
推荐阅读
编辑精选文章
换一批
万字详解高可用架构设计
4445
Go 开发者必备：Protocol Buffers 入门指南
2727
10分钟带你彻底搞懂分布式链路跟踪
1917
多租户的 4 种常用方案
3921
亿级月活的社交 APP，陌陌如何做到 3 分钟定位故障？
2772
60页PPT全解：DeepSeek系列论文技术要点整理
4102
浅谈区块链去中心化问题
区块链访问管理
区块链从技术上，最看好以可信随机数为核心的共识机制。就是说从一百个节点中随机抽取10个节点来做事情。
广州闪链科技
2018/12/08
1.3K0
浅谈区块链去中心化问题
区块链+旅游业
区块链分布式大数据
随着全球经济的持续发展，旅游业展现出强大生命力。据WTTC与牛津经济研究院统计，2017年旅游业增长3.8%，创造价值高达7.9万亿美元。旅游行业的迅速发展催生了在线旅游平台（OTA）的兴起，这种提供市场渠道、旅行产品、周边服务等一体服务的平台迅速吸引了大量用户，旅游市场被OTA所垄断。OTA的运营成本不可避免的转换为用户高昂的出行费用。
广州闪链科技
2018/10/19
1.3K0
区块链+旅游业
从区块链看新旧技术交替 No.80
大数据数据处理
区块链也火了很长一段时间了，2018 可能是区块链野蛮生长的一年，结合之前看过的一本书《创新者的窘境》 聊聊新旧技术的交替，以及区块链技术什么时候能得到重用。 先稍微说说区块链目前在应用中存在什么问题。 1、不可篡改、撤销 现在各个领域因为程序问题或者客户投诉问题，总是会出现非常多的数据修订，但如果使用了区块链技术，可能就没那么方便了，因为数据是不可篡改的。但是其实这还是可以解决的，有正向的交易，那就有逆向的交易即可。 2、交易账本必须公开 如果交易账本是完全公开的，那么不可避免就会出现很多的隐私问题。比
大蕉
2018/02/05
7430
从区块链看新旧技术交替 No.80
区块链小知识：公有链和联盟链的区别
编程算法比特币数字货币
从2008年比特币相关的论文发布到现在2020年6月，区块链技术经历了十余年的发展，尤其最近5年发展蓬勃成果密集。单从媒体角度看，2019年之前区块链圈主要是“币圈”发声，金融机构对区块链探索领先于其他行业，而在2019年10月24日在中央政治局集体学习区块链技术的发展和现状之后，“链圈”代表技术联盟链开始逐步走入大众视野，政务、能源、进出口等更多的行业开始关注和探索区块链在自己领域可能带来的深远影响。
bengbengsu
2022/04/26
6.8K0
区块链小知识：公有链和联盟链的区别
EKT多链技术谈 | 闪电网络、多链、分片、DAG——区块链的横向扩展
区块链比特币数字货币
前言：认真来说，传统的BFT共识机制是一种效率不高的算法，由于每笔交易都要通过所有节点验证，验证结果需要被广播到网络，换句话说，一笔交易要先被广播到网络一次，然后每个节点都要再广播一次，这就导致了一笔交易有O(N^2)的消息复杂度。计算机背景的同学都知道，O(N^2)是一个很低效的 方案，直接导致BFT在大于1000个节点之后同步能力明显下降。对于比特币的POW，因为任何矿工节点发现符合当前难度的块之后，把交易打包进块里，向全网(N)广播，然后网络上的所有的全节点验证这个交易的哈希，即可证伪，所以实际上是一种一对多且不需要回复的共识机制，也即O(N)的复杂度。目前共识算法研究的前沿是如何实现O(1)算法，叫做横向扩展(scale-out)，也即一笔交易不广播到全网，或者说，有的交易有的节点并不知道，这样就可以解决区块链的可扩展性问题。目前出现在大家视野里的O(1)共识算法有off-chain(链下通道)，sharding(分片)，DAG(有向无环图)，multi-chain(多链)等等，每种算法都有其特点和长处，本文将解读这类横向扩展的解决方案。
风中凌乱的靓仔
2019/03/22
1.4K0
EKT多链技术谈 | 闪电网络、多链、分片、DAG——区块链的横向扩展
除了游戏和医疗，腾讯区块链还准备做什么？
游戏区块链
本文从技术的角度详细介绍了腾讯云区块链TBAAS系统上的最新应用场景。
腾讯技术工程官方号
2018/05/11
8.9K5
晓说区块链 | 去中心化为什么对区块链如此重要？
区块链分布式比特币数字货币
区块链分为布式思维、代码化思维、共识性思维这三大思维，哪种思维最重要呢？去中心化公开信息又是为什么对区块链来说如此重要？
维基链WICC
2018/11/27
1K0
晓说区块链 | 去中心化为什么对区块链如此重要？
两万字深度长文！从原理到趋势，解剖风口上的区块链技术
其他
前言：区块链不是一项新技术，而是一个新的技术组合。其关键技术包括P2P动态组网、基于密码学的共享账本、共识机制、智能合约等技术； 科技史上大部分创新都是与生产力有关的，提升效率，让人做更少工作，让机器做更多工作；区块链带来的最主要的颠覆却是生产关系上的； 互联网实现了信息的传播，区块链实现了价值的转移；区块链可以看作是“价值互联网”的基础协议，类似于“信息互联网”的HTTP协议，二者都是建议在TCP/IP协议之上的应用层协议； 区块链并不是一个全能技术，在某些应用领域里相比传统技术并不具备明显的技术优势，
刘盼
2018/03/16
1.5K0
两万字深度长文！从原理到趋势，解剖风口上的区块链技术
【案例】蜂巢链：基于区块链的资产证劵化
区块链
【案例】蜂巢链：基于区块链的资产证劵化
数据猿
2018/04/25
1.7K0
【案例】蜂巢链：基于区块链的资产证劵化
正本清源区块链——Caoz
区块链安全比特币数字货币
本课程内容分为两部分： 第一部分，烧脑篇，介绍区块链的技术概念，目标本源和技术演进，以及信息安全相关的风险。 第二部分，诱惑篇，介绍区块链的产业链，相关产业的收益模式和未来的潜在商业空间。谁在赚钱，赚什么钱。
Daotin
2018/08/31
3K0
正本清源区块链——Caoz
区块链是什么（上）超通俗的区块链入门干货
区块链比特币分布式
区块链是比特币的底层技术，不等同于比特币。有人说比特币就是一场泡沫，甚至放话“比特币是传销”。区块链作为继互联网后的新一波技术浪潮，本身无罪，况且炒币只是区块链里最初级的玩法。读完这篇文章，我们就能弄懂大部分区块链基础知识，从而离保守和狭隘远一点。
互链脉搏
2018/05/18
2.7K0
区块链是什么（上）超通俗的区块链入门干货
区块链众筹的创想N次方
区块链
近两年区块链逐渐成为热门话题，不断在媒体、学术和金融界出现。国内外大量的知名企业纷纷加入针对区块链研究的社区和联盟，争取在区块链技术爆发之前，了解区块链技术，应用区块链改变自身业务形态。区块链研究不断
用户1310347
2018/03/02
2.1K0
区块链众筹的创想N次方
杭州趣链创始人李启雷：区块链并不是万能的，去中心化才是目的
其他
数据猿导读 结合区块链的可信任、自动化、多中心等特征，其在银行、供应链金融、物联网以及智能制造等方面都有很好的应用实践。其中，在银行领域，区块链技术可以涉及数字汇票、供应链金融、同业和监管以及其他业务
数据猿
2018/04/24
1.3K0
杭州趣链创始人李启雷：区块链并不是万能的，去中心化才是目的
区块链技术中的矛与盾
区块链数字货币
作为一种分布式账本技术，区块链系统记录所有的交易信息，并在所有参与者之间进行共享。系统的每个参与方都可以拥有账本的相同副本、验证每一笔交易。毫无疑问，相比于传统的中心化系统，区块链技术为业务提供了更高的透明度。
bengbengsu
2022/04/26
5120
区块链的“善”与“恶”：炒币不等于区块链
区块链游戏数字货币比特币
区块链技术发展还需要一个过程。 3月5日，英雄互娱联合恺英网络宣布，面向海外用户，基于用户体验来启动和研发区块链项目。随后，6日早间消息出来，比特大陆董事长吴忌寒确认了对该项目的投资：“区块链技术将给游戏行业带来影响深远的变革。作为本项目的天使投资人，我很荣幸从一开始就参与其中。” 一时间，“区块链应用”话题再次被推上了至高点。 以“数字货币”入局 区块链在金融领域步履维艰 区块链这项技术，作为比特币的底层技术，伴随着数字货币的兴起，而被大家熟知。虽然区块链是作为比特币的底层技术呈现在世人面前，但区块链并
镁客网
2018/05/29
1.3K2
区块链链游项目系+统开+发
游戏存储区块链
1）依托公链。最普遍的也最方便，如 BSC、Solana、AVAX 上线的游戏，将游 戏嫁接到链上。
用户10176617
2022/11/11
1.2K1
区块链链游项目系+统开+发
区块链有限公司 区块链去中心化有何作为？
区块链
区块链价值传递可以应用到各大产业中，未来也必将是促进各界产业转型的巨大动力，无论是企业的材料订购、生产售出，还是民众从需求搜索到实物使用，都能通过区块链节点的信息计算得到快速匹配，节点信息公认让造假成本高昂，除非你改变链上全部的信息造假，否则单节点将遭所有人排斥！所以无需担心“假货”、“诈骗”等问题。
用户3126099
2018/09/20
1.1K0
区块链有限公司 区块链去中心化有何作为？
企业应该选择哪种区块链
区块链企业
随着探索如何把区块链应用在各种场景，许多人就想到，也许不需要全世界的人共同参与，也不需要挖矿，我们只需要用到区块链的可信任、可追溯特性，通过较少节点达到拜占庭将军容错，于是私有链就诞生了。但私有链仍是中心化的，难以维持去中心化的优势。因此又有了为企业联盟而生的联盟链（consortium blockchain）。
南坡海瑞
2019/04/17
1.8K0
企业应该选择哪种区块链
区块链技术原理
区块链
本文主要是对区块链进行概念分析和组成技术解析，从哈希运算、数字签名、共识算法、智能合约、P2P网络等技术在区块链中的应用进行综合分析
憧憬博客
2021/06/24
7.3K0
区块链技术原理
区块链入门总结区块链
区块链比特币编程算法二叉树存储
新交易创建 -> 交易广播网络 -> 交易验证 -> 验证结果通过网络广播 -> 交易写账本
若与
2018/09/29
55.6K1
区块链入门总结区块链
推荐阅读
编辑精选文章
万字详解高可用架构设计Go 开发者必备：Protocol Buffers 入门指南10分钟带你彻底搞懂分布式链路跟踪多租户的 4 种常用方案亿级月活的社交 APP，陌陌如何做到 3 分钟定位故障？60页PPT全解：DeepSeek系列论文技术要点整理
相关讨论
怎样学习Linux操作？如何高效化学习Linux内核？linux服务器新手怎么学习？
相关课程
AI绘画-StableDiffusion图像生成微信公众号在线学习平台搭建实践_《硅谷课堂》低代码实战营
浅谈区块链去中心化问题
1.3K0
区块链+旅游业
1.3K0
从区块链看新旧技术交替 No.80
7430
区块链小知识：公有链和联盟链的区别
6.8K0
EKT多链技术谈 | 闪电网络、多链、分片、DAG——区块链的横向扩展
1.4K0
除了游戏和医疗，腾讯区块链还准备做什么？
8.9K5
晓说区块链 | 去中心化为什么对区块链如此重要？
1K0
两万字深度长文！从原理到趋势，解剖风口上的区块链技术
1.5K0
【案例】蜂巢链：基于区块链的资产证劵化
1.7K0
正本清源区块链——Caoz
3K0
区块链是什么（上）超通俗的区块链入门干货
2.7K0
区块链众筹的创想N次方
2.1K0
杭州趣链创始人李启雷：区块链并不是万能的，去中心化才是目的
1.3K0
区块链技术中的矛与盾
5120
区块链的“善”与“恶”：炒币不等于区块链
1.3K2
区块链链游项目系+统开+发
1.2K1
区块链有限公司 区块链去中心化有何作为？
1.1K0
企业应该选择哪种区块链
1.8K0
区块链技术原理
7.3K0
区块链入门总结区块链
55.6K1
相关推荐
浅谈区块链去中心化问题
更多 >
开水泡饭0
LV.0
这个人很懒，什么都没有留下～
文章
16
获赞
45
专栏
1
作者相关精选
换一批
交个朋友
加入行业数字化趋势交流群
解读转型政策方向 参考企业落地案例
加入讨论
的问答专区 >
tracywang0
工程师擅长3个领域
相关课程
一站式学习中心 >
AI绘画-StableDiffusion图像生成
1706人在学
腾讯混元生图
高性能应用服务
微信公众号在线学习平台搭建实践_《硅谷课堂》
396人在学
文件存储
云点播
CODING DevOps
低代码实战营
280人在学
微搭低代码
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2025 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论
2