红黑树面试题-红黑树面试最简洁的回答方式

今天来给大家分享一下关于红黑树面试题-红黑树面试最简洁的回答方式的问题，以下是对此问题的归纳整理，让我们一起来看看吧。

有了二叉树，平衡二叉树为什么还需要红黑树

红黑树是处于二叉树和平衡二叉树之间的一种折中方案的算法。说起来红黑树也算是比较难理解的一个数据结构了吧，因为其本身的增删节点，除了左旋右旋还需要变色的复杂操作。

为什么有平衡二叉树这种适合适合查找的数据结构在，还需要红黑树呢？还是先从二叉树说起。

二叉查找树的特点就是 左子树的节点值比父亲节点小，而右子树的节点值比父亲节点大。

二叉树的查询颇有 二分查找 的思想，如果查询一个节点，n 个节点的二叉查找树，正常的情况下，查找的时间复杂度为 O（logn）。为什么说是正常情况，因为上面的树其实不只是二叉树而且还是平衡二叉树。

那如果不正常的情况下，二叉树是啥样的呢？下面是一种退化为类似链表的二叉树的极端情况。这样的二叉查找树的查找时间复杂度顿时变成了 O(n)，类似于在做全表扫描，为了避免这种情况的发生，平衡二叉树在这种情况下登场了。平衡二叉树除了具有二叉树的全部特性外，加了一个规则，就是每个节点的左子树和右子树的高度差至多等于1。

嗯，这样的话就不会出现一棵链表了。平衡二叉树基于这种特点就可以保证不会出现大量节点偏向于一边的情况了。这样平衡二叉树对于有 n 个节点的平衡树，最坏的查找时间复杂度也为 O(logn)。平衡二叉树通过 构建、插入、删除、左旋、右旋 等操作来达到平衡。

MySQL索引中 B树和B+树是基于平衡二叉树的进一步改进 。B+树索引按照存储方式的不同分为 聚集索引 和 非聚集索引。

二叉树的算法实现 其实就是要插入的节点都开始和根节点比，小的放节点左边大的右边，如果位置上已经有节点了就再迭代，把当前节点作为根节点来判断放左右，直到有空位置为止。

有了平衡二叉树这么优秀的结构为什么还需要红黑树，因为平衡二叉树要求 每个节点的左子树和右子树的高度差至多等于1 ，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树规则，进而我们都需要通过 左旋 和 右旋 来进行调整，使之再次成为一颗符合要求的平衡树。如果频繁增删就会带来性能问题。所以红黑树出现了。

红黑树特性：

1、具有二叉查找树的特点。

2、根节点是黑色的；

3、 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存数据 。

4、 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的。

5、 每个节点，从该节点到达其可达的叶子节点是所有路径，都包含相同数目的黑色节点。（限制了高度）

下面是两棵红黑树的例子（黑色的空叶子节点没有画出）：

上面的例子似乎有点平衡二叉树的味道，但它并不是必须满足平衡二叉树的深度差不超过1的条件，如下面的例子。

红黑树的这种特点，使得它能够在最坏情况下，也能在 O(logn) 的时间复杂度查找到某个节点。但与平衡树不同的是，红黑树在插入、删除等操作， 不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整。 意思是查效率相当，但改效率高于平衡树，这也是我们为什么大多数情况下使用红黑树的原因。只不过据说单单在查找方面的效率的话，平衡树会比红黑树快点。

综上，可以说 红黑树是一种不大严格（没有深度差要求）的平衡树 。也可以说是一个折中方案。

那么红黑树如何进行左旋，右旋和变色来达到平衡呢 ?笔者也还没完全吃透，不过理解了上面的这些应该也够驰骋沙场了。

参考文献：

腾讯面试题：有了二叉查找树、平衡树为啥还需要红黑树？

红黑树旋转

谁能提供一些C++面试的常见程序题

流个邮箱，我可以发给你！经典C++面试问题

1.介绍STL，详细讲解STL如何实现矢量。

回答

