数据结构:第7章:查找(复习)

目录

顺序查找:

折半查找:

二叉排序树:

4. (程序题)

平衡二叉树: 


顺序查找:

ASL=\frac{1}{n}\sum i=\frac{1+n}{2}

折半查找:

ASL=\frac{1}{n}\sum_{i=1}^{h}j*2^{j-1}=\frac{n+1}{n}log2(n+1)-1

这里 j 表示 二叉查找树的第 j 层

二叉排序树:

二叉排序树(Binary Search Tree,BST)是一种特殊的二叉树,定义:

  1. 对于二叉排序树的每个节点,其左子树的所有节点的值都小于该节点的值。
  2. 对于二叉排序树的每个节点,其右子树的所有节点的值都大于该节点的值。
  3. 对于二叉排序树的每个节点,其左右子树也分别是二叉排序树。

可以发现二叉排序树的定义时递归定义。

这些性质保证了对于二叉排序树中的任意节点,其左子树的节点值小于它,右子树的节点值大于它,从而形成了一种有序的结构。

二叉排序树的有序性质使得在其中进行查找、插入和删除等操作时具有较高的效率。对于给定的值,可以通过比较节点的值,按照二叉排序树的性质在树中快速定位所需的节点。

二叉排序树的难点在于删除树中的某个值。删除某个键值为 key 的节点时,有三中情况要考虑:

1.该节点 r 的左孩子为空:r=r->lch;

2.该节点 r 的右孩子为空:l=l->rch;

3.该节点的左右孩子均不位空:选择左孩子中 key 值最大的节点替换 r;

4. (程序题)

二叉排序树插入、删除

键盘输入若干整型数据,以0做结束,利用二叉排序树的插入算法创建二叉排序树,并中序遍历该二叉树。之后输入一个整数x,在二叉排序树中查找,若找到则输出“该数存在”,否则输出“该数不存在”;再输入一个要删除的一定存在的整数y,完成在该二叉树中删除y的操作,并输出删除y后的二叉树中序遍历的结果。

输出数据之间用一个空格分隔。

输入:
1 5 4 2 3 6 8 7 9 11 14 13 12 16 19 0
输出:
1 2 3 4 5 6 7 8 9 11 12 13 14 16 19
输入:
19
输出:
该数存在
输入:
14
输出:
1 2 3 4 5 6 7 8 9 11 12 13 16 19

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
typedef long long LL;

typedef struct Info {
	int key;
}Info;

typedef struct Node {
	Info data;
	struct Node* lch;
	struct Node* rch;
}Node,*Tree;

void print(Tree& r) {
	if (r == NULL)return;
	print(r->lch);
	cout << r->data.key << " ";
	print(r->rch);
}

void Insert(Tree& r, int key) {
	if (r == NULL) {
		Node* p = new Node;
		p->data.key = key;
		p->rch = p->lch = NULL;
		r = p;
	}
	else if(r->data.key<key) {
		Insert(r->rch, key);
	}
	else {
		Insert(r->lch, key);
	}
}

void build(Tree& r) {
	int in;
	cin >> in;
	while (in) {
		Insert(r, in);
		cin >> in;
	}
}

int search(Tree& r, int key) {
	if (r == NULL)return 0;
	if (r->data.key == key) {
		return 1;
	}
	if (r->data.key < key) {
		if (search(r->rch, key))return 1;
	}
	else {
		if (search(r->lch, key))return 1;
	}
	return 0;
}

int del(Tree& r, int key) {
	if (r == NULL)return 0;
	if (r->data.key == key) {
		if (r->lch == NULL) {
			r =r->rch;
		}
		else if (r->rch == NULL) {
			r =r->lch;
		}
		else {
			//cout << r->data.key << endl;
			Node* p = r->lch;
			Node* fa = r;
			
			while (p->rch != NULL) {
				fa = p;
				p = p->rch;
			}
			Node* t = r;
			if (fa != r)
				fa->rch = p->lch;
			if (r->lch != p)
				p->lch = r->lch;
			p->rch = r->rch;
			//cout << p->data.key << endl;
			r = p;
			delete t;
		}
		return 1;
	}
	if (r->data.key < key) {
		if (del(r->rch, key))return 1;
	}
	else {
		if (del(r->lch, key))return 1;
	}
	return 0;
}

int main() {
	Node* root = NULL;
	build(root);
	print(root);
	int in;
	cin >> in;
	if (search(root, in)) {
		cout << "该数存在" << endl;
	}
	else {
		cout << "该数不存在" << endl;
	}
	cin >> in;
	del(root, in);
	print(root);
	return 0;
}

用例1:

