国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

【樹】二叉樹堆與堆排序平衡(AVL)樹紅黑(RB)樹

2年前作者：布逆呲沒來分類：Toy博客閱讀(19)違法舉報

這篇具有很好參考價值的文章主要介紹了【樹】二叉樹堆與堆排序平衡(AVL)樹紅黑(RB)樹。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點(diǎn)擊"舉報違法"按鈕提交疑問。

1 樹

1.1 認(rèn)識樹

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個有限結(jié)點(diǎn)組成一個具有層次關(guān)系的集合。

【樹】二叉樹堆與堆排序平衡(AVL)樹紅黑(RB)樹,數(shù)據(jù)結(jié)構(gòu),c++筆記,算法,數(shù)據(jù)結(jié)構(gòu)

有一個特殊的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，根節(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)

除根節(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成M(M>0)個互不相交的集合T1、T2、……、Tm，其中每一個集合Ti(1<= i<= m)又是一棵結(jié)構(gòu)與樹類似的子樹。每棵子樹的根結(jié)點(diǎn)有且只有一個前驅(qū)，可以有0個或多個后繼。

因此，樹是遞歸定義的。

注意：樹形結(jié)構(gòu)中

子樹之間不能有交集，否則就不是樹形結(jié)構(gòu)

除了根節(jié)點(diǎn)外，每個結(jié)點(diǎn)有且僅有一個父結(jié)點(diǎn)

一顆N各結(jié)點(diǎn)的樹有N-1條邊

1.2 樹的相關(guān)概念

節(jié)點(diǎn)的度：一個節(jié)點(diǎn)含有的子樹的個數(shù)稱為該節(jié)點(diǎn)的度；如上圖：A的為6

葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)；如上圖：B、C、H、I…等節(jié)點(diǎn)為葉節(jié)點(diǎn)

非終端節(jié)點(diǎn)或分支節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)；如上圖：D、E、F、G…等節(jié)點(diǎn)為分支節(jié)點(diǎn)

雙親節(jié)點(diǎn)或父節(jié)點(diǎn)：若一個節(jié)點(diǎn)含有子節(jié)點(diǎn)，則這個節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)；如上圖：A是B的父節(jié)點(diǎn)

孩子節(jié)點(diǎn)或子節(jié)點(diǎn)：一個節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)；如上圖：B是A的孩子節(jié)點(diǎn)

兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn)；如上圖：B、C是兄弟節(jié)點(diǎn)

樹的度：一棵樹中，最大的節(jié)點(diǎn)的度稱為樹的度；如上圖：樹的度為6

節(jié)點(diǎn)的層次：從根開始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推；

樹的高度或深度：樹中節(jié)點(diǎn)的最大層次；如上圖：樹的高度為4

堂兄弟節(jié)點(diǎn)：雙親在同一層的節(jié)點(diǎn)互為堂兄弟；如上圖：H、I互為兄弟節(jié)點(diǎn)

節(jié)點(diǎn)的祖先：從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn)；如上圖：A是所有節(jié)點(diǎn)的祖先

子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。如上圖：所有節(jié)點(diǎn)都是A的子孫

森林：由m（m>0）棵互不相交的樹的集合稱為森林；

1.3 樹的表示

孩子兄弟表示法

【樹】二叉樹堆與堆排序平衡(AVL)樹紅黑(RB)樹,數(shù)據(jù)結(jié)構(gòu),c++筆記,算法,數(shù)據(jù)結(jié)構(gòu)

typedef int DataType;
struct TreeNode {
	struct TreeNode* _firstChild1;  //第一個孩子結(jié)點(diǎn)
	struct Node* _pNextBrother;    //指向其下一個兄弟結(jié)點(diǎn)
	DataType _data;   //結(jié)點(diǎn)中的數(shù)據(jù)域
};

2 二叉樹

2.1 概念

一棵二叉樹是結(jié)點(diǎn)的一個有限集合，該集合：

或者為空

或者，由一個根節(jié)點(diǎn)加上兩顆別稱為左子樹和右子樹的二叉樹組成

注意：

二叉樹不存在度大于2的結(jié)點(diǎn)

二叉樹的子樹有左右之分，次序不能顛倒，因此二叉樹是有序樹

任意二叉樹都是由以下幾種情況復(fù)合而成

2. 2 特殊二叉樹

滿二叉樹：

每一層節(jié)點(diǎn)數(shù)達(dá)到最大值，即第k層結(jié)點(diǎn)總數(shù)為2^(k-1)。

通過等比數(shù)列運(yùn)算，滿二叉樹總結(jié)點(diǎn)數(shù)為2^k - 1。

完全二叉樹：

對于深度為k的完全二叉樹，則前k-1層是滿的

最后一層從左到右是連續(xù)的

2.3 二叉樹的性質(zhì)

若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第i層上最多有2^(i-1)個結(jié)點(diǎn).

若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點(diǎn)數(shù)是2^h - 1.

對任何一棵二叉樹，如果度為0其葉結(jié)點(diǎn)個數(shù)為n0，度為2的分支結(jié)點(diǎn)個數(shù)為n2 ,則有n₀＝ n₂＋1

若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個結(jié)點(diǎn)的滿二叉樹的深度，h = log₂(n+1)

