树：二叉搜索树，B树，红黑树(附 python实现)
树：二叉搜索树，B树，红黑树
摘要
数据结构是什么？在计算机科学中的定义为：是计算机存储，组织数据的方式。数据结构就意味着接口和封装，数据结构要能够透过程序语言所提供的数据类型，引用以及其他操作实现，一个设计良好的数据结构可以在低的时间和空间复杂度下，解决场景的问题.在这篇文章中我们要着重介绍的是数这种数据结构，它是非常常见的一种数据结构，所以了解它是计算机学生的必修内功。顾名思义这个数据结构叫做树那么它和显示中的树存在着某种联系。我们现实中的树是自底向上逐渐分叉的，一个条主干可以有很多的分支。在计算机科学中的树也是这样的一个节点可以有很多的子节点。这里有点区别的是，为了方便人的阅读，就把根节点放到最上面。
二叉搜索树
二叉树
在给二叉搜索树之前，先来给二叉一个定义：
- 由一系列的节点，这些节点包含链接，这些节点可以为null，或者指向其他节点
- 除了根节点以外，每个节点只能又一个父节点
- 每个节点都只有左右连个链接分别指向自己的左节点，和右节点。
其实在第三点，我们把，左节点，和右节点看作一个新的二叉树，这样的话一些搜素和插入操作就可以很好地使用迭代的算法来使用了，下图为一棵普通的二叉树：
搜索树
二叉搜索树（Binary Search Tree）它是一棵二叉树而且具有以下4个特点：
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点。
下面为python代码的实现
class Node:
def __init__(self,key,left=None,right=None):
self.key = key
self.left = left
self.right = right
class Tree:
def __init__(self):
self.root = None
def add(self, x,listCompare2):
node = Node(x)
if self.root is None:
self.root = node
#print (self.root.key)
return listCompare2
else:
y = self.root
#print (y)
while True:
#print(y.key)
if y.key > node.key:
# print(y)
#listCompare2.append({node.key,y.key})
if y.left == None:
y.left = node
return listCompare2
else:
y = y.left
else:
if y.right == None:
listCompare2.append({y.key,node.key})
y.right = node
return listCompare2
else:
y = y.right
从上面的程序我们可以看出，二叉树的实现（add）操作，它是和数据的排列顺序有关系的，在最好的情况下即二叉树为平衡二叉树的时候：这棵树的高度为：H = log(N);N为这个树的所有节点数。但是在最差的时候即插入时数据是有序的那么在这种情况下树的高度就是：N了
这样二叉树的建立就影响到二叉树的基本操作：查询。它取决于书的结构了。
B树
从上面的二叉搜索树的例子可以看出，它的add和serach操作都是不稳定的，它在最坏的情况下的性能还是很糟糕的。于是人们就想建造出一个即稳定又高效率的数据结构，B树就呼之欲出了。我们都知道，到一棵二叉搜索树为平衡时，它的add和serach都是对数时间的，但是我们在构建树的时候保证树的完美平衡的代价很高，所有为了保证稳定和高效率，我们需要一些灵活性，因此在这里我们允许树中的一个节点保存多个键
在维基百科中是这样定义B树的：是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树（binary search tree），可以拥有多于2个子节点。
2-3树
在这里就挑选最简单的B树来讲解，对于它的定义如下：
2-3查找树或为一棵空树，或由以下的节点组成：
- 2-节点，含有一个键（及其对应的值）和两个链接左链接指向的是2-3树中的键都小于该节点，右链接指向的是2-3树中的键都大于该节点
- 3-节点，含有两个键（及其对于的值）和三个链接，左链接指向的是2-3树中的键都小于该节点，中链接指向的2-3树中键都位于该节点的俩个键之间，右链接指向的2-3树中的键都大于该节点
从这里我们知道2节点就相当于二叉搜索树中的节点，但是它就比二叉搜索树多一个3-节点。下图就是一个简单的2-3树
理解2-3树主要的就是它是怎么自平衡的，自平衡的操作主要就是旋转操作。2-3树的插入大体可以分为两种，
- 向2-节点插入数据
- 向3-节点插入数据
当我们先2-节点上插入数据的时候，这个操作是不会破坏2-3树的特性，因为向2-节点增加字段，相当于把这个2-节点变成3-节点。主要的操作就是向3-节点插入数据时，这个3-节点就变成了4-节点。就破坏了2-3树的特性。这个时候就需要一些操作来保证树的特性。这就是为什么它叫做自平衡树的原因。
上面的第二种情况又可以细分为三种情况：
- case1:插入节点为根节点
- case2:插入节点的父节点为2-节点
- 插入的节点是2-节点的左侧
- 插入的节点在2-节点的右侧
- case3:插入节点的父节点为3-节点
- 插入的节点在3-节点的左侧
- 插入的节点在3-节点的中间
- 插入的节点在3-节点的右侧
下面这个图就是在这三种情况下树在做怎样的一种旋转，其实我们可以验证下，这三种情况下做出来的旋转，之后的状态还是符合红黑树的性质。这个图要好好理解它是红黑树的关键所在（引自《算法》第四版）。
上面的3种case可以包含所有的2-3树的插入操作。从上面的旋转操作都没有使2-3树变称不平衡（存在两个叶子节点s1,s2：他们的深度H(s1) != H(s2)）,这个就是2-3树为自平衡树的原因。
下面的这段代码就是上面6个操作的具体python实现
class Node:
def __init__(self, key1,key2 = None, key3 = None,left=None, right=None, right2 = None,middle = None, p=None):
self.left = left
## 当节点为3-节点时，right为节点的右子树
self.right = right
## 当节点为2-节点时middle为节点的右子树
self.middle = middle
## 这个为临时4-节点的最右子树
self.right2 = right2
self.key1 = key1
self.key2 = key2
## 这个节点是作为一个临时节点它用来存储从3-节点增加的那个节点
self.key3 = key3
self.p = p
## 如果这个键为空的话那么它的父节点为它自己
if key1 == "NIL":
self.p = self
def getChild(self,key):
if key<self.key1:
return self.left
elif self.key2 is None:
return self.middle
elif key < self.key2:
return self.middle
else :
return self.right
class Tree:
def __init__(self):
nil = Node("NIL")
self.root = nil
self.nil = nil
def get(self, key):
if self.root is None:
return None
else:
return self._get(self.root, key)
def _get(self, node, key):
if node is None:
return None
elif node.hasKey(key):
return node
else:
child = node.getChild(key)
return self._get(child, key)
## 直接插入不管fixup
def insert(self , T ,x):
if T.root.key1 == "NIL":
T.root = Node(x)
else:
y = T.root
while y.isLeaf() == False:
print ("y",y.key1)
y = y.getChild(x)
print ("x",y)
if y.key2 is not None:
if x < y.key1:
y.key3 = y.key2
y.key2 = y.key1
y.key1 = x
elif (x>y.key1 and x<y.key2):
y.key3 = y.key2
y.key2 = x
else:
y.key3 = x
print ("y.p",y.p)
self.insertFixUp(T,y)
else:
if x < y.key1:
y.key2 = y.key1
y.key1 = x
else :
y.key2 = x
## 插入的时候把4-节点变成符合2-3树的2/3节点
def insertFixUp(self,T,x):
## case 1
if x.p == None:
print ("x == T.root")
T.root = Node(x.key2)
T.root.left = Node(x.key1)
T.root.left.p = T.root
T.root.middle = Node(x.key3)
T.root.middle.p = T.root
if T.root.left is not None:
T.root.left.left = x.left
if T.root.left.left is not None:
T.root.left.left.p = T.root.left
T.root.left.middle = x.middle
if T.root.left.middle is not None:
T.root.left.middle.p = T.root.left
if T.root.middle is not None:
T.root.middle.left = x.right
if T.root.middle.left is not None :
T.root.middle.left.p = T.root.middle
T.root.middle.middle = x.right2
if T.root.middle.middle is not None :
T.root.middle.middle.p = T.root.middle
return
## case 2
if x.p.key2 is None:
## 在 左侧插入
print ("case2执行")
z = x.p
print(x.key1)
if x is x.p.left:
print ("case2 从左侧插入")
z.key2 = z.key1
z.key1 = x.key2
z.left = Node(x.key1)
z.right = z.middle
z.middle = Node(x.key3)
z.left.p = z
z.middle.p = z
if x.left is not None:
z.left.left = x.left
z.left.left.p = z.left
if x.middle is not None :
z.left.middle = x.middle
z.left.middle.p = z.left
if x.right is not None:
z.middle.left = x.right
z.middle.left.p = z.middle
if x.right2 is not None:
z.middle.middle = x.right2
z.middle.middle.p = z.middle
## 在右侧插入
else:
print("右侧插入执行")
z.key2 = x.key2
z.middle = Node(x.key1)
z.right = Node(x.key3)
z.middle.p = z
z.right.p = z
if x.left is not None:
z.middle.left = x.left
z.middle.left.p = z.middle
if x.middle is not None:
z.middle.middle = x.middle
z.middle.middle.p = z.middle
if x.right is not None :
z.right.left = x.right
z.right.left.p = z.middle
if x.right2 is not None:
z.right.middle = x.right2
z.right.middle.p = z.right
return
if x.p.key2 is not None:
z = x.p
#在左侧插入
if x is z.left:
z.key3 = z.key2
z.key2 = z.key1
z.key1 = x.key2
z.right2 = z.right
z.right2.p = z
z.right = z.middle
z.middle = Node(x.key3)
z.left = Node(x.key2)
z.left.p = z
z.middle.p = z
z.left.left = x.left
z.left.left.p = z.left
z.left.right = x.middle
z.left.right.p = z.left
z.middle.left = x.right
z.middle.left.p = z.middle
z.middle.right = x.right2
z.middle.right.p = z.middle
# 在中间插入
if x is z.middle:
z.key3 = z.key2
z.key2 = x.key2
z.right2 = z.right
z.right2.p = z
z.right = Node(x.key3)
z.right.p = z
z.right.left = x.right
z.right.left.p = z.right
z.right.right = x.right2
z.right.right.p = z.right
z.middle = Node(x.key1)
z.middle.p = z
z.middle.left = x.left
z.middle.left.p = z.middle
z.middle.right = x.middle
z.middle.right.p = z.middle
# 从右侧插入
if x is z.right:
z.key3 = x.key2
z.right2 = Node(x.key3)
z.right2.p = z
z.right2.left = x.right
z.right2.right = x.right2
if z.right2.left is not None:
z.right2.left.p = z.right2
if z.right2.right is not None:
z.right2.right.p = z.right2
z.right = Node(x.key1)
z.right.left = x.left
z.right.right = x.middle
if z.right.left is not None:
z.right.left.p = z.right
if z.right.left is not None:
z.right.right.p = z.right
self.insertFixUp(T,z)
2-3树的一些性质
它的所有叶子结点的高度是一样的：
这点不难得到，我们在上一些中知道，2-3树的所有插入操作都不会使这种情况发生：存在两个节点s1和s2 使得他们的高度：H(s1) !=H(s2)
search和add的操作时间复杂度为O(log(N))
要搜素一个键是否存在，我们先将它和根结点中的节点比较，如果相等，查找命中；否则我们就根据查找的结果找到相应的区间的链接，并递归地继续查找。如果查找到叶子结点还没有查找到就表示这个值在2-3树中不存在，所以查找的时间复杂度和树的高度成线性关系，而树的高度在为 所以2-3树的查找的时间复杂度是对数级别的。同理add操作也是指数级别的；
相近的数大体在同一个或者相近的叶子节点中（这个是B+树，非叶子结点不存储数据的特性了）
这个特性提供B+树作为数据库常用的索引的原因了，这里就不细讲了，大体的逻辑就是，数据库是外部存储器，它不像内存一样，读取一个树的时间复杂度为1，它需要操作磁头，而操作磁头是一个物理过程，很耗费时间。所以希望从外部磁盘中读取数据都是顺序读取的，这样的话就减少了移动磁盘的操作了，加上局部性原理（当一个值被用到的时候，那么它边上的数很大概率都会使用到，所以，磁盘的读写都会使用预读），而且在数据库的应用场景来说，一般执行SQL都是查询相近位置的数据：比如在where条件后面加上大于或者小于号，这也是为什么在Innodb中不使用hash索引的原因，因为hash索引虽然查找单个数据的时间复杂度是O(1)的但是它们之间数据是无序的。在外部存储的索引中B+树是很常见的一种
红黑树
从B树到红黑树
我们上一节学了B树，也讲解了一个B树的例子：2-3树，现在我们把这个放开一点，允许每个节点存放三个数值，那么这个这个时候就会变成2-3-4树了，但是从上面的2-3树我们可以看到，这个B树实现起来很复杂，而且它也没有一般二叉树的简单,从本质上讲：一个红黑树都有对应的2-3-4树。
RED-BLACK TREE 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的，他称之为"对称二叉B树"，它现代的名字是在Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在O( log n) 时间内做查找，插入和删除，这里的n是树中元素的数目1
用途和好处
红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如实时应用（real time application）中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树。
红黑树的定义
为什么一个二叉树，会与B树等价呢？其中比较特别的就是红黑是的定义来约束的：
- 节点是红色或黑色。
- 根结点是黑色的
- 所有叶子节点都是黑色的（叶子结点是NIL节点）
- 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树
这个特性是怎么维持的呢？原因就在于第四个和第五个约束条件。当根结点到一个叶子结点的路径为红黑搭配着前行，那么他的高度最大为2倍的黑色节点的数量；当根节点到某个叶子节点的路径全为黑色节点的时候那么高度最小为1倍的黑色节点树。所以这颗树的最大高度与最小高度相差不会超过两倍。
红黑树的构建
红黑树的构建也是数据插入其中的过程。我们约定插入的数据都是红色的，插入红色的就不会破坏红黑树的第五个特性，下面是插入数据的一些情况：
这里要使用到红黑树的一个特性 当一叶子节点为红色的时候，那么它的兄弟节点只能为红色，或者为空；当一个节点为红色时，那么它的父节点为黑色
以下流程图是以插入的父节点为祖父节点的左节点做例子的，当为右节点，只需把左旋和右旋改变即可
这样一直循环，直到插入的节点为root节点：
from graphviz import Digraph
import time
dot = Digraph(comment='Red Black Tree')
class Node:
def __init__(self, key, left=None, right=None, color=None, p=None):
self.left = left
self.right = right
self.color = color
self.key = key
self.p = p
if key == "NIL":
self.p = self
def LeftRotate(self, T, x):
y = x.right
x.right = y.left
if y.left != T.nil:
y.left.p = x
y.p = x.p
if x.p == T.nil:
T.root = y
elif x == x.p.left:
x.p.left = y
else:
x.p.right = y
y.left = x
x.p = y
def RightRotate(self, T, x):
y = x.left
x.left = y.right
if y.right != T.nil:
y.right.p = x
y.p = x.p
if x.p == T.nil:
T.root = y
elif x == x.p.left:
x.p.left = y
else:
x.p.right = y
y.right = x
x.p = y
def RBInsert(self, T, z):
y = T.nil
x = T.root
while x != T.nil:
y = x
if z.key < x.key:
x = x.left
else:
x = x.right
z.p = y
if y == T.nil:
T.root = z
elif z.key < y.key:
y.left = z
else:
y.right = z
z.left = T.nil
z.right = T.nil
z.color = "RED"
self.RBInsertFixUp(T, z)
def TreeHeight(self, T, z):
if z == T.nil:
return 0
lh = self.TreeHeight(T, z.left)
rh = self.TreeHeight(T, z.right)
if lh > rh:
return lh + 1
return rh + 1
def RBInsertFixUp(self, T, z):
while z.p.color == "RED":
if z.p == z.p.p.left:
y = z.p.p.right
if y.color == "RED":
z.p.color = "BLACK"
y.color = "BLACK"
z.p.p.color = "RED"
z = z.p.p
elif z == z.p.right:
z = z.p
self.LeftRotate(T, z)
z.p.color = "BLACK"
if z.p.p != T.nil:
z.p.p.color = "RED"
self.RightRotate(T, z.p.p)
else:
y = z.p.p.left
if y.color == "RED":
z.p.color = "BLACK"
y.color = "BLACK"
z.p.p.color = "RED"
z = z.p.p
elif z == z.p.left:
z = z.p
self.RightRotate(T, z)
z.p.color = "BLACK"
if z.p.p != T.nil:
z.p.p.color = "RED"
self.LeftRotate(T, z.p.p)
T.root.color = "BLACK"
def RBTransplant(self, T, u, v):
if u.p == T.nil:
T.root = v
elif u == u.p.left:
u.p.left = v
else:
u.p.right = v
v.p = u.p
def TreeMinimum(self, T, z):
if z.left != T.nil:
return self.TreeMinimum(T, z.left)
else:
return z
def RBDeleteFixUp(self, T, x):
while x != T.root and x.color == "BLACK":
if x == x.p.left:
w = x.p.right
if w.color == "RED":
w.color = "BLACK"
x.p.color = "RED"
self.LeftRotate(T, x.p)
w = x.p.right
if w !=T.nil :
if w.left.color == "BLACK" and w.right.color == "BLACK":
w.color = "RED"
x = x.p
elif w.right.color == "BLACK":
w.left.color = "BLACK"
w.color = "RED"
self.RightRotate(T, w)
w = x.p.right
w.color = x.p.color
x.p.color = "BLACK"
w.right.color = "BLACK"
self.LeftRotate(T, x.p)
x = T.root
else:
w = x.p.left
if w.color == "RED":
w.color = "BLACK"
x.p.color = "RED"
self.RightRotate(T, x.p)
w = x.p.left
if w.right.color == "BLACK" and w.left.color == "BLACK":
w.color = "RED"
x = x.p
elif w.left.color == "BLACK":
w.right.color = "BLACK"
w.color = "RED"
self.LeftRotate(T, w)
w = x.p.left
w.color = x.p.color
x.p.color = "BLACK"
w.left.color = "BLACK"
self.RightRotate(T, x.p)
x = T.root
x.color = "BLACK"
def RBDelete(self, T, z):
y = z
yOriginalColor = y.color
if z.left == T.nil:
x = z.right
self.RBTransplant(T, z, z.right)
elif z.right == T.nil:
x = z.left
self.RBTransplant(T, z, z.left)
else:
y = self.TreeMinimum(T, z.right)
yOriginalColor = y.color
x = y.right
if y.p == z:
x.p = y
else:
self.RBTransplant(T, y, y.right)
y.right = z.right
y.right.p = y
self.RBTransplant(T, z, y)
y.left = z.left
y.left.p = y
y.color = z.color
if yOriginalColor == "BLACK":
self.RBDeleteFixUp(T, x)
def InOrderTraversal(self, T, s, A):
if s == T.nil :
return
if s.left != T.nil:
self.InOrderTraversal(T, s.left, A)
A.append(s)
if s.right != T.nil:
self.InOrderTraversal(T, s.right, A)
def printTree(self, T, y, dot):
if(y != T.nil):
dot.node(str(y.key), str(y.key), color=y.color)
if (y.left != T.nil):
dot.node(str(y.left.key), str(y.left.key), color=y.left.color)
dot.edge(str(y.key), str(y.left.key))
dot = self.printTree(T, y.left, dot)
if (y.right != T.nil):
dot.node(str(y.right.key), str(y.right.key), color=y.right.color)
dot.edge(str(y.key), str(y.right.key))
dot = self.printTree(T, y.right, dot)
return dot
class Tree:
def __init__(self):
nil = Node("NIL", color="BLACK")
self.root = nil
self.nil = nil
##os.chdir("/Users/wujiahui/")
T = Tree()
B = [11, 2, 14, 1, 7, 15, 5, 8, 4]
BB = [26]
i = 0
for j in B:
dot = Digraph(comment='Red Black Tree')
T.root.RBInsert(T, Node(j))
dot = T.root.printTree(T, T.root,dot)
dot.render('test-output/'+str(i), view=False)
i = i+ 1
## 把生成的pdf文件转成jpg的文件
from wand.image import Image
def convert_pdf_to_jpg(filename):
pdf_list = []
os.chdir(filename)
for i in os.listdir():
if ".pdf" in i:
pdf_list.append(i)
sorted(pdf_list)
t = 0
print(pdf_list)
for i in pdf_list:
with Image(filename=i) as img :
with img.convert('jpeg') as converted:
converted.save(filename=i.split(".")[0]+'.jpg')
t = t+1
convert_pdf_to_jpg(os.getcwd())
## 把生成的jpg文件生成gif的动图
import matplotlib.pyplot as plt
import imageio,os
images = []
images.append(imageio.imread('8.jpg'))
filenames=sorted((fn for fn in os.listdir('.') if fn.endswith('.jpg')))
for filename in filenames:
images.append(imageio.imread(filename))
imageio.mimsave('gif.gif', images,duration=1,loop=1)
下图就是插入序列[11,2,14,1,7,15,5,8,4]生成的gif图片：
ps:当在高并发的情况下，建议使用skiplist。