输入

1 5 4 2 3 6 8 7 9 11 14 13 12 16 19 0 19 14

输出

1 2 3 4 5 6 7 8 9 11 12 13 14 16 19 该数存在 1 2 3 4 5 6 7 8 9 11 12 13 16 19

用例2:

输入

10 9 8 7 11 12 13 14 0 14 8

输出

7 8 9 10 11 12 13 14 该数存在 7 9 10 11 12 13 14

用例3:

输入

23 45 67 21 12 15 9 10 55 0 19 9

输出

9 10 12 15 21 23 45 55 67 该数不存在 10 12 15 21 23 45 55 67

平衡二叉树: 

平衡二叉树的定义


平衡二叉排序树查找算法的性能取决于二叉树的结构,而二叉树的形状则取决于其数据集。
如果数据呈有序排列,则二叉排序树是线性的,查找的时间复杂度为O(n);反之,如果二叉排序
树的结构合理,则查找速度较快,查找的时间复杂度为O(logn)。事实上,树的高度越小,查找
速度越快。因此,希望二叉树的高度尽可能小。本节将讨论一种特殊类型的二叉排序树,称为平
衡二叉树
(Balanced Binary Tree 或 Height-Balanced Tree),因由前苏联数学家 Adelson-Velskii 和
Landis 提出,所以又称AVL树。


平衡二叉树或者是空树,或者是具有如下特征的二叉排序树:
(1)左子树和右子树的深度之差的绝对值不超过1;
(2)左子树和右子树也是平衡二叉树。


若将二叉树上结点的平衡因子(Balance Factor,BF)定义为该结点左子树和右子树的深度之
差,则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡
因子的绝对值大于1,则该二叉树就是不平衡的。图7.11(a)所示为两棵平衡二叉树,而图 7.11
(b)所示为两棵不平衡的二叉树,结点中的值为该结点的平衡因子。

平衡二叉树的调整(重难点)

LL型调整操作由于在A左子树根结点的左子树上插入结点,A的平衡因子由1增至2,致使以A为根的子树失去平衡,则需进行一次向右的顺时针旋转操作 

RR 型调整操作:当在 A 的右子树的右子树上插入结点时,A 的平衡因子由 -1 变为 -2,导致以 A 为根结点的子树失去平衡。此时,需要进行一次向左的逆时针旋转操作,将 A 的右子树作为其左子树的右子树,并将 A 作为其左子树的根结点。

LR型调整操作:由于在A的左子树根结点的右子树上插入结点, A的平衡因子由1增至2,致使以A为根结点的子树失去平衡,则需进行两次旋转操作。第一次对B及其右子树进行递时针旋转,C转上去成为B的根,这时变成了LL型,所以第二次进行LL型的顺时针旋转即可恢复平衡。如果C原来有左子树,则调整C的左子树为B的右子树,


RL型调整操作:由于在A的右子树根结点的左子树上插入结点,A的平衡因子由-1变为-2,致使以A 为根结点的子树失去平衡,则旋转方法和LR型相对称,也需进行两次旋转,先顺时针右旋,再逆时针左旋。

左,右旋转调整代码:

 void Turnleft(TreeNode*& r) {
        TreeNode* A = r;
        TreeNode* B = r->right;
        A->right = B->left;
        B->left = A;
        r = B;
    }

    void Turnright(TreeNode*& r) {
        TreeNode* A = r;
        TreeNode* B = r->left;
        A->left = B->right;
        B->right = A;
        r = B;
    }

 判断不平衡类型类型的代码:

 

void fun1(vector<int>& g, TreeNode* r) {
        if ( r == NULL||(r->left==NULL&&r->right==NULL))return;
        if (mp[r->left] == mp[r->right])return;
        g.push_back(mp[r->left] - mp[r->right]);
        fun1(g, r->left);
        fun1(g, r->right);
    }

string check(TreeNode* root) {
        vector<int>g;
        fun1(g, root);
        if (g[0] == 2&&g[1]==1)return "LL";
        else if (g[0] == 2&&g[1]==-1)return "LR";
        else {
            if (g[0] == -2&&g[1]==1)return "RL";
            return "RR";
        }
        return "NO";
    }

将二叉树转换成平衡二叉树的代码:


class Solution {
public:
    unordered_map<TreeNode*, int>mp;

    void fun1(vector<int>& g, TreeNode* r) {
        if ( r == NULL||(r->left==NULL&&r->right==NULL))return;
        if (mp[r->left] == mp[r->right])return;
        g.push_back(mp[r->left] - mp[r->right]);
        fun1(g, r->left);
        fun1(g, r->right);
    }