對于具有n個結(jié)點(diǎn)的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點(diǎn)從0開始編號，則對
于序號為i的結(jié)點(diǎn)有：

2.4 二叉樹的存儲結(jié)構(gòu)

二叉樹一般有兩種結(jié)構(gòu)存儲，一種順序結(jié)構(gòu)，一種鏈?zhǔn)浇Y(jié)構(gòu)

順序結(jié)構(gòu)

適合滿二叉樹和完全二叉樹，其他二叉樹會造成空間浪費(fèi)。

鏈?zhǔn)浇Y(jié)構(gòu)

二叉鏈

typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{
    struct BinTreeNode* _pLeft; // 指向當(dāng)前節(jié)點(diǎn)左孩子
    struct BinTreeNode* _pRight; // 指向當(dāng)前節(jié)點(diǎn)右孩子
    BTDataType _data; // 當(dāng)前節(jié)點(diǎn)值域
};

三叉鏈

// 三叉鏈
struct BinaryTreeNode
{
    struct BinTreeNode* _pParent; // 指向當(dāng)前節(jié)點(diǎn)的雙親
    struct BinTreeNode* _pLeft; // 指向當(dāng)前節(jié)點(diǎn)左孩子
    struct BinTreeNode* _pRight; // 指向當(dāng)前節(jié)點(diǎn)右孩子
    BTDataType _data; // 當(dāng)前節(jié)點(diǎn)值域
};

3 堆 — 完全二叉樹的順序結(jié)構(gòu)實(shí)現(xiàn)

3.1 堆的概念

完全二叉樹

小根堆：樹中所有的父親都是小于等于孩子
大根堆：樹中所有的父親都是大于等于孩子

3.2 核心代碼

插入時向上調(diào)整

