平衡二叉搜索树的C++实现

最新推荐文章于 2023-02-25 19:51:55 发布
最新推荐文章于 2023-02-25 19:51:55 发布
阅读量324 收藏
点赞数
分类专栏： 算法 C/C++ 文章标签： c++ 算法 树 AVL BST
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-NC-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/qq_37232329/article/details/127177683
版权

该模板类实现了平衡二叉搜索树的操作，其搜索的效率高达log2n，来看代码:

#pragma once
#include "CStack.hpp"
#include "CQueue.hpp"

template <typename T>
class CAVLTree
{
public:
	// 搜索树的结点结构
	typedef struct tagTreeNode
	{
		tagTreeNode() = default;
		tagTreeNode(T data) :
			m_data(data), m_pLeftChild(nullptr), 
			m_pRightChild(nullptr), m_pParent(nullptr), m_nHeight(1)
		{ }
		T m_data;
		struct tagTreeNode *m_pLeftChild;   // 左孩子指针
		struct tagTreeNode *m_pRightChild;  // 右孩子指针
		struct tagTreeNode *m_pParent;		// 父结点指针
		size_t m_nHeight;					// 结点默认高度
	} TreeNode, *pTreeNode;
public:
	CAVLTree() : m_pRootNode(nullptr) {}
	~CAVLTree();
	// 寻找结点, 寻找值为rcDataToFind的结点并将结点的引用通过参数传回
	bool FindNode(TreeNode &rNode, const T rcDataToFind);
	bool FindNode(pTreeNode *ppNode, const T rcDataToFind);
	// 判定值为rcDataToFind的结点是否存在
	bool FindNode(const T rcDataToFind);
	// 插入结点
	bool InsertNode(T data);
	// 删除结点
	bool DeleteNode(const T &rcdata);
	// 创建一个具有nDataArySize个元素的树
	bool CreateTree(const T *pDataAry, size_t nDataArySize);
	// 执行前序遍历
	void PreOrderTraverse() const;
	// 执行中序遍历
	void InOrderTraverse() const;
	// 执行后续遍历
	void PostOrderTraverse() const;
	// 执行层序遍历
	void LevelOrderTraverse() const;
private:
	// 为转成AVAL树调整高度
	void AdjustHeight(pTreeNode pNode);
	// 左旋
	void LeftRotate(pTreeNode pNode);
	// 右旋
	void RightRotate(pTreeNode pNode);
	// 获取当前结点高度
	size_t GetHeight(const pTreeNode pNode) const
	{
		return(pNode ? (pNode->m_nHeight) : 0);
	}
	// 内部用的max函数
	size_t MaxNodeValue(size_t nLeft, size_t nRight) 
	{
		return((nLeft >= nRight) ? nLeft : nRight);
	}
	// 重新结算当前结点高度
	size_t CalcHeight(pTreeNode pNode);
	// 释放树
	void ReleaseTree();
private:
	pTreeNode m_pRootNode;
};

template <typename T>
CAVLTree<T>::~CAVLTree()
{
	ReleaseTree();
}

template <typename T>
bool CAVLTree<T>::FindNode(pTreeNode *ppNode, const T rcDataToFind)
{
	pTreeNode pCurNode = m_pRootNode;
	T CurNodeData;

	if (!pCurNode)
	{
		return(false);
	}

	while (pCurNode)
	{
		// 获取当前节点数据
		CurNodeData = pCurNode->m_data;
		// 根据数据大小在二叉树内移动
		if (CurNodeData > rcDataToFind)
		{
			pCurNode = pCurNode->m_pLeftChild;
		}
		else if (CurNodeData < rcDataToFind)
		{
			pCurNode = pCurNode->m_pRightChild;
		}
		else
		{
			// 找到后获取并返回
			*ppNode = pCurNode;
			return(true);
		}
	}

	return(false);
}