    string check(TreeNode* root) {
        vector<int>g;
        fun1(g, root);
        if (g[0] == 2&&g[1]==1)return "LL";
        else if (g[0] == 2&&g[1]==-1)return "LR";
        else {
            if (g[0] == -2&&g[1]==1)return "RL";
            return "RR";
        }
        return "NO";
    }

    void Turnleft(TreeNode*& r) {
        TreeNode* A = r;
        TreeNode* B = r->right;
        A->right = B->left;
        B->left = A;
        r = B;
    }

    void Turnright(TreeNode*& r) {
        TreeNode* A = r;
        TreeNode* B = r->left;
        A->left = B->right;
        B->right = A;
        r = B;
    }

    void change(TreeNode*& r, string ret) {
        if (ret == "LL") {
            Turnright(r);
            mp[r] = mp[r->left] + 1;
        }
        else if (ret == "RR") {
            Turnleft(r);
            mp[r] = mp[r->left] + 1;
        }
        else if (ret == "RL") {
            Turnright(r->right);
            Turnleft(r);
            mp[r] = mp[r->left] + 1;
        }
        else {
            Turnleft(r->left);
            Turnright(r);
            mp[r] = mp[r->left] + 1;
        }
    }

    int dfs(TreeNode*& root) {
        if (root == NULL) {
            return 0;
        }
        int lh = dfs(root->left);
        int rh = dfs(root->right);

        int h = lh - rh;
        //cout << "__________________" << lh << " " << rh << " " << h << "______"<<root->val<<endl;
        if (h == 2 || h == -2) {
            //cout << root->val << endl;
            string ret = check(root);
            //cout << ret << endl;
            change(root, ret);
        }
        mp[root] = max(lh, rh) + 1;
        return max(lh,rh)+1;
    }

    TreeNode* balanceBST(TreeNode* root) {
        dfs(root);
        return root;
    }
};

 完整代码:

代码中有测试样例

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

// Function to insert a value into BST
TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (!root) {
        return new TreeNode(val);
    }
    if (val < root->val) {
        root->left = insertIntoBST(root->left, val);
    }
    else {
        root->right = insertIntoBST(root->right, val);
    }
    return root;
}

// Function to construct BST from preorder traversal
TreeNode* bstFromPreorder(vector<int>& preorder) {
    TreeNode* root = nullptr;
    for (int val : preorder) {
        if (val == 0)continue;
        root = insertIntoBST(root, val);
    }
    return root;
}

// Function to perform inorder traversal (for verification)
void inorderTraversal(TreeNode* root) {
    if (root) {
        inorderTraversal(root->left);
        cout << root->val << " ";
        inorderTraversal(root->right);
    }
}


// Function to perform level order traversal
void levelOrderTraversal(TreeNode* root) {
    if (!root) {
        return;
    }

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        TreeNode* current = q.front();
        q.pop();

        cout << current->val << " ";

        if (current->left) {
            q.push(current->left);
        }
        if (current->right) {
            q.push(current->right);
        }
    }
}


class Solution {
public:
    unordered_map<TreeNode*, int>mp;

    void fun1(vector<int>& g, TreeNode* r) {
        if ( r == NULL||(r->left==NULL&&r->right==NULL))return;
        if (mp[r->left] == mp[r->right])return;
        g.push_back(mp[r->left] - mp[r->right]);
        fun1(g, r->left);
        fun1(g, r->right);
    }

    string check(TreeNode* root) {
        vector<int>g;
        fun1(g, root);
        if (g[0] == 2&&g[1]==1)return "LL";
        else if (g[0] == 2&&g[1]==-1)return "LR";
        else {
            if (g[0] == -2&&g[1]==1)return "RL";
            return "RR";
        }
        return "NO";
    }

    void Turnleft(TreeNode*& r) {
        TreeNode* A = r;
        TreeNode* B = r->right;
        A->right = B->left;
        B->left = A;
        r = B;
    }

    void Turnright(TreeNode*& r) {
        TreeNode* A = r;
        TreeNode* B = r->left;
        A->left = B->right;
        B->right = A;
        r = B;
    }

    void change(TreeNode*& r, string ret) {
        if (ret == "LL") {
            Turnright(r);
            mp[r] = mp[r->left] + 1;
        }
        else if (ret == "RR") {
            Turnleft(r);
            mp[r] = mp[r->left] + 1;
        }
        else if (ret == "RL") {
            Turnright(r->right);
            Turnleft(r);
            mp[r] = mp[r->left] + 1;
        }
        else {
            Turnleft(r->left);
            Turnright(r);
            mp[r] = mp[r->left] + 1;
        }
    }

