设备发现协议SSDP实现

article/2025/10/1 2:46:09

原理：

1.将socket加入239.255.255.250，端口 1900

2.客户端：通过设置setsockopt +IPPROTO_IP,IP_ADD_MEMBERSHIP属性，可向ssdp组进行组播。

3.服务端：通过设置绑定239.255.255.250:1900进行数据接收，通过setsockopt +IPPROTO_IP,IP_ADD_MEMBERSHIP属性 加入组播。

容易错误的地方：

服务端打印sendto成功，但是通过wireshark抓包发现没有组播发送到239.255.255.250

这是因为：sendto的时候，用的sockaddr_in是通过recvfrom得到的：recvfrom得到的是具体的某个从组播拷贝的数据的源ip,这是单播。如果要组播发送，则要发送到这个地址：
    m_cddr.sin_family = AF_INET;
    m_cddr.sin_addr.s_addr = inet_addr("239.255.255.250");
    m_cddr.sin_port = htons(1900);

客户端代码：

/*
Author:zhuoyong
Date:2022-04-07
Mark:人脸识别客户端代码
*/#ifndef CSSDPCLIENT_H
#define CSSDPCLIENT_H
#include<string>
#include<string.h>
#include<queue>
#include<stdio.h>
#include<stdlib.h>
#include<arpa/inet.h>
#include<thread>
#include<chrono>
#include<unistd.h>
#include<netinet/in.h>
#include<arpa/inet.h>
#include<net/if.h>
#include<pthread.h>
#include<fcntl.h>
#define ERR printf
#define RTM printf
#define MAXSSDPSIZE 1024using namespace std;class CSSDPClient
{
public:static  void    Discover();//最终加密后的pssword=：md5(<uuid>:<uid>:<pwd>)static  void    ModifyNet(string &strUuid,string&strUid,string&strPwd,string &strMask,string&strGateway,string &strDns);//strCryptPwd=base64(AES(pwd))static  void    ModifyUser(string &strUuid,string&strUid,string&strPwd);
protected:CSSDPClient();~CSSDPClient();void    SendMsg(const string&str);void    RecvMsg();void    NotifyOne(const string&str);string  MakeSSDHeader();string  MakeSearchMsg();string  MakeModifyNetMsg();string  MakeModifyUserMsg();static  CSSDPClient *Ins();void    InerDiscover(const string&str);void    InitSocket();
private:static CSSDPClient *    g_in;sockaddr_in             m_sddr ;int                     m_ssdps;queue<string>           m_que;pthread_cond_t          m_cd;pthread_mutex_t         m_mt;
};#endif // CSSDPCLIENT_H