typedef int HPDataType;
typedef struct Heap {
	HPDataType* a;
	int size;
	int capacity;
}HP;
//向上調(diào)整
void AdjustUp(HPDataType* a, int child) {
	int parent = (child - 1) / 2;
	while (child > 0) {
        // if (a[child] > a[parent]) //大根堆
		if (a[child] < a[parent]) {
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}
void HeapPush(HP* php, HPDataType x) {
	assert(php);
	if (php->size == php->capacity) {
		//擴(kuò)容
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)*newcapacity);
		if (tmp == NULL) {
			printf("realloc fail\n");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size - 1);

}

刪除時向下調(diào)整

//向下調(diào)整
void AdjustDown(HPDataType* a, int size, int parent) {
	int child = parent * 2 + 1;
	while(child < size)
	{
        // if (child+1 < size && a[child + 1] > a[child])  //大根堆
		if (child+1 < size && a[child + 1] < a[child]) {
			++child;
		}
        // if (a[child] > a[parent])   //大根堆
		if (a[child] < a[parent]) {
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}else{
            break;
        }
	}

}
void HeapPop(HP* php) {
	assert(php);
	assert(php->size > 0);

	Swap(php->a[0], php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);

}

#include "Heap.h"

void Swap(HPDataType* p1, HPDataType* p2) {
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void HeapPrint(HP* php) {
	assert(php);
	for (int i = 0; i < php->size; ++i) {
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

void HeapInit(HP* php) {
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}

void HeapDestroy(HP* php) {
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size= php->capacity = 0;
}
//向上調(diào)整
void AdjustUp(HPDataType* a, int child) {
	int parent = (child - 1) / 2;
	while (child > 0) {
		if (a[child] < a[parent]) {
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}
void HeapPush(HP* php, HPDataType x) {
	assert(php);
	if (php->size == php->capacity) {
		//à?èY
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)*newcapacity);
		if (tmp == NULL) {
			printf("realloc fail\n");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size - 1);

}
//向下調(diào)整
void AdjustDown(HPDataType* a, int size, int parent) {
	int child = parent * 2 + 1;
	while(child < size)
	{
		if (child+1 < size && a[child + 1] < a[child]) {
			++child;
		}
		if (a[child] < a[parent]) {
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}
void HeapPop(HP* php) {
	assert(php);
	assert(php->size > 0);

	Swap(php->a[0], php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);

}
HPDataType HeapTop(HP* php) {
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

bool HeapEmpty(HP* php) {
	assert(php);
	return php->size == 0;
}
int HeapSize(HP* php) {
	assert(php);
	return php->size;
}
void Swap(HPDataType* p1, HPDataType* p2);
void HeapPrint(HP* php);
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);

3.3 堆應(yīng)用

1 堆排序

升序排序使用大根堆，降序排序使用小根堆

核心代碼

void HeapSort(int* a, int n) {
    
	// 向下調(diào)整建堆 O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i) {
		AdjustDown(a, n, i);
	}
	int end = n - 1;
    
	// O(N * logN) 
	while (end > 0){
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}

}

時間復(fù)雜度

O(N*logN)

2 TOP-K問題

求大數(shù)據(jù)量大的前K個最大或最小元素。

直接堆排序 O(N*logN)
當(dāng)數(shù)據(jù)量不是非常大時，建N個數(shù)的大堆，Top/Pop K次， O(N + logN*K)
當(dāng)N非常大(100億)，K比較小(100)
- 前K個數(shù)建立小堆
- 剩下的N-K個一次跟堆頂數(shù)據(jù)比較，如果比堆頂數(shù)據(jù)大，就替換堆頂數(shù)據(jù)進(jìn)隊(duì)
- 走完以后，堆里面的K個數(shù)，就是最大的前K個

核心代碼

//模擬實(shí)現(xiàn)
void PrintTopK(int* a, int n, int k)
{
	// 1. 建堆--用a中前k個元素建堆
	int* kMinHeap = (int*)malloc(sizeof(int) * k);
	assert(kMinHeap);
	for (int i = 0; i < k; ++i) {
		kMinHeap[i] = a[i];
	}
	for (int i = (k - 1 - 1) / 2; i >= 0; --i) {
		AdjustDown(kMinHeap, k, i);
	}
	// 2. 將剩余n-k個元素依次與堆頂元素交換，不滿則則替換
	for (int j = k; j < n; ++j) {
		if (a[j] > kMinHeap[0]) {
			kMinHeap[0] = a[j];
			AdjustDown(kMinHeap, k, 0);
		}
	}
	for (int i = 0; i < k; ++i) {
		printf("%d ", kMinHeap[i]);
	}
	printf("\n");
}
void TestTopk()
{
	int n = 10000;
	int* a = (int*)malloc(sizeof(int) * n);
	srand(time(0));
	for (int i = 0; i < n; ++i)
	{
		a[i] = rand() % 1000000;
	}
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[115] = 1000000 + 5;
	a[2335] = 1000000 + 6;
	a[9999] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;

	PrintTopK(a, n, 10);
}

4 二叉樹的鏈?zhǔn)酱鎯?/h2>
二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。通常的方法是鏈表中每個結(jié)點(diǎn)由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲地址。

鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈，三叉鏈比二叉鏈多一個parent指針。

4.1 二叉鏈結(jié)構(gòu)與初始化

typedef int BTDataType;
typedef struct BinaryTreeNode {
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;

BTNode* BuyNode(BTDataType x) {
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	assert(node);
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}

4.2 核心代碼

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include "Queue.h"
typedef int BTDataType;
typedef struct BinaryTreeNode {
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;

BTNode* BuyNode(BTDataType x) {
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	assert(node);
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	return node1;
}
// 前序遍歷 分治
void PreOrder(BTNode* root) {
	if (root == NULL) {
		printf("# ");
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}
// 中序遍歷
void InOrder(BTNode* root) {
	if (root == NULL) {
		printf("# ");
		return;
	}

	PreOrder(root->left);
	printf("%d ", root->data);
	PreOrder(root->right);
}

// 后序遍歷
void PostOrder(BTNode* root) {
	if (root == NULL) {
		printf("# ");
		return;
	}

	PreOrder(root->left);
	PreOrder(root->right);
	printf("%d ", root->data);

}
int count = 0;
void TreeSize(BTNode* root) {
	if (root == NULL) {
		return;
	}
	++count;
	TreeSize(root->left);
	TreeSize(root->right);
}
// 分而治之
int TreeSize2(BTNode* root) {
	return root == NULL ? 0 :
		TreeSize2(root->left) + TreeSize2(root->right) + 1;
}

int TreeLeafSize2(BTNode* root) {
	if (root == NULL)
		return 0;
	else if(root->left == NULL && root->right == NULL){
		return 1;
	}
	else {
		return TreeLeafSize2(root->left) + TreeLeafSize2(root->right);
	}
}
// 求第K層結(jié)點(diǎn)數(shù)
int TreeKLevel(BTNode* root, int k) {
	assert(k >= 1);
	if (root == NULL) {
		return 0;
	}
	if (k == 1) {
		return 1;
	}
	return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}
// 求二叉樹深度
int  TreePath(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	else {
		int leftDepth = TreePath(root->left);
		int rightDepth = TreePath(root->right);
		return (leftDepth > rightDepth) ? (leftDepth + 1) : (rightDepth + 1);
	}
}

// 二叉樹查找值為x的結(jié)點(diǎn)
BTNode* TreeFind(BTNode* root, BTDataType x) {
	if (root == NULL)
		return NULL;
	if (root->data == x) {
		return root;
	}
	BTNode* ret1 = TreeFind(root->left, x);
	if (ret1)
		return ret1;

	BTNode* ret2 = TreeFind(root->left, x);
	if (ret2)
		return ret2;

	return NULL;
}

void TreeDestroy(BTNode* root) {
	if (root == NULL) {
		return;
	}
	TreeDestroy(root->left);
	TreeDestroy(root->right);
	printf("%p:%d\n", root, root->data);
	free(root);

}

//層序遍歷 一種廣度優(yōu)先遍歷 借助隊(duì)列
void LevelOrder(BTNode* root) {
	Queue q;
	QueueInit(&q);
	if (root) {
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		printf("%d ", front->data);
		QueuePop(&q);
		if (front->left) {
			QueuePush(&q, front->left);
		}
		if (front->right) {
			QueuePush(&q, front->right);
		}
	}
	printf("\n");
	QueueDestroy(&q);
}

// 判斷二叉樹是否是完全二叉樹 借助隊(duì)列
bool TreeComplete(BTNode* root) {
	Queue q;
	QueueInit(&q);
	if (root) {
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front) {
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
		else {
			//遇到空以后，則跳出層序遍歷
			break;
		}
	}
	//1、如果后面全是空，則是完全二叉樹
	//2、如果空后面還有非空，則不是完全二叉樹
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front) {
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

int main() {
	BTNode* root = CreatBinaryTree();
	PreOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PostOrder(root);
	printf("\n");
	printf("層序遍歷：");
	LevelOrder(root);

	TreeSize(root);
	printf("TreeSize:%d\n", count);

	printf("TreeSize2:%d\n", TreeSize2(root));
	printf("leafCount:%d\n", TreeLeafSize2(root));
	printf("Tree2Level: %d\n", TreeKLevel(root, 2));
	printf("deep：%d\n", TreePath(root));

	printf("Is TreeComplete: %d\n", TreeComplete(root)); 
	TreeDestroy(root);
	root = NULL;
	return 0;
}

【樹】二叉樹堆與堆排序平衡(AVL)樹紅黑(RB)樹,數(shù)據(jù)結(jié)構(gòu),c++筆記,算法,數(shù)據(jù)結(jié)構(gòu)

5 二叉搜索樹

5.1 概念

二叉搜索樹又稱二叉排序樹，它是一棵空樹或者具有以下性質(zhì)的非空二叉樹：

若左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值
若右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值
搜索二叉樹的左右子樹也分別為二叉搜索樹

【樹】二叉樹堆與堆排序平衡(AVL)樹紅黑(RB)樹,數(shù)據(jù)結(jié)構(gòu),c++筆記,算法,數(shù)據(jù)結(jié)構(gòu)

因其以上特性，使用搜索二叉樹查找時，最多查找次數(shù)等于其高度。

對二叉搜索樹進(jìn)行中序遍歷，可得到一個升序排序的數(shù)值。

5.2 結(jié)構(gòu)與代碼實(shí)現(xiàn)

#pragma once
#include <iostream>
using namespace std;
template <class K>
struct BSTreeNode {

	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;

	BSTreeNode(const K& key)
		: _left(nullptr)
		, _right(nullptr)
		, _key(key)
	{}
};

//class BinarySearchTree {
template<class K>
class BSTree{
	typedef BSTreeNode<K> Node;
public:
	bool Insert(const K& key) {
		if (_root == nullptr) {
			_root = new Node(key);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key) {
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else {
				return false;
			}
		}

		cur = new Node(key);
		if (parent->_key < key) {
			parent->_right = cur;
		}
		else {
			parent->_left = cur;
		}
		return true;
	}
	bool Find(const K& key) {
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key) {
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else {
				return true;
			}
		}
		return false;
	}
	bool Erase(const K& key) { 
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key) {
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key) {
				parent = cur;
				cur = cur->_left;
			}
			else {
				// 開始刪除
				//1. 左為空
				//2. 右為空
				//3. 左右都不為空
				if (cur->_left == nullptr) {
					if (cur == _root) {
						_root = cur->_right;
					}
					else {
						if (cur == parent->_left) {
							parent->_left = cur->_right;
						}
						else {
							parent->_right = cur->_right;
						}
					}
					delete cur;
					cur = nullptr;
				}
				else if (cur->_right == nullptr) {
					if (_root == cur) {
						_root = cur->_left;
					}
					else {
						if (cur == parent->_left) {
							parent->_left = cur->_left;
						}
						else {
							parent->_right = cur->_left;
						}
					}
					delete cur;
					cur = nullptr;
				}
				else {
					//替換法刪除
					Node* minParent = cur;
					Node* min = cur->_right;
					while (min->_left)
					{
						minParent = min;
						min = min->_left;
					}
					//cur->_key = min->_key;
					swap(cur->_key, min->_key);
					if (minParent->_left == min)
					{
						minParent->_left = min->_right;
					}
					else {
						minParent->_right = min->_right;
					}
					delete min;
				}
				return true;
			}
		}
		return false;
	}
	void InOrder() {
		_InOrder(_root);
		cout << endl;
	}

/*---------------------利用遞歸實(shí)現(xiàn)操作-------------------------------*/
	bool FindR(const K& key) {
		return _FindR(_root, key);
	}
	bool InsertR(const K& key) {
		return _InsertR(_root, key);
	}
	bool EraseR(const K& key) {
		return _EraseR(_root, key);
	}

	~BSTree() {
		_Destory(_root);
	}
	// c++11的用法，強(qiáng)制編譯器生成默認(rèn)的構(gòu)造
	BSTree() = default;
	BSTree(const BSTree<K>& t) {
		_root = _Copy(t._root);
	}
	BSTree<K>& operator=(BSTree<K> t) {
		swap(_root, t._root);
		return *this;
	}
private:
	Node* _Copy(Node* root) {
		if (root == nullptr) {
			return nullptr;
		}
		Node* copyRoot = new Node(root->_key);
		copyRoot->_left = _Copy(root->_left);
		copyRoot->_right = _Copy(root->_right);
		return copyRoot;
	}
	void _Destory(Node*& root) {
		if (root == nullptr) {
			return;
		}
		_Destory(root->_left);
		_Destory(root->_right);
		delete root;
		root = nullptr;
	}
	bool _EraseR(Node*& root, const K& key) {
		if (root == nullptr) {
			return false;
		}
		if (root->_key < key) {
			return _EraseR(root->_right, key);
		}
		else if (root->_key > key) {
			return _EraseR(root->_left, key);
		}
		else {
			Node* del = root;
			if (root->_left == nullptr) {
				root = root->_right;
			}else if (root->_right == nullptr) {
				root = root->_left;
			}
			else {
				// 找右樹的最左節(jié)點(diǎn)
				Node* min = root->_right;
				while (min->_left) {
					min = min->_left;
				}
				swap(root->_key, min->_key);
				return _EraseR(root->_right, key);
			}
			delete del;
			return true;
		}
	}
	bool _InsertR(Node* &root, const K& key) {
		if (root == nullptr) {
			root = new Node(key);
			return true;
		}
		if (root->_key < key) {
			return _InsertR(root->_right, key);
		}
		else if (root->_key > key) {
			return _InsertR(root->_left, key);
		}
		else {
			return false;
		}
	}
	bool _FindR(Node* root, const K& key) {
		if (root == nullptr) {
			return false;
		}
		if (root->_key < key) {
			return _FindR(root->_right);
		}
		else if (root->_key > key) {
			return _FindR(root->_left, key);
		}
		else {
			return true;
		}
	}
	void _InOrder(Node* root) {
		if (root == nullptr) {
			return;
		}
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
private:
	Node* _root = nullptr;

};
void TestBSTree1() {
	BSTree<int> t;
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	for (auto e : a) {
		t.Insert(e);
	}
	// 排序+去重
	t.InOrder();

	t.EraseR(3);
	t.InOrder();

	t.EraseR(8);
	t.InOrder();

	for (auto e : a) {
		t.EraseR(e);
		t.InOrder();
	}
}
void TestBSTree3() {
	BSTree<int> t;
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	for (auto e : a) { 
		t.InsertR(e);
	}
	BSTree<int> copy = t;
	copy.InOrder();
	t.InOrder();

	BSTree<int> t1;
	t1.Insert(2);
	t1.Insert(1);
	t1.Insert(3);

	copy = t1;
	copy.InOrder();
	t1.InOrder();
}

5.3 復(fù)雜度與缺陷

二叉搜索樹的增刪查的時間復(fù)雜度為O(h)，h為樹的高度。當(dāng)key值的插入接近有序時，h最壞情況下等于N。此時增刪查時間復(fù)雜度過高。

平衡樹（AVL樹）改善了此處的缺陷。

6 AVL樹

6.1 概念

當(dāng)向二叉搜索樹中插入新結(jié)點(diǎn)后，如果能保證每個結(jié)點(diǎn)的左右子樹高度之差的絕對值不超過1(需要對樹中的結(jié)點(diǎn)進(jìn)行調(diào)整)，即可降低樹的高度，從而減少平均搜索長度。

AVL樹，或者是顆空樹，或者是具有下列性質(zhì)的二叉搜索樹：

左右子樹都是AVL樹
左右子樹高度之差（簡稱平衡因子）的絕對值不超過1（-1/0/1)

【樹】二叉樹堆與堆排序平衡(AVL)樹紅黑(RB)樹,數(shù)據(jù)結(jié)構(gòu),c++筆記,算法,數(shù)據(jù)結(jié)構(gòu)

6.2 旋轉(zhuǎn)核心代碼與思想

單旋：

【樹】二叉樹堆與堆排序平衡(AVL)樹紅黑(RB)樹,數(shù)據(jù)結(jié)構(gòu),c++筆記,算法,數(shù)據(jù)結(jié)構(gòu)

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

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

    Node* ppNode = parent->_parent;

    subR->_left = parent;
    parent->_parent = subR;

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

        subR->_parent = ppNode;
    }

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

【樹】二叉樹堆與堆排序平衡(AVL)樹紅黑(RB)樹,數(shù)據(jù)結(jié)構(gòu),c++筆記,算法,數(shù)據(jù)結(jié)構(gòu)

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

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

    Node* ppNode = parent->_parent;

    subL->_right = parent;
    parent->_parent = subL;

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

        subL->_parent = ppNode;
    }

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

左右雙旋：

b插入新增，引發(fā)雙旋

【樹】二叉樹堆與堆排序平衡(AVL)樹紅黑(RB)樹,數(shù)據(jù)結(jié)構(gòu),c++筆記,算法,數(shù)據(jù)結(jié)構(gòu)

c插入新增，引發(fā)雙旋

【樹】二叉樹堆與堆排序平衡(AVL)樹紅黑(RB)樹,數(shù)據(jù)結(jié)構(gòu),c++筆記,算法,數(shù)據(jù)結(jié)構(gòu)

a/b/c/d是空樹，60是新增，引發(fā)雙旋

【樹】二叉樹堆與堆排序平衡(AVL)樹紅黑(RB)樹,數(shù)據(jù)結(jié)構(gòu),c++筆記,算法,數(shù)據(jù)結(jié)構(gòu)

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

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

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

        parent->_bf = 1;
        subL->_bf = 0;
    }
    else if (bf == 0)
    {
        parent->_bf = 0;
        subL->_bf = 0;
    }
    else
    {
        assert(false);
    }
}
//右左雙旋，與左右雙旋相似，圖略
void RotateRL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;

    int bf = subRL->_bf;

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

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

旋轉(zhuǎn)的價值和意義：

平衡
降高度（高度恢復(fù)到插入之前的樣子）

6.3 插入

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;

    // 控制平衡
    // 1、更新平衡因子
    while (parent)
    {
        if (cur == parent->_right)
        {
            parent->_bf++;
        }
        else
        {
            parent->_bf--;
        }

        if (parent->_bf == 0)
        {
            break;
        }
        else if (abs(parent->_bf) == 1)
        {
            parent = parent->_parent;
            cur = cur->_parent;
        }
        else if (abs(parent->_bf) == 2)
        {
            // 說明parent所在子樹已經(jīng)不平衡了，需要旋轉(zhuǎn)處理
            if (parent->_bf == 2 && cur->_bf == 1)
            {
                RotateL(parent);
            }
            else if ((parent->_bf == -2 && cur->_bf == -1))
            {
                RotateR(parent);
            }
            else if (parent->_bf == -2 && cur->_bf == 1)
            {
                RotateLR(parent);
            }
            else if (parent->_bf == 2 && cur->_bf == -1)
            {
                RotateRL(parent);
            }
            else
            {
                assert(false);
            }

            break;
        }
        else
        {
            assert(false);
        }
    }

    return true;
}

6.4 驗(yàn)證平衡

bool _IsBanlance(Node* root) {
    if (root == nullptr) {
        return true;
    }
    int leftHT = Height(root->_left);
    int rightHT = Height(root->_right);
    int diff = rightHT - leftHT;

    return abs(diff) < 2
        && _IsBanlance(root->_left)
        && _IsBanlance(root->_right);
}
int Height(Node* root) {
    if (root == nullptr)
        return 0;
    return max(Height(root->_left), Height(root->_right)) + 1;
}

7 紅黑樹

7.1 紅黑樹的概念

紅黑樹，是一種二叉搜索樹，但在每個結(jié)點(diǎn)上增加一個存儲位表示結(jié)點(diǎn)的顏色，可以是Red或Black。通過對任何一條從根到葉子的路徑上各個結(jié)點(diǎn)著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，即最長路徑不超過最短路徑的2倍，因而是接近平衡的。

效果：相對而言，插入同樣的數(shù)據(jù)，AVL樹旋轉(zhuǎn)更多，紅黑樹旋轉(zhuǎn)更少

【樹】二叉樹堆與堆排序平衡(AVL)樹紅黑(RB)樹,數(shù)據(jù)結(jié)構(gòu),c++筆記,算法,數(shù)據(jù)結(jié)構(gòu)

7.2 紅黑樹的性質(zhì)

每個節(jié)點(diǎn)不是紅色就是黑色
根節(jié)點(diǎn)是黑色的
如果一個節(jié)點(diǎn)是紅色的，則它的兩個孩子節(jié)點(diǎn)是黑色的（樹中沒有連續(xù)的紅色節(jié)點(diǎn)）
對于每個節(jié)點(diǎn)，從該節(jié)點(diǎn)到其所有后代節(jié)點(diǎn)的簡單路徑上，均包含相同數(shù)目的黑色節(jié)點(diǎn)（每條路徑黑色節(jié)點(diǎn)數(shù)量相等）
每個葉子節(jié)點(diǎn)都是黑色的（此處的葉子節(jié)點(diǎn)指的是空節(jié)點(diǎn)）

由以上性質(zhì)可知，一棵樹內(nèi)極限最短為全黑，極限最長為一黑一紅，因此最長路徑中節(jié)點(diǎn)個數(shù)不會超過最短路徑節(jié)點(diǎn)個數(shù)的兩倍。

7.3 插入

插入思想

cur->_parent為黑，插入成功
cur->_parent為紅，分情況進(jìn)行調(diào)整：
- 情況一：cur為紅，p為紅，g為黑，u存在且為紅：
  
  調(diào)整后，若g為根節(jié)點(diǎn)，此時只需將g變?yōu)楹谏纯烧{(diào)整完畢。
  
  調(diào)整后，若g不為根節(jié)點(diǎn)，且g的父結(jié)點(diǎn)為黑色則調(diào)整完畢；若g的父結(jié)點(diǎn)為紅色，則將g作為當(dāng)前節(jié)點(diǎn)繼續(xù)根據(jù)情況調(diào)整。
- 情況二：cur為紅，p為紅，g為黑，u不存在/u存在且為黑
  
  cur和p都是他們的父結(jié)點(diǎn)的左孩子，對g進(jìn)行右單旋，p變黑，g變紅，則調(diào)整完畢：
  
  cur和p都是他們的父結(jié)點(diǎn)的右孩子，對g進(jìn)行左單旋，p變黑，g變紅，則調(diào)整完畢：
- 情況三：cur為紅，p為紅，g為黑，u不存在/u存在且為黑
  
  p為g的左孩子，cur為p的右孩子，則針對p做左單旋，則可轉(zhuǎn)為情況二繼續(xù)調(diào)整：
  
  p為g的右孩子，cur為p的左孩子，則針對p做右單旋，則可轉(zhuǎn)為情況二繼續(xù)調(diào)整：
  
  則情況三中，無論是上述哪兩種小情況，都需要進(jìn)行一次單旋后轉(zhuǎn)為情況二繼續(xù)調(diào)整，那么情況三總的調(diào)整也就是雙旋后進(jìn)行變色（單旋+情況二的單旋+變色）。

紅黑樹的的關(guān)鍵是看叔叔。

核心代碼

bool Insert(const pair<K, V>& kv)
{
    if (_root == nullptr)
    {
        _root = new Node(kv);
        _root->_col = BLACK;
        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);
    cur->_col = RED;
    if (parent->_kv.first < kv.first)
    {
        parent->_right = cur;
    }
    else
    {
        parent->_left = cur;
    }

    cur->_parent = parent;

    while (parent && parent->_col == RED)
    {
        Node* grandfather = parent->_parent;
        assert(grandfather);
        assert(grandfather->_col == BLACK);
        // 關(guān)鍵看叔叔
        if (parent == grandfather->_left)
        {
            Node* uncle = grandfather->_right;
            // 情況一：uncle存在且為紅，變色+繼續(xù)往上處理
            if (uncle && uncle->_col == RED)
            {
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                // 繼續(xù)將grandfather作為current進(jìn)行處理
                cur = grandfather;
                parent = cur->_parent;
            }
            // 情況二+三：uncle不存在或uncle存在為黑色
            else
            {
                // 情況二:單旋+變色
                //     g
                //   p   u
                // c
                if (cur == parent->_left)
                {
                    RotateR(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                }
                else
                {
                    // 情況三:左單旋+右單旋+變色
                    //     g
                    //   p   u
                    //     c
                    RotateL(parent);
                    RotateR(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        }
        else
        {
            Node* uncle = grandfather->_left;
            // 情況一：叔叔是紅色
            if (uncle && uncle->_col == RED)
            {
                parent->_col = uncle->_col = BLACK;
                grandfather->_col = RED;
                // 繼續(xù)將grandfather作為current進(jìn)行處理
                cur = grandfather;
                parent = cur->_parent;
            }
            // 情況二+三：uncle不存在或uncle存在為黑色
            else
            {
                // 情況二:單旋+變色
                //     g
                //   u   p
                //         c
                if (cur == parent->_right)
                {
                    RotateL(grandfather);
                    parent->_col = BLACK;
                    grandfather->_col = RED;
                }
                else
                {
                    // 情況三:右單旋+左單旋+變色
                    //     g
                    //   u   p
                    //     c
                    RotateR(parent);
                    RotateL(grandfather);
                    cur->_col = BLACK;
                    grandfather->_col = RED;
                }
                break;
            }
        }
    }
    _root->_col = BLACK;
    return true;
}

7.4 驗(yàn)證紅黑樹

紅黑樹的檢測分為兩步：文章來源地址http://www.zghlxwxcb.cn/news/detail-626293.html

檢測其是否滿足二叉搜索樹(中序遍歷是否為有序序列)
檢測其是否滿足紅黑樹的性質(zhì)

bool IsBanlance()
{
    if (_root == nullptr)
    {
        return true;
    }
    if (_root->_col == RED)
    {
        cout << "根節(jié)點(diǎn)不是黑色" << endl;
        return false;
    }
    // 黑色節(jié)點(diǎn)數(shù)量基準(zhǔn)值
    int benchmark = 0;
    Node* cur = _root;
    while (cur)
    {
        if (cur->_col == BLACK) {
            ++benchmark;
        }
        cur = cur->_left;
    }
    return PrevCheck(_root, 0, benchmark);
}
bool PrevCheck(Node* root, int blackNum, int benchmark)
{
    if (root == nullptr)
    {
        /*cout << blackNum << endl;
            return;*/
        if (blackNum != benchmark)
        {
            cout << "某條黑色節(jié)點(diǎn)的數(shù)量不相等" << endl;
            return false;
        }
        else {
            return true;
        }
    }
    if (root->_col == RED && root->_parent->_col == RED)
    {
        cout << "存在紅色的連續(xù)節(jié)點(diǎn)" << endl;
        return false;
    }
    if (root->_col == BLACK)
    {
        ++blackNum;
    }
    return PrevCheck(root->_left, blackNum, benchmark)
        && PrevCheck(root->_right, blackNum, benchmark);
}

到了這里，關(guān)于【樹】二叉樹堆與堆排序平衡(AVL)樹紅黑(RB)樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請點(diǎn)擊違法舉報進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

【數(shù)據(jù)結(jié)構(gòu)】：二叉樹與堆排序的實(shí)現(xiàn)
樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n=0）個有限結(jié)點(diǎn)組成一個具有層次關(guān)系的集合把它叫做樹是因?yàn)樗雌饋硐褚豢玫箳斓臉?，也就是說它是根朝上，而葉朝下的有一個特殊的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，根節(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn) 除根節(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成M(M0)個互不相交的集合T1、
2024年02月08日
瀏覽(19)
數(shù)據(jù)結(jié)構(gòu)——常見二叉樹的分類（完全二叉樹、滿二叉樹、平衡二叉樹、二叉搜索樹、紅黑樹）
專業(yè)術(shù)語中文描述 Root 根節(jié)點(diǎn) 一棵樹的頂點(diǎn) Child 孩子結(jié)點(diǎn) 一個結(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該結(jié)點(diǎn)的子節(jié)點(diǎn) Leaf 葉子結(jié)點(diǎn) 沒有孩子的節(jié)點(diǎn) Degree 度一個節(jié)點(diǎn)包含子樹的數(shù)量 Edge 邊一個節(jié)點(diǎn)與另外一個節(jié)點(diǎn)的連接 Depth 深度根節(jié)點(diǎn)到這個節(jié)點(diǎn)經(jīng)過邊的數(shù)量 Height 節(jié)點(diǎn)高度從
2024年02月03日
瀏覽(29)
數(shù)據(jù)結(jié)構(gòu)：堆與堆排序
目錄堆的定義：堆的實(shí)現(xiàn)：堆的元素插入：堆元素刪除：堆初始化與銷毀：堆排序：堆的定義：堆是一種完全二叉樹，完全二叉樹定義如下：一棵深度為k的有n個結(jié)點(diǎn)的二叉樹，對樹中的結(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號，如果編號為i（1≤i≤n）的結(jié)點(diǎn)與滿二
2024年01月23日
瀏覽(17)
數(shù)據(jù)結(jié)構(gòu)-各種樹（二叉樹、二叉查找樹、平衡二叉樹、紅黑樹、B樹、B+樹）
概念：二叉樹（binary tree）是指樹中節(jié)點(diǎn)的度不大于2的有序樹，它是一種最簡單且最重要的樹。二叉樹的遞歸定義為：二叉樹是一棵空樹，或者是一棵由一個根節(jié)點(diǎn)和兩棵互不相交的，分別稱作根的左子樹和右子樹組成的非空樹；左子樹和右子樹又同樣都是二叉樹特點(diǎn)：每個
2024年02月09日
瀏覽(18)
Java常見的數(shù)據(jù)結(jié)構(gòu)：棧、隊(duì)列、數(shù)組、鏈表、二叉樹、二叉查找樹、平衡二叉樹、紅黑樹
數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)底層存儲、組織數(shù)據(jù)的方式。是指數(shù)據(jù)相互之間是以什么方式排列在一起的。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲效率棧隊(duì)列數(shù)組鏈表二叉樹二叉查找樹平衡二叉樹紅黑樹... 后進(jìn)先出，先進(jìn)后出數(shù)據(jù)進(jìn)入棧模型的過程稱為
2024年02月07日
瀏覽(29)
數(shù)據(jù)結(jié)構(gòu)07：查找[C++][平衡二叉排序樹AVL]
圖源：文心一言考研筆記整理1w+字，小白友好、代碼可跑，請小伙伴放心食用~~???? 第1版：查資料、寫B(tài)UG、畫導(dǎo)圖、畫配圖~???? 參考用書：王道考研《2024年數(shù)據(jù)結(jié)構(gòu)考研復(fù)習(xí)指導(dǎo)》參考用書配套視頻： 7.3_2 平衡二叉樹_嗶哩嗶哩_bilibili 特別感謝： ?Chat GPT老師、文心
2024年02月11日
瀏覽(46)
【數(shù)據(jù)結(jié)構(gòu)與算法】堆與堆排序
堆是一種數(shù)據(jù)結(jié)構(gòu)，首先它總是一顆完全二叉樹( 因?yàn)槎堰m合表示完全二叉樹 )，在邏輯上堆是一顆完全二叉樹，真正實(shí)現(xiàn)上是使用數(shù)組來實(shí)現(xiàn)的。根據(jù)不同的規(guī)則( 任意根節(jié)點(diǎn)比左右孩子大或者小 )區(qū)分出大根堆和小根堆。上圖就是一個大根堆的演示，小根堆則相反。堆的底
2023年04月08日
瀏覽(28)
數(shù)據(jù)結(jié)構(gòu)之進(jìn)階二叉樹（二叉搜索樹和AVL樹、紅黑樹的實(shí)現(xiàn)）超詳細(xì)解析，附實(shí)操圖和搜索二叉樹的實(shí)現(xiàn)過程圖
緒論? “生命有如鐵砧，愈被敲打，愈能發(fā)出火花?！だ浴保槐菊轮饕菙?shù)據(jù)結(jié)構(gòu) 二叉樹的進(jìn)階知識，若之前沒學(xué)過二叉樹建議看看這篇文章一篇掌握二叉樹，本章的知識從淺到深的對搜索二叉樹的使用進(jìn)行了介紹和對其底層邏輯的實(shí)現(xiàn)進(jìn)行了講解，希望能對你有所
2024年02月04日
瀏覽(28)
【數(shù)據(jù)結(jié)構(gòu)】二叉排序樹——平衡二叉樹的調(diào)整
參考視頻：懶貓老師-數(shù)據(jù)結(jié)構(gòu)-(59)平衡二叉樹【互動視頻】（1）什么是平衡二叉樹平衡二叉樹（Balanced Binary Tree）是一種特殊的二叉查找樹，它的目的是保持樹的高度盡量平衡，以保證查找、插入、刪除等操作的時間復(fù)雜度為 O(log n)。常見的平衡二叉樹算法包括 AVL 樹、紅
2024年02月04日
瀏覽(29)
【數(shù)據(jù)結(jié)構(gòu)】7.平衡搜索樹（AVL樹和紅黑樹）
對于普通的搜索樹，如果一直插入比第一個元素小的元素，它會退化成一個無限向左下角眼神的單鏈表，使得時間復(fù)雜度退化為O(n)。如果我們在插入時保持樹的結(jié)構(gòu)是平衡的，則可以保證查找、插入和刪除的時間復(fù)雜度有對數(shù)級的時間性能，下面講到的AVL樹和紅黑樹都是平衡
2024年02月08日
瀏覽(31)