    int dfs(TreeNode*& root) {
        if (root == NULL) {
            return 0;
        }
        int lh = dfs(root->left);
        int rh = dfs(root->right);

        int h = lh - rh;
        //cout << "__________________" << lh << " " << rh << " " << h << "______"<<root->val<<endl;
        if (h == 2 || h == -2) {
            //cout << root->val << endl;
            string ret = check(root);
            //cout << ret << endl;
            change(root, ret);
        }
        mp[root] = max(lh, rh) + 1;
        return max(lh,rh)+1;
    }

    TreeNode* balanceBST(TreeNode* root) {
        dfs(root);
        return root;
    }
};

int main() {
    vector<int> preorder={ 31,25,47,16,28,0,0,0,0,0,30,0,0 };

    /*
    31,25,47,0,0,40,69,0,43,0,0 ,0,0            RL
    1,0,2,0,3,0,4,0,0                         RR
    31,25,47,0,0,40,69,36,0,0,0 ,0,0            RL
    31,25,47,16,28,0,0,0,0,26,0,0,0             LR
    31,25,47,16,28,0,0,0,0,0,30,0,0             LR
    */

    TreeNode* root = bstFromPreorder(preorder);

    // Verification by performing inorder traversal
    inorderTraversal(root);
    cout << endl;
    levelOrderTraversal(root);
    cout << endl;

    Solution solve;
    root=solve.balanceBST(root);

    levelOrderTraversal(root);
    cout << endl;

    return 0;
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/283280.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

零知识证明(zk-SNARK)- groth16(一)

全称为 Zero-Knowledge Succinct Non-Interactive Argument of Knowledge&#xff0c;简洁非交互式零知识证明&#xff0c;简洁性使得运行该协议时&#xff0c;即便 statement 非常大&#xff0c;它的 proof 大小也仅有几百个bytes&#xff0c;并且验证一个 proof 的时间可以达…

2023年年度总结,一个小白的CSDN涨粉历程

前言 滚滚长江东逝水&#xff0c;一去不复返。 转眼间已到2024年节点&#xff0c;时间如滚滚长江水向东奔流不息&#xff0c;在长江消失之前&#xff0c;都不会停歇&#xff0c;也不会回头。人亦如此&#xff0c;不管是生活还是学习&#xff0c;都是不断往前走的过程&#xff…

数据中台的数据处理及应用说明

科技飞速发展的时代&#xff0c;企业信息化建设会越来越完善&#xff0c;越来越体系化&#xff0c;当今数据时代背景下更加强调、重视数据的价值&#xff0c;以数据说话&#xff0c;通过数据为企业提升渠道转化率、改善企业产品、实现精准运营&#xff0c;为企业打造自助模式的…

[BUG]Datax写入数据到psql报不能序列化特殊字符

1.问题描述 Datax从mongodb写入数据到psql报错如下 org.postgresql.util.PSQLException: ERROR: invalid bytesequence for encoding "UTF8": 0x002.原因分析 此为psql独有的错误&#xff0c;不能对特殊字符’/u0000’,进行序列化&#xff0c;需要将此特殊字符替…

GCP 创建1个windows vm 并连接

有时需要临时使用1台windows 的机器 创建windows vm 既然是临时 直接用gcloud command gcloud compute instances create instance-windows \--zoneeurope-west2-c \--machine-typen2d-standard-4 \--boot-disk-size100GB \--image-projectwindows-cloud \--imagewindows-se…

力扣回溯算法-电话号码的字母组合

力扣第17题&#xff0c;电话号码的字母组合 题目 给定一个仅包含数字 2-9 的字符串&#xff0c;返回所有它能表示的字母组合。 给出数字到字母的映射如下&#xff08;与电话按键相同&#xff09;。注意 1 不对应任何字母。 .电话号码的字母组合 示例: 输入&#xff1a;“2…

【动态规划】【字符串】C++算法:正则表达式匹配

作者推荐 视频算法专题 涉及知识点 动态规划 字符串 LeetCode10:正则表达式匹配 给你一个字符串 s 和一个字符规律 p&#xff0c;请你来实现一个支持 ‘.’ 和 ‘’ 的正则表达式匹配。 ‘.’ 匹配任意单个字符 ’ 匹配零个或多个前面的那一个元素 所谓匹配&#xff0c;是…

ORACLE Primavera Unifier v23.12 最新虚拟机(VM)分享下载

引言 根据上周的计划&#xff0c;我近日简单制作了一个基于ORACLE Primavera Unifier 最新版23.12的虚拟机演示环境&#xff0c;里面包括了unifier的全套系统服务 此虚拟系统环境仅用于演示、培训和测试目的。如要在生产环境中使用此虚拟机&#xff0c;请您与Oracle 销售代表联…

使用setoolkit制作钓鱼网站并结合dvwa靶场储存型XSS漏洞利用

setoolkit是一款kali自带的工具 使用命令启动 setoolkit 1) Social-Engineering Attacks 1&#xff09; 社会工程攻击 2) Penetration Testing (Fast-Track) 2&#xff09; 渗透测试&#xff08;快速通道&#xff09; 3) Third Party Module…