template <typename T>
void CAVLTree<T>::RightRotate(pTreeNode pNode)
{
	pTreeNode pCurNode = nullptr;
	pTreeNode pCurLNode = nullptr;
	pTreeNode pCurLRNode = nullptr;
	pTreeNode pParentNode = nullptr;

	if (!pNode)
	{
		return;
	}
	pCurNode = pNode;
	pCurLNode = pCurNode->m_pLeftChild;
	pCurLRNode = pCurLNode->m_pRightChild;
	pParentNode = pCurNode->m_pParent;

	// 如果当前结点的父结点不存在说明是根节点
	if (!pParentNode)
	{
		// 更新根结点指向
		m_pRootNode = pCurLNode;
	}
	else
	{
		// 如果不平衡结点的父结点存在则更新父结点的指向
		if (pCurNode == pParentNode->m_pLeftChild)
		{
			// 如果当前结点类型是左结点
			pParentNode->m_pLeftChild = pCurLNode;
		}
		else
		{
			// 如果当前结点类型是右结点
			pParentNode->m_pRightChild = pCurLNode;
		}
	}
	
	pCurLNode->m_pParent = pParentNode;
	
	pCurLNode->m_pRightChild = pCurNode;
	pCurNode->m_pParent = pCurLNode;

	pCurNode->m_pLeftChild = pCurLRNode;
	if (pCurLRNode)
	{
		pCurLRNode->m_pParent = pCurNode;
	}

	CalcHeight(pCurNode);
	CalcHeight(pCurLNode);
}

template <typename T>
size_t CAVLTree<T>::CalcHeight(pTreeNode pNode)
{
	size_t nLeftChildHeight = 0;
	size_t nRightChildHeight = 0;

	if (!pNode)
	{
		return(0);
	}
	nLeftChildHeight = GetHeight(pNode->m_pLeftChild);
	nRightChildHeight = GetHeight(pNode->m_pRightChild);
	pNode->m_nHeight = MaxNodeValue(nLeftChildHeight, nRightChildHeight) + 1;

	return(pNode->m_nHeight);
}

template <typename T>
void CAVLTree<T>::LeftRotate(pTreeNode pNode)
{
	pTreeNode pParentNode = nullptr;
	pTreeNode pCurNode = nullptr;
	pTreeNode pCurRNode = nullptr;
	pTreeNode pCurRLNode = nullptr;

	if (!pNode)
	{
		return;
	}

	pCurNode = pNode;
	pCurRNode = pCurNode->m_pRightChild;
	pCurRLNode = pCurRNode->m_pLeftChild;
	pParentNode = pNode->m_pParent;
	// 如果不平衡结点是根节点
	if (!pParentNode)
	{
		// 更新根节点
		m_pRootNode = pCurRNode;
	}
	else
	{
		// 判定不平衡结点是其父节点的左孩子还是右孩子
		// 并按照此进行左旋
		if (pCurNode == pParentNode->m_pLeftChild)
		{
			pParentNode->m_pLeftChild = pCurRNode;
		}
		else
		{
			pParentNode->m_pRightChild = pCurRNode;
		}
	}

	pCurNode->m_pParent = pCurRNode;
	pCurNode->m_pRightChild = pCurRLNode;
	if (pCurRLNode)
	{
		pCurRLNode->m_pParent = pCurNode;
	}
	pCurRNode->m_pLeftChild = pCurNode;
	pCurRNode->m_pParent = pParentNode;
	// 重新计算高度
	CalcHeight(pCurNode);
	CalcHeight(pCurRNode);

	return;
}

template <typename T>
void CAVLTree<T>::AdjustHeight(pTreeNode pNode)
{
	int iLeftChildHeight = 0;
	int iRightChildHeight = 0;
	
	while (pNode)
	{
		// 计算当前结点的高度
		CalcHeight(pNode);
		// 判定当前结点的平衡因子
		iLeftChildHeight = GetHeight(pNode->m_pLeftChild);
		iRightChildHeight = GetHeight(pNode->m_pRightChild);
		
		if (iRightChildHeight - iLeftChildHeight > 1)
		{
			pTreeNode pRightNode = pNode->m_pRightChild;
			// RR型旋
			if (GetHeight(pRightNode->m_pLeftChild) <= GetHeight(pRightNode->m_pRightChild))
			{
				LeftRotate(pNode);
			}
			else
			{
				// RL型旋
				RightRotate(pRightNode);
				LeftRotate(pNode);
			}
		}
		else if (iLeftChildHeight - iRightChildHeight > 1)
		{
			pTreeNode pLeftNode = pNode->m_pLeftChild;
			if (GetHeight(pLeftNode->m_pLeftChild) >= GetHeight(pLeftNode->m_pRightChild))
			{
				RightRotate(pNode);
			}
			else
			{
				LeftRotate(pLeftNode);
				RightRotate(pNode);
			}
		}

		pNode = pNode->m_pParent;
	}
}