/** ===========================================================================**       Filename:  SSDPClient.cpp*    Description:  客户端设备发现 xml协议*        Version:  1.0*        Created:  20220406-12:07*       Revision:  none*       Compiler:  g++*         Author:   (zhouyongku),*        Company:  ** ===========================================================================*/#include"SSDPClient.h"CSSDPClient *CSSDPClient::g_in=NULL;
//全局变量//解析IP地址
CSSDPClient::CSSDPClient()
{m_mt=PTHREAD_MUTEX_INITIALIZER;m_cd=PTHREAD_COND_INITIALIZER;std::thread t([&]{InitSocket();while(true){pthread_mutex_lock(&m_mt); // 拿到互斥锁，进入临界区if( m_que.size()<=0 )pthread_cond_wait(&m_cd,&m_mt); // 令线程等待在条件变量上pthread_mutex_unlock(&m_mt); // 释放互斥锁InerDiscover(m_que.front());m_que.pop();}});t.detach();
}CSSDPClient::~CSSDPClient()
{}CSSDPClient *CSSDPClient::Ins()
{if( CSSDPClient::g_in == nullptr ){CSSDPClient::g_in = new CSSDPClient();}return CSSDPClient::g_in;
}void CSSDPClient::InerDiscover(const string&str)
{SendMsg( str );RecvMsg( );
}void CSSDPClient::InitSocket()
{struct timeval TimeOut;TimeOut.tv_sec = 1;TimeOut.tv_usec = 0;m_ssdps=socket(AF_INET,SOCK_DGRAM,0);if( m_ssdps < 0){ERR("CSSDPClient::InitSocket failed of create socket 239.255.255.250:1900");return;}bzero(&m_sddr, sizeof(m_sddr));m_sddr.sin_family = AF_INET;m_sddr.sin_addr.s_addr = inet_addr("239.255.255.250");m_sddr.sin_port = htons(1900);setsockopt(m_ssdps, SOL_SOCKET, SO_RCVTIMEO, (char *)&TimeOut, sizeof(TimeOut));ip_mreq mreq;bzero(&mreq,sizeof(mreq));mreq.imr_multiaddr.s_addr =inet_addr("239.255.255.250");mreq.imr_interface.s_addr =htonl(INADDR_ANY);if( setsockopt(m_ssdps, IPPROTO_IP,IP_ADD_MEMBERSHIP, &mreq, sizeof(mreq)) <0 ){ERR("CSSDPServer::InitSocket failed of setsockopt IP_ADD_MEMBERSHIP");return;}//    if( bind(m_ssdps, (struct sockaddr *)&m_sddr, sizeof(m_sddr)) < 0 )
//    {
//        ERR("CSSDPClient::InitSocket failed of bind socket %s:%d",SSDP_MCAST_ADDR,SSDP_PORT);
//    }
}void CSSDPClient::Discover()
{string str=CSSDPClient::Ins()->MakeSearchMsg();CSSDPClient::Ins()->NotifyOne(str);}void CSSDPClient::ModifyNet(string &strUuid, string &strUid, string &strPwd, string &strMask, string &strGateway, string &strDns)
{string str=CSSDPClient::Ins()->MakeModifyNetMsg();CSSDPClient::Ins()->NotifyOne(str);
}void CSSDPClient::ModifyUser(string &strUuid, string &strUid, string &strPwd)
{string str=CSSDPClient::Ins()->MakeModifyUserMsg();CSSDPClient::Ins()->NotifyOne(str);
}void CSSDPClient::NotifyOne(const string&str)
{RTM("CSSDPClient::NotifyOne quesize=%d",m_que.size());pthread_mutex_lock(&m_mt); // 拿到互斥锁，进入临界区m_que.push( str );pthread_cond_signal(&m_cd); // 通知等待在条件变量上的消费者pthread_mutex_unlock(&m_mt); // 释放互斥锁
}string CSSDPClient::MakeSSDHeader()
{string strMsg="M-SEARCH * HTTP/1.1\n";strMsg +="HOST: 239.255.255.250:1900\n";strMsg +="MAN: \"ssdp:discover\"\n";strMsg +="MX: 1\n";strMsg +="ST: urn:dial-multiscreen-org:service:dial:1\n";strMsg +="USER-AGENT:arm\n";return strMsg;
}string CSSDPClient::MakeSearchMsg()
{string strMsg=MakeSSDHeader();strMsg +="<?xml version=\"1.0\" encoding=\"utf-8\"?>\n";strMsg +="<Probe>\n";strMsg +="  <Uuid>";strMsg += "uuid-test";strMsg +="</Uuid>\n";strMsg +="  <Types>inquiry</Types>\n";strMsg +="  <DeviceType>";strMsg += "wodepingban";strMsg +="</DeviceType>\n";strMsg +="</Probe>";return strMsg;
}string CSSDPClient::MakeModifyNetMsg()
{string strMsg=MakeSSDHeader();char szMsg[MAXSSDPSIZE]={0};sprintf( szMsg,"%s\n""<?xml version=\"1.0\" encoding=\"utf-8\"?>\n""<Probe>\n""<Uuid>testuuid</Uuid>\n""<Types>update</Types>\n""<DeviceSN>123456sdflsdfjl1023-1asdfgh</DeviceSN>\n""<method>modifyipdns</method>\n""<MAC>ab-cd-ef-gh-kh</MAC>\n""<IPv4Address>192.168.66.24</IPv4Address>\n""<IPv4SubnetMask>255.255.255.0</IPv4SubnetMask>\n""<IPv4Gateway>192.168.66.254</IPv4Gateway>\n""<IPv6Address>::</IPv6Address>\n""<IPv6Gateway>::</IPv6Gateway>\n""<IPv6MaskLen>64</IPv6MaskLen>\n""<DHCP>false</DHCP>\n""<Password>kFnsMaQrzmGi89g+6txepC1RNnZMSi/fA16x+UdjFOmqBmoVCc/zeZ8X6oZmLBdWaXnvwTxjLIQBsLsDP0xjHw==</Password>\n""</Probe>\n",strMsg.c_str());return string(szMsg);}string CSSDPClient::MakeModifyUserMsg()
{string strMsg=MakeSSDHeader();char szMsg[MAXSSDPSIZE]={0};sprintf( szMsg,"%s\n""<?xml version=\"1.0\" encoding=\"utf-8\"?>\n""<Probe>\n""<Uuid>your uuid>\n""<Types>update</Types>\n""<DeviceSN>your device sn</DeviceSN>\n""<method>modifypassword</method>\n""<newpassword>your new md5 password</newpassword>\n""<Password>your md5 password</Password>\n""</Probe>\n");return string(szMsg);
}//发送ssdp:discover消息
void CSSDPClient::SendMsg(const string&str)
{RTM("CSSDPClient::SendMsg msg=%s",str.c_str());socklen_t len = sizeof(m_sddr);int nRet=sendto(m_ssdps,str.c_str(),str.length(),0,(sockaddr*)&m_sddr,len);if( nRet >0 ){RTM("CSSDPClient::SendMsg leng=%d",nRet);}char szMsg[MAXSSDPSIZE]={0};nRet = recvfrom( m_ssdps,szMsg,MAXSSDPSIZE,0,(sockaddr*)&m_sddr,&len);if( nRet >0 ){RTM("CSSDPClient::SendMsg RECV MSG=%s",szMsg);}
}void CSSDPClient::RecvMsg()
{socklen_t len = sizeof(m_sddr);char szMsg[MAXSSDPSIZE]={0};int num = recvfrom(m_ssdps,szMsg,MAXSSDPSIZE,0,(sockaddr*)&m_sddr,&len);if( num >0 ){string str;//ParseMsg(buf);}
}

服务端：

#ifndef CSSDPSERVER_H
#define CSSDPSERVER_H
/*
Author:zhuoyong
Date:2022-04-07
Mark:设备发现服务端代码
*/
#include<string>
#include<string.h>
#include<queue>
#include<stdio.h>
#include<stdlib.h>
#include<arpa/inet.h>
#include<thread>
#include<chrono>
#include<unistd.h>
#include<netinet/in.h>
#include<arpa/inet.h>
#include<net/if.h>
#include<pthread.h>
#include<fcntl.h>
#include<mutex>
#define ERR printf
#define RTM printf
#define MAXSSDPSIZE 1024using namespace std;class CSSDPServer
{
public:static  void    Init(  );protected:CSSDPServer(  );~CSSDPServer();void    SendMsg(const string&str);void    RecvMsg();string  MakeSSDHeader();string  MakeResponseSearchMsg( );static  CSSDPServer *Ins();void    InitSendSocket();void    InitRecvSocket();void    ProcesMsg( const char *strMsg );
private:static CSSDPServer *    g_in;sockaddr_in             m_sddr ;sockaddr_in             m_cddr ;int                     m_ssdps;int                     m_ssdpc;queue<string>           m_que;pthread_cond_t          m_cd;pthread_mutex_t         m_mt;
};#endif // CSSDPSERVER_H

/** ===========================================================================**       Filename:  SSDPServer.cpp*    Description:  服务端设备发现 xml协议*        Version:  1.0*        Created:  20220406-12:07*       Revision:  none*       Compiler:  g++*         Author:   (zhouyongku),*        Company:  ** ===========================================================================*/#include"SSDPServer.h"CSSDPServer *CSSDPServer::g_in=NULL;
//全局变量//解析IP地址
CSSDPServer::CSSDPServer(  )
{m_mt=PTHREAD_MUTEX_INITIALIZER;m_cd=PTHREAD_COND_INITIALIZER;RTM("CSSDPServer::CSSDPServer");std::thread t([&]{RTM("CSSDPServer::CSSDPServer create thread");InitSendSocket();InitRecvSocket();char szMsg[MAXSSDPSIZE]={0};socklen_t len = sizeof(m_sddr);while( true ){if((recvfrom(m_ssdps, szMsg, MAXSSDPSIZE, 0, (sockaddr*)&m_sddr, &len)) >= 0){//printf("recvfrom success ip=%s,msg=%s",inet_ntoa(m_sddr.sin_addr),szMsg);ProcesMsg( szMsg );memset(szMsg,0,sizeof(szMsg));}std::this_thread::sleep_for(std::chrono::seconds(10));}});t.detach();
}
void CSSDPServer::ProcesMsg( const char *strMsg )
{//and your code hereSendMsg( MakeResponseSearchMsg( ) );}CSSDPServer::~CSSDPServer()
{}CSSDPServer *CSSDPServer::Ins(  )
{if( CSSDPServer::g_in == nullptr ){CSSDPServer::g_in = new CSSDPServer(  );}return CSSDPServer::g_in;
}void CSSDPServer::InitSendSocket()
{struct timeval TimeOut;TimeOut.tv_sec = 1;TimeOut.tv_usec = 0;m_ssdpc=socket(AF_INET,SOCK_DGRAM,0);if( m_ssdpc < 0){ERR("CSSDPClient::InitSocket failed of create socket 239.255.255.250:1900");return;}bzero(&m_cddr, sizeof(m_cddr));m_cddr.sin_family = AF_INET;m_cddr.sin_addr.s_addr = inet_addr("239.255.255.250");m_cddr.sin_port = htons(1900);setsockopt(m_ssdpc, SOL_SOCKET, SO_RCVTIMEO, (char *)&TimeOut, sizeof(TimeOut));ip_mreq mreq;bzero(&mreq,sizeof(mreq));mreq.imr_multiaddr.s_addr =inet_addr("239.255.255.250");mreq.imr_interface.s_addr =htonl(INADDR_ANY);if( setsockopt(m_ssdpc, IPPROTO_IP,IP_ADD_MEMBERSHIP, &mreq, sizeof(mreq)) <0 ){ERR("CSSDPServer::InitSocket failed of setsockopt IP_ADD_MEMBERSHIP");return;}
}void CSSDPServer::InitRecvSocket()
{RTM("CSSDPServer::InitRecvSocket");struct timeval TimeOut;TimeOut.tv_sec = 1;TimeOut.tv_usec = 0;m_ssdps=socket(AF_INET,SOCK_DGRAM,0);if( m_ssdps < 0){ERR("CSSDPServer::InitSocket failed of create socket 239.255.255.250:1900");return;}bzero(&m_sddr, sizeof(m_sddr));m_sddr.sin_family = AF_INET;m_sddr.sin_addr.s_addr = INADDR_ANY;m_sddr.sin_port = htons(1900);if( bind(m_ssdps, (struct sockaddr *)&m_sddr, sizeof(m_sddr)) < 0 ){ERR("CSSDPServer::InitSocket failed of bind socket 0.0.0.0:1900");return ;}ip_mreq mreq;bzero(&mreq,sizeof(mreq));mreq.imr_multiaddr.s_addr =inet_addr("239.255.255.250");mreq.imr_interface.s_addr =htonl(INADDR_ANY);if( setsockopt(m_ssdps, IPPROTO_IP,IP_ADD_MEMBERSHIP, &mreq, sizeof(mreq)) <0 ){ERR("CSSDPServer::InitSocket failed of setsockopt IP_ADD_MEMBERSHIP");return;}RTM("CSSDPServer::InitRecvSocket success");}void CSSDPServer::Init( )
{CSSDPServer::Ins(  );
}string CSSDPServer::MakeSSDHeader()
{string strMsg="NOTIFY * HTTP/1.1\n""HOST: 239.255.255.250:1900\n""CACHE-CONTROL: max-age=66\n""LOCATION:xml\n""OPT:ns=01\n""01-NLS:0\n""NT: urn:schemas-upnp-org:service:AVTransport:1\n""NTS: ssdp:alive\n""SERVER: Ubuntu/16.04\n""X-User-Agent: redsonic\n""USN:1\n";return strMsg;
}string CSSDPServer::MakeResponseSearchMsg()
{string strMsg=MakeSSDHeader();char szMsg[MAXSSDPSIZE]={0};snprintf( szMsg,MAXSSDPSIZE,"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n""<ProbeMatch>\n""<mount>your msg</mount>\n""<enable>your msg</enable>\n""<platformip>%s</platformip>\n""<Uuid>your msg</Uuid>\n""<Types>inquiry</Types>\n""<DeviceType>CDZSFACEBOX</DeviceType>\n""<DeviceSN>your msg</DeviceSN>\n""<DeviceName>your msg</DeviceName>\n""<MAC>your msg</MAC>\n""<IPv4Address>your msg</IPv4Address>\n""<IPv4SubnetMask>your msg</IPv4SubnetMask>\n""<IPv4Gateway>your msg</IPv4Gateway>\n""<IPv6Address>::</IPv6Address>\n""<IPv6Gateway>::</IPv6Gateway>\n""<IPv6MaskLen>64</IPv6MaskLen>\n""<DHCP>::</DHCP>\n""<SoftwareVersion>your msg</SoftwareVersion>\n""<BootTime>your msg</BootTime>\n""<Diskrate>your msg</Diskrate >\n""<Cpurate>your msg</Cpurate >\n""<Memoryrate>%s</Memoryrate >\n""</ProbeMatch>");strMsg += szMsg;return strMsg;
}//发送ssdp:discover消息
void CSSDPServer::SendMsg(const string&str)
{RTM("CSSDPServer::SendMsg msg=%s",str.c_str());socklen_t len = sizeof(m_cddr);int nLen = sendto(m_ssdps,str.c_str(),str.length(),0,(sockaddr*)&m_cddr,len);if( nLen >0 ){RTM("CSSDPServer::SendMsg success to send to %s msg len=%d",inet_ntoa(m_cddr.sin_addr),nLen);}else{RTM("CSSDPServer::SendMsg failed to send msg");}
}void CSSDPServer::RecvMsg()
{socklen_t len = sizeof(m_sddr);char szMsg[MAXSSDPSIZE]={0};int num = recvfrom(m_ssdps,szMsg,MAXSSDPSIZE,0,(sockaddr*)&m_sddr,&len);if( num >0 ){string str;//ParseMsg(buf);}
}

测试代码：

#include<SSDPClient.h>int main(int argc, char *argv[])
{while( true ){CSSDPClient::Discover();std::this_thread::sleep_for( std::chrono::seconds(10) );}return 0;
}
#include"SSDPServer.h"
int main(int argc, char *argv[])
{CSSDPServer::Init( );std::this_thread::sleep_for( std::chrono::seconds(100000) );return 0;
}

抓包：

发送方：ssdpclient 192.168.66.44 发送 search命令

接收方 ssdpserv (我在同一个电脑上测试 ip都是192.168.66.44)


http://chatgpt.dhexx.cn/article/WpMNw8T8.shtml

相关文章

wireshark-协议分析【初见】（NBNS协议，SSDP协议、IGMPv2）

wireshark-协议分析【初见】（NBNS协议，SSDP协议、IGMPv2）

写在前面 win7:192.168.2.150&#xff08;00-0c-29-CF-D3-0F&#xff09; kali:192.168.2.120&#xff08;00:0c:29:e7:1c:e5&#xff09; &#xff08;均使用的vmware虚拟机平台&#xff09; 该系列并不会太关注wireshark的用法&#xff0c;重点关注协议交换时数据包的情况。…
阅读更多...
ssdp协议搜索GB28181设备

ssdp协议搜索GB28181设备

1、http协议和ssdp协议 ssdp协议近似于http协议&#xff0c;事实上&#xff0c;和http协议相似得地方就是他得协议内容&#xff0c;当然&#xff0c;我们要去除他得端口和d类地址。 为什么我在给其他员工或者面试得时候要他人深入一些&#xff0c;理解一下http协议&#xff0…
阅读更多...
二叉树、红黑树

二叉树、红黑树

二叉树 遍历概念 　所谓遍历(Traversal)是指沿着某条搜索路线&#xff0c;依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。 　遍历是二叉树上最重要的运算之一&#xff0c;是二叉树上进行其它运算之基础。 遍历方案 1&#x…
阅读更多...
图解红黑树及Java进行红黑二叉树遍历的方法

图解红黑树及Java进行红黑二叉树遍历的方法

红黑树 红黑树是一种数据结构与算法课堂上常常提到但又不会细讲的树&#xff0c;也是技术面试中经常被问到的树&#xff0c;然而无论是书上还是网上的资料&#xff0c;通常都比较刻板难以理解&#xff0c;能不能一种比较直观的方式来理解红黑树呢&#xff1f;本文将以图形的方式…
阅读更多...
算法 红黑树

算法 红黑树

红黑树 红黑树概述红黑树性质 红黑树的插入代码实现 红黑树概述 红黑树&#xff08;Red Black Tree&#xff09;是一种自平衡二叉查找树&#xff0c;是在计算机科学的中用到的一种数据结构&#xff0c;典型的用途是实现关联数组&#xff0c;红黑树和AVL树类似&#xff0c;都是…
阅读更多...
【数据结构】--二叉树，红黑树

【数据结构】--二叉树，红黑树

【数据结构】--二叉树&#xff0c;红黑树 &#x1f3c6;概念&#x1f34d;定义&#x1f34b; 术语&#x1f4dd;可视化网站 ☀️二叉树✨ 二叉搜索树&#x1f34d;定义&#x1f351;查找节点&#x1f34b;插入节点&#x1f345;遍历节点&#x1f355; 前序排序&#x1f9c0; 后…
阅读更多...
红黑树的详细实现(C++)

红黑树的详细实现(C++)

红黑树概念(concept) 树型结构主要用于搜索&#xff0c;一直是科学领域的重要演算法&#xff0c;当中探讨了树可能遇到的问题&#xff1a;树的成长可能偏向于一边&#xff0c;也就是不平衡现象。 二叉树是常见且广泛使用的一种树&#xff0c;面临其可能退化成链表的潜藏缺点&…
阅读更多...
二叉树——二叉查找树和红黑树

二叉树——二叉查找树和红黑树

二叉树 二叉树&#xff0c;是一个非常重要的数据结构&#xff0c;在日常的开发中起着很重要的作用&#xff0c;它也衍生出来的各种高效的复杂的数据结构&#xff0c;为我们解决问题提供了高效的解决方案。 二叉树&#xff0c;它是由各个数据节点和左右链接构成的一种类似树的数…
阅读更多...
Java——红黑树

Java——红黑树

概念 红黑树也是一种二叉搜索树&#xff0c;但是和avl树不同&#xff0c;它并不是依靠平衡因子来保证树的平衡的&#xff0c;而是通过颜色 红黑树每个节点中会存储颜色&#xff0c;分为红色和黑色&#xff0c;通过红黑树的限制条件&#xff0c;可以保证从根节点出发到叶子节点…
阅读更多...
二叉树--红黑树

二叉树--红黑树

红黑树 定义 红黑树&#xff0c;顾名思义&#xff0c;就是树的节点只有红色和黑色两种状态&#xff0c;通过这两种状态的标识和规定颜色的使用&#xff0c;来使树达到相对平衡。为什么说相对平衡&#xff1f;因为在红黑树中&#xff0c;所有的条件限制只能保证&#xff0c;所…
阅读更多...
二叉树之红黑树

二叉树之红黑树

红黑树 概述 为什么要有红黑树&#xff1f;&#xff1f;&#xff1f; 特点 红黑规则 如何在红黑树上添加节点&#xff1f; &#xff08;1&#xff09;我们不妨假设加入的节点都是黑色 &#xff08;2&#xff09;如果我们加入的节点都是红色 红黑树添加节点后如何保持红…
阅读更多...
红黑二叉树

红黑二叉树

红黑树 红黑树是每个节点都带有颜色属性的二叉查找树&#xff0c;颜色或红色或黑色。在二叉查找树强制一般要求以外&#xff0c;对于任何有效的红黑树我们增加了如下的额外要求: 节点是红色或黑色。 根节点是黑色。 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有…
阅读更多...
红黑树-Java实现

红黑树-Java实现

目录 一、定义 二、插入 三、删除 四、全部代码 五、颜色效果 一、定义 红黑树是特殊的平衡二叉树&#xff0c;具有以下特性&#xff1a; 1、根节点的颜色是黑色 2、节点颜色要么是黑色、要么是红色 3、如果一个节点的颜色是红色&#xff0c;则它的子节点必须是黑色&…
阅读更多...
红黑二叉树原理分析

红黑二叉树原理分析

1.引言 HashMap的基本结构是数组&#xff0c;链表和红黑树。以数组为基本形态&#xff0c;数组中的元素先以链表形式储存&#xff0c;当链表的长 度超过8时&#xff08;包含数组上的那个链表头&#xff09;就会将链表转换为红黑树&#xff0c;以加快修改和查询效率。当然除了H…
阅读更多...
理解红黑树及代码实现

理解红黑树及代码实现

1.红黑树定义 红黑树是一颗 红-黑的平衡二叉树,它具有二叉树的所有特性,是一颗自平衡的排序二叉树.(树中任何节点值都大于左子节点的值&#xff0c;而且都小于右子节点的值),其检索效率高&#xff0c;它是一颗空树或它的左右两个子树高度差的绝对值不超过1&#xff0c;并且左右…
阅读更多...
红黑二叉树的漫画讲解（轻松理解红黑二叉树原理）

红黑二叉树的漫画讲解（轻松理解红黑二叉树原理）

———————————— 二叉查找树&#xff08;BST&#xff09;具备什么特性呢&#xff1f; 1.左子树上所有结点的值均小于或等于它的根结点的值。 2.右子树上所有结点的值均大于或等于它的根结点的值。 3.左、右子树也分别为二叉排序树。 下图中这棵树&#xff0c;就是…
阅读更多...
Java的二叉树、红黑树、B+树

Java的二叉树、红黑树、B+树

数组和链表是常用的数据结构&#xff0c;数组虽然查找快&#xff08;有序数组可以通过二分法查找&#xff09;&#xff0c;但是插入和删除是比较慢的&#xff1b;而链表&#xff0c;插入和删除很快&#xff08;只需要改变一些引用值&#xff09;&#xff0c;但是查找就很慢&…
阅读更多...
二叉树与红黑树

二叉树与红黑树

二叉树的形成 二叉树是n(n>0)个结点的有限集合&#xff0c;该集合或者为空集&#xff08;称为空二叉树&#xff09;&#xff0c;或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成 二叉树特点 由二叉树定义以及图示分析得出二叉树有以下特点&#xff1…
阅读更多...
红黑树（C++实现）

红黑树（C++实现）

文章目录 红黑树的概念红黑树的性质红黑树结点的定义红黑树的插入红黑树的验证红黑树的查找红黑树的删除红黑树与AVL树的比较 红黑树的概念 红黑树是一种二叉搜索树&#xff0c;但在每个结点上增加了一个存储位用于表示结点的颜色&#xff0c;这个颜色可以是红色的&#xff0c;…
阅读更多...
红黑二叉树详解及理论分析

红黑二叉树详解及理论分析

发表于我的博客网站(prajna.top)&#xff1a; http://prajna.top/doc/2/175 什么是红-黑二叉树&#xff1f; 红-黑二叉树首先是一颗二叉树&#xff0c;它具有二叉树的所有性质&#xff0c;是一种平衡二叉树。普通二叉树在生成过程中&#xff0c;容易出现不平衡的现象&#xff…
阅读更多...
推荐文章

Copyright @ 2022~2023