排序算法-选择插入排序

文章目录 排序算法-选择插入排序 排序算法-选择插入排序 /// <summary>/// 选择插入排序/// Krystal 2023-11-10 09:02:06 每一次找一个最小的放到正确的位置上/// 直接选择排序通过每一轮的比较&#xff0c;找到最大值和最小值&#xff0c;将最大值的节点和右边交换&…

[OCR]Python 3 下的文字识别CnOCR

目录 1 CnOCR 2 安装 3 实践 1 CnOCR CnOCR 是 Python 3 下的文字识别&#xff08;Optical Character Recognition&#xff0c;简称OCR&#xff09;工具包。 工具包支持简体中文、繁体中文&#xff08;部分模型&#xff09;、英文和数字的常见字符识别&#xff0c;支持竖…

【Elasticsearch源码】 分片恢复分析

带着疑问学源码&#xff0c;第七篇&#xff1a;Elasticsearch 分片恢复分析 代码分析基于&#xff1a;https://github.com/jiankunking/elasticsearch Elasticsearch 8.0.0-SNAPSHOT 目的 在看源码之前先梳理一下&#xff0c;自己对于分片恢复的疑问点&#xff1a; 网上对于E…

outlook邮箱群发邮件方法?邮箱如何群发?

outlook邮箱群发邮件如何使用&#xff1f;QQ邮箱设置群发的步骤&#xff1f; Outlook邮箱群发邮件&#xff1a;必要性 Outlook邮箱作为全球广泛使用的邮件服务之一&#xff0c;不仅提供了便捷的邮件收发功能&#xff0c;还支持多种附件、日历提醒及强大的联系人管理。Outlook…

Java集合/泛型篇----第五篇

系列文章目录 文章目录 系列文章目录前言一、说说LinkHashSet( HashSet+LinkedHashMap)二、HashMap(数组+链表+红黑树)三、说说ConcurrentHashMap前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇文章男女通…

微信计数统计器

前段采用非注入Exui编写 分享页 后台采用ThinkPHP开发

3D视觉-相机选用的原则

鉴于不同技术方案都有其适用的场景&#xff0c;立体相机的选型讲究的原则为“先看用途&#xff0c;再看场景&#xff0c;终评精度”&#xff0c;合适的立体相机在方案中可以起到事半功倍的效果。从用途上来进行划分&#xff0c;三维视觉方案主要应用在两个方向&#xff1a;测量…

ChatGPT 对SEO的影响

ChatGPT 的兴起是否预示着 SEO 的终结&#xff1f; 一点也不。事实上&#xff0c;如果使用得当&#xff0c;它可以让你的 SEO 工作变得更加容易。 强调“正确使用时”。 你可以使用ChatGPT来帮助进行关键字研究的头脑风暴部分、重新措辞你的内容、生成架构标记等等。 但你不…

国产化软硬件升级之路:πDataCS 赋能工业软件创新与实践

在国产化浪潮的推动下&#xff0c;基础设施软硬件替换和升级的需求日益增长。全栈国产化软硬件升级替换已成为许多领域中的必选项&#xff0c;也引起了数据库和存储领域的广泛关注。近年来&#xff0c;虽然涌现了许多成功的替换案例&#xff0c;但仍然面临着一些问题。 数据库…

操作系统 全整理

第一章 第二章 进程控制 原语 进程创建 进程终止 进程阻塞和唤醒 进程切换 进程通信 共享数据空间 略过 消息传递 以格式化的消息通过发送、接收消息原语来进行数据交换 管道通信 什么是线程&#xff1f; 线程的实现方式 线程模型是由 线程的状态与转换 进程调度 高级调…

[2024区块链开发入门指引] - 比特币运行原理

一份为小白用户准备的免费区块链基础教程 工欲善其事,必先利其器 Web3开发中&#xff0c;各种工具、教程、社区、语言框架.。。。 种类繁多&#xff0c;是否有一个包罗万象的工具专注与Web3开发和相关资讯能毕其功于一役&#xff1f; 参见另一篇博文&#x1f449; 2024最全面…