template <typename T>
bool CAVLTree<T>::DeleteNode(const T &rcdata)
{
	pTreeNode pDelNode = nullptr;
	pTreeNode pParentNodeOfDelNode = nullptr;
	pTreeNode pCurNode = nullptr;
	bool fOk = false;

	// 空树直接返回false
	if (!m_pRootNode)
	{
		return(false);
	}
	// 如果是根节点则直接删除后成功
	if (m_pRootNode->m_data == rcdata)
	{
		delete m_pRootNode;
		m_pRootNode = nullptr;
		return(true);
	}
	// 查找要删除的结点, 没有找到直接返回false
	fOk = FindNode(&pDelNode, rcdata);
	if (!fOk)
	{
		return(false);
	}
	// 找到父节点
	pParentNodeOfDelNode = pDelNode->m_pParent;
	// 该结点没有子节点
	if (!pDelNode->m_pLeftChild && !pDelNode->m_pRightChild)
	{
		if (pDelNode == pParentNodeOfDelNode->m_pLeftChild)
		{
			pCurNode = pParentNodeOfDelNode->m_pLeftChild;
			pParentNodeOfDelNode->m_pLeftChild = nullptr;
		}
		else
		{
			pCurNode = pParentNodeOfDelNode->m_pRightChild;
			pParentNodeOfDelNode->m_pRightChild = nullptr;
		}
	}
	else if (pDelNode->m_pLeftChild && pDelNode->m_pRightChild)
	{
		pTreeNode pDelLeftChild = nullptr;
		pTreeNode pDelLeftAndMostRightChild = nullptr;
		pTreeNode pParentNode = nullptr;

		pDelLeftChild = pDelNode->m_pLeftChild;
		pDelLeftAndMostRightChild = pDelLeftChild->m_pRightChild;
		// 找到结点左子树的最右结点
		while (pDelLeftAndMostRightChild)
		{
			pParentNode = pDelLeftAndMostRightChild;
			pDelLeftAndMostRightChild = pDelLeftAndMostRightChild->m_pRightChild;
		}
		if (!pParentNode)
		{
			// 如果左子结点没有右子树, 直接把左子结点的值给需要删除的结点, 然后删除左子结点
			// 获取需要删除的结点
			pCurNode = pDelNode->m_pLeftChild;
			pDelNode->m_data = pDelLeftChild->m_data;
			pDelNode->m_pLeftChild = pDelLeftChild->m_pLeftChild;
			if (pDelLeftChild->m_pLeftChild)
			{
				pDelLeftChild->m_pLeftChild->m_pParent = pDelNode;
			}
		}
		else
		{ 
			// 如果做左子节点存在右子树
			pCurNode = pParentNode;
			pDelNode->m_data = pParentNode->m_data;
			
			if (pParentNode->m_pLeftChild)
			{
				pParentNode->m_pParent->m_pRightChild = pParentNode->m_pLeftChild;
			}
			else
			{
				pParentNode->m_pParent->m_pRightChild = nullptr;
			}
		}
	}
	else
	{
		// 该结点存在1个子树
		if (pDelNode->m_pLeftChild)
		{
			// 被删除结点存在左子树
			if (pDelNode == pParentNodeOfDelNode->m_pLeftChild)
			{
				// 被删结点自身是左结点
				pDelNode->m_pParent->m_pLeftChild = pDelNode->m_pLeftChild;
				pDelNode->m_pLeftChild->m_pParent = pDelNode->m_pParent;
			}
			else
			{
				// 被删结点自身是右结点
				pDelNode->m_pParent->m_pRightChild = pDelNode->m_pLeftChild;
				pDelNode->m_pLeftChild->m_pParent = pDelNode->m_pParent;
			}
		}
		else
		{
			// 被删除结点存在右子树
			if (pDelNode == pParentNodeOfDelNode->m_pLeftChild)
			{
				// 被删结点自身是左结点
				pCurNode = pDelNode->m_pParent->m_pLeftChild;
				pDelNode->m_pParent->m_pLeftChild = pDelNode->m_pRightChild;
				pDelNode->m_pRightChild->m_pParent = pDelNode->m_pParent;
			}
			else
			{
				// 被删结点自身是右结点
				pCurNode = pDelNode->m_pParent->m_pRightChild;
				pDelNode->m_pParent->m_pRightChild = pDelNode->m_pRightChild;
				pDelNode->m_pRightChild->m_pParent = pDelNode->m_pParent;
			}
		}
	}
	AdjustHeight(pCurNode->m_pParent);
	if (pCurNode)
	{
		delete pCurNode;
		pCurNode = nullptr;
	}

	return(true);
}

