红黑树各种操作思路见 从B-树角度理解红黑树背后的原理 ，本文是红黑树的C++实现。但并没有全面的测试，如果大家发现了bug，欢迎指出。 本文的红黑树是从前面的BST继承而来，也是用到了AVL中用到的3+4重构和旋转操作。编译时要用到前面的
常用数据结构C++实现(7)：红黑树
从B-树角度理解红黑树背后的原理
红黑树也是一种平衡二叉树，但并不像AVL那样严格。红黑树有一些等价的表述，其中比较流行的就是给结点染上红色或黑色。下面是一棵红黑树。 红黑树满足4条性质： 1. 根结点是黑色的（如果不是空树） 2. 外部结点是黑色的（外部结点是把NULL指
常用数据结构C++实现(6)：B树
本文介绍的数据结构英文是B-tree，中文写作B-树，其中 – 并不是减号，而是连接符，读作B树。 B-树是一种平衡搜索树，但它的每个结点包含的元素可以多于2个，因此并不是严格意义上的二叉树。 B-树的结点类似如下： 这可以看做
常用数据结构C++实现(5)：伸展树
伸展树也是一种平衡二叉搜索树，但它的平衡是在平均意义下的。伸展树中n次操作，每次的均摊复杂度是O(logn) 。而单独的一次操作，可能达到O(n)的复杂度。那么，与AVL相比，伸展树的优势又在哪里呢？ 伸展树中，每次会把访问到的结点通过单旋
常用数据结构C++实现(4)：AVL树
一般的二叉搜索树的高度并没有得到有效限制，在极端情况下，他甚至可以退化为一个链表。而对树高进行限制以达到O(logn)高度的二叉搜索树，又称为平衡搜索树。AVL树是最先发明的自平衡二叉查找树，它的名字来源于它的发明者 G.M. Adelso
二叉树的图形化显示
二叉树的图形化显示最主要的一步就是计算每个结点的位置。得到位置后，可以使用命令行或者图形界面来显示。应该说使用图形界面可以在任意坐标处画图，实现起来要比命令行简单很多。本文介绍如何计算结点的横纵坐标，并分别给出命令行和基于QT的图形界面显示
常用数据结构C++实现(3)：二叉树和二叉搜索树
本文包含二叉树数据结构的完整实现以及简单演示，二叉树具有属性查看、连接、删除、遍历等多个接口，还增加直观显示接口。
常用数据结构C++实现(2)：栈和队列
栈和队列都可以看做插入和删除受限制的线性表，通过继承线性表可以实现栈和队列。 Github: https://github.com/yalewoo/cpp-data-structure 栈（Stack） 从Vector派生而来，新增的接口
常用数据结构C++实现(1)：向量和列表
向量和列表都是逻辑上线性数据结构，在物理上向量是顺序存储，列表是链式存储。 向量（Vector）接口描述 概述 内部使用数组封装，支持随机访问 空间复杂度 插入时，若容量不足会翻倍 删除时，目前不会缩小占用内存 构造函数和析构函数 Vect
用两个栈模拟队列，快速获得队列的最大值
队列是一种常用的数据结构。如果按照常规的想法，要获得队列中的最大值，必须遍历队列中的所有元素，时间复杂度为O(n)。怎么降低这个时间呢？求最大元素很容易想到堆。如果建立一个辅助的最大堆（里面存放队列中元素的指针以及值），入队或者出队的时候，