STL(标准模板库。它由容器算法迭代器组成。

STL有以下优点:

可以轻松实现数据搜索或数据排序等一系列算法；

调试程序更安全更方便；

即使是UNIX平台上的人用STL写的代码也很容易理解(因为STL是跨平台的)。

vector本质上是一个动态数组，会根据数据的增加动态增加数组空。

2。如果用VC开发程序，常见的错误就那么多，C2001，C2005，C2011。这些错误的原因是什么？

回答

在学习VC++的过程中，LNK2001错误的主要错误信息有:

未解析的外部符号“symbol”。

如果链接器在所有库和目标文件中找不到被引用的函数、变量或标签，则会生成此错误信息。

一般来说，错误的原因有两个:一是引用的函数或变量不存在、拼写错误或使用错误；可以使用不同版本的连接库。

在编程中，我们经常会遇到LNK2005错误——重复定义错误。其实LNK2005错误并不难解决。

3。继承和委托的区别是什么，在决定使用继承还是委托时应该考虑什么？

在OOD，OOP中，组合优于继承。

当然，多态性是建立在继承的基础上的，没有继承就不可能有多态性。

当对象的类型不影响类中函数的行为时，应该使用模板来生成这样一组类。

当一个对象的类型影响到一个类中函数的行为时，我们应该使用继承来得到这样一组类。

4。指针和引用的区别是什么？如果传递引用比传递指针更安全，为什么？我不能用常量指针吗？

(1)引用创建时必须初始化，即引用有效对象；指针在定义时不需要初始化，但可以在定义后的任何地方重新赋值。

(2)没有空引用，引用必须关联合法的存储单元；指针可以为空。

(3)引用一旦初始化为指向一个对象，就不能更改为另一个对象的引用；指针可以随时更改为指向另一个对象。为引用赋值不会改变它与原始对象的绑定关系。

(4)引用的创建和销毁不会调用类的复制构造函数

(5)在语言层面，引用的用法和对象的用法是一样的；在二进制层面，引用一般是通过指针实现的，但是编译器帮助我们完成转换。

没有空引用，引用一旦初始化指向一个对象，就不能再改成另一个对象的引用，非常安全。

const指针还存在空指针，有可能产生wild指针。

一般来说，引用既有指针的效率，又有变量使用的方便直观。

5。有几种方法可以传递参数；用什么方法实现多态参数传递，如果不是，原因是什么；

传递值、传递指针或引号

6。解释你如何在项目中应用设计模式的概念。

设计模式更关心扩展和重用，这在很多情况下往往被忽略。

但是，我不建议滥用设计模式，认为它可能会使简单的问题复杂化。

7。介绍一下你对设计模式的理解。(这个过程中随机问了很多细节问题。)

设计模式的概念是由建筑师Christopher Alexander提出的。每个模式都描述了一个我们身边反复出现的问题，以及解决这个问题的核心。这样，你就可以一次又一次地使用该方案，而不必重复工作。上面的定义是设计模式的广义定义。当应用到面向对象软件领域时，就形成了狭义的设计模式定义。

可以简单的认为设计模式是解决一个特定的面向对象软件问题的具体方法，它已经上升到了一个理论层面。

框架和设计模式的区别

1。设计模式和框架针对不同的问题领域。设计模式针对面向对象的问题域；框架是针对具体业务的问题域

2，设计模式比框架更抽象。设计模式只有在遇到具体问题后才能生成代码；框架已经可以用代码

3来表示，设计模式是比框架更小的架构元素。一个框架可以包含多个设计模式

。设计模式就像武术中的基本动作。当这些招式纵向合理组合，就形成了一个套路(框架)，框架就是半成品。

8。c++和C有什么区别？

C language的结构只是数据的组合

c++的struct和class其实功能差不多，只是默认的访问属性不同。

9。构造函数可以是虚数吗，为什么？析构函数呢？可以是纯虚构的吗？

构造函数不能是虚函数。要构造一个对象，你必须清楚地知道要构造什么，否则你无法构造一个对象。

析构函数可以是一个纯虚函数。

10。与复制构造函数、深度复制、浅层复制、临时对象等相关的问题。

深拷贝是指复制资源和指针，而浅拷贝只复制指针，不复制资源

这使得两个指针指向同一个资源，导致同一个副本被析构两次，程序崩溃。

临时对象的开销比本地对象小。

11。结合一个你认为更能体现OOP思想的项目，用UML描述。这个问题大概会占面试时间的一半，会问很多问题，一不小心就可能被难倒。

.。。

12 .基类有一个虚函数。子类需要声明为虚拟的吗？为什么？

不申报也没关系。

但是，我总是喜欢显式地声明它，让代码更清晰。

13。通过仔细封装一些函数，c也可以重用。C++类有什么优势？仅仅是为了重用吗？

不仅仅是这样。

OOD和OOP从根本上改变了编程模式和设计思想，意义重大而深远。

类的三个基本特征是封装、继承和多态。

14。c++有什么特点，如何实现多态性？画出内存中基类和子类的关系。

多态性是基于继承的，需要虚函数的支持。简单多态非常简单。

子类继承父类的大部分资源，但不能继承的有构造函数、析构函数、复制构造函数、operator=函数、friend函数等。

15。为什么要引入抽象基类和纯虚函数？

主要目的是为了达到一个界面的效果。

16。介绍模板和容器。如何实现？

模板可以说是古老的，但是现在的泛型编程本质上还是模板编程。

它体现了一种普遍的、概括的思想。

STL有七个主要的容器:Vector、List、Deque、Map、MultiMap、Set、Multiset。

17。你是怎么理解MVC的？简单的例子说明了它的应用。

MVC模式是观察者模式的特例，MFC中有一个典型的文档视图架构。

18。多重继承如何消除向上继承的歧义？

就用虚拟继承吧。

1.STL里面的贴图是怎么实现的？

红黑树。

二叉树在平衡或者叶节点到根节点的高度在一定范围内时最有效。红黑树算法是一种平衡树算法。这个名字是因为树的每个节点都是红色或黑色的，节点的颜色用来检查树的平衡。在插入和删除节点的操作中，它们可能被旋转以保持树的平衡。平均和最坏情况下的插入、删除和搜索时间为O(lg n)。详情请参考Cormen [2001]。

理论

红黑树是具有以下性质的二叉查找树:

1 .所有节点都是红色或黑色的。

2。每个叶节点都是空节点，并且是黑色的。

3。如果父节点是红色的，那么两个子节点都是黑色的。

4。从一个节点到其子节点的每条简单路径都包含相同数量的黑色节点。

5。根节点总是黑色的。

2。对象是如何存储在内存中的？

需要读取

简单来说，

在类对象的内存布局中，如果有虚函数，首先是类的vtbl指针，然后是对象数据，按顺序存储

，当然会涉及到字节对齐，这样会提高访问效率。

3.说说COM的原理和实现？

COM简单来说就是不同应用、不同语言共享二进制代码的一种方式，与C++不同，只是源代码级别的复用。Windows允许你与dll共享二进制代码，如kernel32.dll、user32.dll等。但是因为这些dll都是用C写的，所以只能用C或者懂C如何调用的语言来调用。MFC引入了另一种二进制代码共享机制——MFC扩展dll，但这种机制的限制性更强，你只能在MFC程序中使用它们。COM通过建立二进制规范来解决这些问题，这也意味着COM二进制模块应该按照特殊的结构来组织，在内存中也是如此。规则是独立于语言的，负担交给了编译器。

COM对象在内存中的组织结构和C++的虚函数是一样的，这也是为什么大部分COM代码都使用C++的原因，但是要记住，COM是真正独立于语言的，因为生成的代码可以被其他所有语言使用。顺便说一下，COM不是Win32规范。理论上可以移植到Unix等任意操作系统上，但在Windows世界之外我没见过COM。

4.为什么使用智能指针？是如何实现的？

以避免资源泄漏。

内部使用引用计数机制，实现起来非常复杂。

5.给你一个指针，用new动态申请空，在另一个函数中释放。在不知道是元素还是数组的情况下，如何决定使用delete还是delete []？

不同的编译器有不同的实现机制，常用的有两种:

1。新建时，在第一个对象之前分配了多少个对象。

2。使用键值，即key-value

for ex:

int * p = new int[

p是key，n是value。

6.虚函数是如何实现的？

简单来说就是用虚函数表。

7。虚函数表是如何实现的？

每个包含虚函数的类都有一个虚函数表(vtbl)，表中的每一项都指向一个虚函数的地址，这个地址实际上是一个函数指针的数组。

虚函数表既有继承性又有多态性。每个派生类的vtbl继承其基类的vtbl。如果基类vtbl包含一个项，其派生类的vtbl也将包含相同的项，但两个项的值可能不同。如果派生类重写了与该项对应的虚函数，则派生类vtbl的项指向重载的虚函数。如果没有重载，将遵循基类的值。

在类对象的内存布局中，首先是类的vtbl指针，然后是对象数据。通过对象指针调用虚函数时，编译器生成的代码会先获取对象类的vtbl指针，然后调用vtbl中对应的项。在通过对象指针调用的情况下，无法确定指针指向的是基类对象还是派生类对象，或者是哪个派生类对象。但在运行时执行调用语句时，已经确认编译后的调用代码可以根据具体对象获得正确的vtbl，调用正确的虚函数，从而实现多态性。

这里分析一下思路。问题的本质是，这个进行虚函数调用的对象指针，在编译时缺少更多的信息，而在运行时有足够的信息，只是那时不再绑定。如何才能在两者之间做一个过渡？绑定所需的信息记录在一个公共数据结构中，该结构可以与对象指针相关联。编译时抽象绑定只需要这个数据结构，真正的绑定会在运行时获得。这个数据结构是vtbl。可以看出，用户要求的抽象和多态的实现需要后绑定，编译器通过抽象和多态实现后绑定。

一、C++程序设计：

1）标准C++模板库中有一个名为bind1st的函数配接器（实际就是一个函数模板），它接受两个参数，一个是二元函数对象bin_op，一个是二元函数对象的参数value。返回一个新的一元函数对象uni_op。在使用uni_op(param)等效于bin_op(value,param)。即二元函数对象的第一个value被“固定”了。

试编写程序实现一个类似功能的my_bind1st函数配接器，并给出相应的测试代码。

2）如果想禁止类被复制的功能（也就是保持类实例的唯一性），怎么办？

二、C程序设计

1）定义一个宏 SWAP_MIN(x, y)

交换x和y的值，并返回x和y中的最小值。

例如：

////////////////////////////////////////////////////

int x, y;

x = 1;

y = 3;

printf(“--%d--%d--%d--”, SWAP_MIN(x,y), x, y);

//////////////////////////////////////////////////////

结果是

--1--3--1--

2)我想在C文件里面重用一些C++的函数，怎么做？

三、程序设计技巧

1.1. 用C/C++实现一个简单的hash链表, 定义读和写的用户接口并实现

1.2. 如果用户需要对上述链表规定能够存储的最大元素个数，例如

set_max_size (int n)

如何修改上步中的代码来实现？

2. 设计一种数据结构用20个byte存储32个不超过32的正整数值, 给出

对每个数读，写, ++等操作的代码

3. 用正则表达式将程序中的int替换成unsigned int

4. 下面的程序的运行结果是什么,如果有错误，如何修正

char get_last ( char *str ) {

int length = sizeof (str);

return str[length-1];

}

int main () {

char* a = \"hello world!\";

char last = get_last (a);

printf (\"%c\\n\", get_last (a) );

}

5. 写一段程序找出一个数列中第二大数

6. 用户定义类型如下:

packet_type packet {

int id;

int data;

}

怎样让下面的代码能够打印p中的id和data

packet p;

cout ‘VAR’ id{‘,’id}’;’

--> {‘;’}

--> ’+’

--> ’*’

--> id

要求：

1） 检测G中在中缀表达式中出现的变量id必须在中定义过，且不能重复定义

2） 将中缀表达式转化为后缀表达式，给出语义翻译

五、如何在C程序中，实现一个能够存储任意类型数据的堆栈？比如：

push (a, int); 表示push一个int型数据a进栈。

push (b, defined_type); defined_type可以是用户自己定义的类型，如struct。这样的话，该语句表示push一个struct defined_type类型的数据b进入堆栈。

以上就是由优质生活领域创作者 嘉文社百科网小编 整理编辑的，如果觉得有帮助欢迎收藏转发~