template <typename T>
void CAVLTree<T>::LevelOrderTraverse() const
{
	CQueue<pTreeNode> queue;
	pTreeNode pCurNode = nullptr;

	if (!m_pRootNode)
	{
		return;
	}

	pCurNode = m_pRootNode;
	//  Insert -> Tail   .....   Head -> Delete
	queue.InsertFromTail(pCurNode);

	while (!queue.IsEmpty())
	{
		queue.GetHeadValue(pCurNode);
		// 队列头部取数据
		if (queue.DeleteFromHead())
		{
			cout << pCurNode->m_data << " ";
			if (pCurNode->m_pLeftChild)
			{
				queue.InsertFromTail(pCurNode->m_pLeftChild);
			}
			if (pCurNode->m_pRightChild)
			{
				queue.InsertFromTail(pCurNode->m_pRightChild);
			}	
		}
	}
	cout << endl;

	return;
}

template <typename T>
void CAVLTree<T>::PreOrderTraverse() const
{
	CStack<pTreeNode> stack;
	pTreeNode pCurTreeNode = nullptr;

	if (!m_pRootNode)
	{
		return;
	}
	pCurTreeNode = m_pRootNode;

	stack.Push(pCurTreeNode);
	while (!stack.IsEmpty())
	{
		pCurTreeNode = stack.GetTop();
		stack.Pop();
		if (pCurTreeNode)
		{
			cout << pCurTreeNode->m_data << " ";
			stack.Push(pCurTreeNode->m_pRightChild);
			stack.Push(pCurTreeNode->m_pLeftChild);
		}
	}
	cout << endl;
	//CStack<pTreeNode> stack;
	//pTreeNode pNode = m_pRootNode;

	//if (!pNode)
	//{
	//	return;
	//}

	//while (true)
	//{
	//	// 把左孩子都压入栈内
	//	while (pNode)
	//	{
	//		cout << pNode->m_data << " ";
	//		stack.Push(pNode);
	//		pNode = pNode->m_pLeftChild;
	//	}

	//	// 栈空了就退出循环
	//	if (stack.IsEmpty())
	//	{
	//		return;
	//	}

	//	do
	//	{
	//		// 弹出栈顶元素
	//		pNode = stack.GetTop();
	//		if (!pNode)
	//		{
	//			break;
	//		}
	//		stack.Pop();
	//		// 找到栈顶元素右孩子
	//		pNode = pNode->m_pRightChild;
	//	} while (!pNode);
	//}
	//
	//return;
}


template <typename T>
void CAVLTree<T>::InOrderTraverse() const
{
	CStack<pTreeNode> stack;
	pTreeNode pCurNode = nullptr;

	if (!m_pRootNode)
	{
		return;
	}
	pCurNode = m_pRootNode;

	while (pCurNode || !stack.IsEmpty())
	{
		if (pCurNode)
		{
			stack.Push(pCurNode);
			pCurNode = pCurNode->m_pLeftChild;
		}
		else
		{
			pCurNode = stack.GetTop();
			stack.Pop();
			cout << pCurNode->m_data << " ";
			pCurNode = pCurNode->m_pRightChild;
		}
	}
	cout << endl;
}

template <typename T>
void CAVLTree<T>::PostOrderTraverse() const
{
	CStack<pTreeNode> stack;
	CStack<T> tmpStack;
	pTreeNode pCurTreeNode = nullptr;

	pCurTreeNode = m_pRootNode;
	stack.Push(pCurTreeNode);

	while (!stack.IsEmpty())
	{
		pCurTreeNode = stack.GetTop();
		stack.Pop();

		if (pCurTreeNode)
		{
			tmpStack.Push(pCurTreeNode->m_data);
			stack.Push(pCurTreeNode->m_pLeftChild);
			stack.Push(pCurTreeNode->m_pRightChild);
		}
	}
	tmpStack.ReverseStack();
	tmpStack.PrintStack();
}


template <typename T>
void CAVLTree<T>::ReleaseTree()
{
	CQueue<pTreeNode> queue;
	pTreeNode pCurNode = nullptr;

	if (!m_pRootNode)
	{
		return;
	}

	pCurNode = m_pRootNode;
	//  Insert -> Tail   .....   Head -> Delete
	queue.InsertFromTail(pCurNode);

	while (!queue.IsEmpty())
	{
		queue.GetHeadValue(pCurNode);
		// 队列头部取数据
		if (queue.DeleteFromHead())
		{
			if (pCurNode->m_pLeftChild)
			{
				queue.InsertFromTail(pCurNode->m_pLeftChild);
			}
			if (pCurNode->m_pRightChild)
			{
				queue.InsertFromTail(pCurNode->m_pRightChild);
			}
			delete pCurNode;
			pCurNode = nullptr;
		}
	}
	m_pRootNode = nullptr;

	return;
}

template <typename T>
bool CAVLTree<T>::CreateTree(const T *pDataAry, size_t nDataArySize)
{
	bool fOk = false;

	for (size_t nIdx = 0; nIdx < nDataArySize; ++nIdx)
	{
		fOk = InsertNode(pDataAry[nIdx]);

		if (!fOk)
		{

		}
	}
}

template <typename T>
bool CAVLTree<T>::FindNode(const T rcDataToFind)
{
	TreeNode CurTreeNode(rcDataToFind);

	return(FindNode(CurTreeNode, rcDataToFind));
}

template <typename T>
bool CAVLTree<T>::FindNode(TreeNode &rNode, const T rcDataToFind)
{
	pTreeNode pCurNode = m_pRootNode;
	T CurNodeData;

	if (!pCurNode)
	{
		return(false);
	}

	while (pCurNode)
	{
		// 获取当前节点数据
		CurNodeData = pCurNode->m_data;
		// 根据数据大小在二叉树内移动
		if (CurNodeData > rcDataToFind)
		{
			pCurNode = pCurNode->m_pLeftChild;
		}
		else if (CurNodeData < rcDataToFind)
		{
			pCurNode = pCurNode->m_pRightChild;
		}
		else 
		{
			// 找到后获取并返回
			rNode = *pCurNode;
			return(true);
		}
	}
	
	return(false);
}



template <typename T>
bool CAVLTree<T>::InsertNode(T data)
{
	pTreeNode pCurNode = m_pRootNode;
	pTreeNode pParentNode = nullptr;
	pTreeNode pNewNode = nullptr;

	do
	{
		// 分配新结点
		pNewNode = new TreeNode(data);
		if (!pNewNode)
		{
			break;
		}
		// 如果树内没有任何结点, 插到根节点返回
		if (!pCurNode)
		{
			m_pRootNode = pNewNode;

			return(true);
		}

		// 树内有结点, 根据BST左小右大的规则
		while (pCurNode)
		{
			// 保存前结点
			pParentNode = pCurNode;
			if (pCurNode->m_data > data)
			{
				pCurNode = pCurNode->m_pLeftChild;
			}
			else if (pCurNode->m_data < data)
			{
				pCurNode = pCurNode->m_pRightChild;
			}
			else
			{
				return(false);
			}
		}
		// 判断插入的位置并插入新结点
		if (pParentNode->m_data > data)
		{
			pParentNode->m_pLeftChild = pNewNode;
			pNewNode->m_pParent = pParentNode;
		}
		else
		{
			pParentNode->m_pRightChild = pNewNode;
			pNewNode->m_pParent = pParentNode;
		}
		AdjustHeight(pNewNode);
		
	} while (false);

	return(true);
}

(完)

平衡二叉树及其调整（含图含代码，C++实现）
chenyu-max
07-20 1256
前言 平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法）。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logn)。 平衡因子(Balance Factor,简称BF)： BF(T) = hL-hR,hL和hR分别代表左右子树高度 我们希望的平衡树是空树或者左右两边高度差不超过1，即 |BF(T)| <=1 如下，图a为AVL树，图b不是AVL树 图a 图b 为什么要有
【数据结构】AVL树——平衡二叉搜索树
2301_79796701的博客
05-25 1953
平衡树：左子树的高度等于右子树的高度不平衡树：左子树的高度不等于等于右子树的高度二叉搜索树很难是一颗平衡树。对二叉树进行插入和删除的操作，或插入大量的数据不够随机，都会是使二叉搜索树不够平衡。极端情况下，二叉树会退化成类似链表的结构，那么二叉搜索树查询数据的效率荡然无存。在二叉树的基础上加入平衡的概念就是平衡二叉搜索树，也叫AVL树。AVL树也不是一颗绝对的平衡树，AVL树的平衡是相对的，它允许左子树和右子树的高度为 1 ，但不能超过 1。
学习-＞C++篇十四：平衡二叉搜索树
u014801954的博客
10-04 408
目录 1.平衡二叉搜索树（AVL树）的定义 2.AVL树是如何平衡的？ 左旋操作 右旋操作 左右双旋操作 右左双旋操作
LeetCode：1382. 将二叉搜索树变平衡(C++带详细注释）
Axe涛的博客
10-16 342
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int>mid;//存中序序列
二叉排序树查找c++_avl树（带有平衡条件的二叉查找树）—C
weixin_39841002的博客
12-06 101
再讲avl树之前我们要先了解什么是二叉查找树。二叉查找树：如图为二叉查找树：1.左子树的所有节点小于根节点2.右子树的所有节点大于根节点3.左右子树均为二叉查找树关于二叉查找树的创建可以参考下面这个文章：夜猫子：二叉查找树的创建和基本操作—c语言​zhuanlan.zhihu.com引入avl树的原因：二叉查找树的特点就是能够快速查找数据，如上图，若查找2，则从左子树开始查找，若查找8，则从右子树...
二叉搜索树与平衡二叉树(详解,含C＋＋代码)
nidayededaye2的博客
01-07 614
常见的平衡树有：AVL树，树堆（Treap），伸展树（Splay tree）,红黑树，B树，B+树等。根节点为val的最大值，然后根据根节点的key把剩余节点分为大于key和小于key，子树依次递归。操作：如果存在左子树，则左子树的最大值就是前驱，如果不存在左子树找第一个右儿子的父节点。左旋：左子树的高度+1，右子树的高度-1。以上的操作set已经实现好了。
C++二叉搜索树的实现代码
最新发布
04-11
为了优化性能，有时候会采用平衡二叉搜索树（如AVL树或红黑树），这样可以保证树的高度大致平衡，从而保证最坏情况下的操作时间复杂度。 C++二叉搜索树的实现对于理解数据结构和算法，以及提升编程技能都是非常有...
二叉搜索树C++代码，可实现树的增删查改，寻找特定元素等功能
12-12
为了解决这一问题，通常会采用平衡二叉搜索树的变种，例如AVL树或红黑树。 C++是一种静态类型、编译式的通用编程语言，它支持多范式编程，包括过程式、面向对象和泛型编程。C++被广泛用于系统/应用软件、游戏开发、...
二叉搜索树查找算法【实现】.rar_C++_C++ 二叉搜索树_organizationzme
09-23
为了保持查找效率，我们可以考虑平衡二叉搜索树，如AVL树或红黑树。这些树通过旋转操作来确保树的高度平衡。 6. **遍历操作**：二叉搜索树支持前序遍历、中序遍历和后序遍历。中序遍历可以得到有序序列，这是因为...
二叉平衡树（C++）
wo_ai_luo_的博客
02-25 1194
平衡二叉树也叫做AVL树,AVL树的名字来源于它的发明作者G.M. Adelson-Velsky 和 E.M. Landis。AVL树是最先发明的自平衡二叉查找树(Self-Balancing Binary Search Tree,简称平衡二叉树。我们怎么知道这棵二叉搜索树平不平衡呢？我们知道，二叉搜索树的搜索时间和高度是有直接关系的，但是我们按递增、递减序输入之后，高度就和n一样了，所以时间复杂度为O(log n).想要优化，就是改变这棵二叉搜索树的高度。
Balance a Binary Search Tree（C++将二叉搜索树变平衡）
coolsunxu的博客
12-29 256
Balance a Binary Search Tree（C++将二叉搜索树变平衡）
AVL树（平衡二叉搜索树）详解及C++代码实现
m0_59074850的博客
12-13 387
AVL树的介绍和代码实现
平衡二叉查找树的构造与遍历（C++）
RToax
04-23 905
首先平衡二叉树是建立在二叉查找树之上的二叉树，需要明白的概念是左旋和右旋，二者代码如下：void rotateLL(Node *&amp;bbst) /* LL型平衡调整：单向右旋平衡处理 */ { Node *lc; lc = bbst-&gt;lchild; bbst-&gt;lchild = lc-&gt;rchild; lc-&gt;rchild = bbst; bbst = l...
二叉查找树转化为平衡二叉树
Tianqinse的博客
08-17 763
为了排除动态查找表中不同的数据排列方式对算法性能的影响，需要考虑在不会破坏二叉排序树本身结构的前提下，将二叉排序树转化为平衡二叉树。 当二叉排序树的平衡性被打破时，就如同扁担的两头出现了一头重一头轻的现象，此时只需要改变扁担的支撑点（树的树根），就能使其重新归为平衡。 使用二叉排序树实现动态查找操作的过程，实际上就是从二叉排序树的根结点到查找元素结点的过程，所以时间复杂度同被查找元素所在的树的深度（层次数）有关。 为了弥补二叉排序树构造时产生影响算法效率的因素，需要对二叉排序树做“平衡化”处理，使其成为一棵
刷题笔记 | 将二叉搜索树变平衡
大虎牙的博客
03-20 235
将二叉搜索树变平衡 二叉查找树（Binary Search Tree）（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。 题目描述 给你一棵二叉搜索树，请你返回一棵平衡后的二叉搜索树，新生成的树应该...
平衡二叉树算法实现C++
weixin_51626421的博客
06-29 2613
数据结构课程设计之平衡二叉树算法实现
《算法》-查找[二叉查找树]
m0_37748303的博客
09-06 508
二叉查找树 二叉查找树是具有有以下性质的二叉树： 若左子树不为空，则左子树上所有节点的值均小于或等于它的根节点的值。 若右子树不为空，则右子树上所有节点的值均大于或等于它的根节点的值。 左、右子树也分别为二叉查找树。 没有键值相等的节点。 复杂度： 算法 平均 平均 空间 O(n) O(n) 搜索 O(log n) O(n) 插入 O(log n) O(n) 删除 O(log n) O(n) 定义节点 class BinarySearchTree(object):
哈希表的C++实现
輚至消亡
10-10 1474
【代码】哈希表的C++实现。
异或加密工具类
輚至消亡
02-13 1297
写了一个异或加密工具类 调用加密字符串 直接加密文件 #define _CRT_SECURE_NO_WARNINGS #include <iostream> using namespace std; class Encrypt { public: // 构造函数 Encrypt(); Encrypt(char *pContent, unsigned char ucKey = 'x'); // 拷贝构造函数 Encrypt(const Encrypt& e); //
C++实现的二叉搜索树源码解析
二叉搜索树的C++实现可以充分利用面向对象的特性，通过构造函数、析构函数、成员函数等，来实现树的构建、数据的添加、查找和删除等操作。 在具体实现上，二叉搜索树的每个节点通常包含三个基本的成员：一个存储...
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值