2.1 顺序查找
顺序查找是所有查找方法中最基础也是最简单的一种，一般用于对线性表的查找。它是按照数据在查找表中原有的顺序进行遍历查询的算法。由于需要遍历整个查找表，所顺序查找的时间复杂度为O(n)。
过于简单，此处就不编写代码
2.2 二分查找
二分查找也叫折半查找，是一种适用于顺序存储的查找方法。它是一种效率较高的查找方法，时间复杂度为O(lgn)，但它仅能用于有序表中。也就是说，表中的元素需要按关键字大小有序排列。
代码实现：
nums = [1,2,3,4,6,7,8,9]
left = 0
right = len(nums)-1
mid = (right+left)//2
key = 5
index = -1
while left <= right:
if nums[mid] > key:
right = mid-1
mid = (right+left)//2
elif nums[mid] < key:
left = mid+1
mid = (right + left) // 2
else:
index = mid
break
print(index)
二分查找的思想也很简单，首先定义左指针指向第一个元素，右指针指向最后一个元素，然后救出位于他们中间的下标mid，然后我们判断，小标为mid的值跟要查找的数谁大谁小，如果大于要查找的值，因为列表是有序列表，那么这个值如果存在一定位于nums[mid]的左侧，反之则位于右侧，如果等于则 查找到 直接输出，如果当左右指针重合时还没有找到，那么元素肯定不存在。
2.3 树
树基本概念：
树是一种由n个元素组成的集合，元素之间具有层次关系。
在树中一个节点连接的孩子节点的数量称为度，所有叶子几点的度都为0，所有节点中最大的度称为树的度。
一个节点的层次从根开始定义。根节点是第一层，往下层层递增，树的高度即为树中节点最大层次。
若干棵互不重合的树构成的集合叫做森林。对树中的每一个节点而言，其所有子树的集合就是森林。而树也分有序树和无序数，无序数也叫自由树。
二叉树的基本概念
二叉树是一棵特殊的树，最直观地体现于它的每个节点至少有两个子节点，二叉树是非常实用的一种数据结构，常常用于实现二叉查找树及二叉堆，使数据的存储和搜索效率大大提高。
在二叉树的第i层至多有2^(i-1)个节点。
满二叉树指每一层都达到了最大节点数的二叉树，也就是深度为k并且有 2^(k-1)个几点的二叉树
完全二叉树是指，设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数(即1~h-1层为一个满二叉树)，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
创建二叉树
class Node:
"""节点信息"""
def __init__(self, item):
self.val = item
self.left = None
self.right = None
class Tree:
"""二叉树"""
def __init__(self):
self.root = None
def add(self, item):
node = Node(item)
if self.root is None:
self.root = node
return
queue = [self.root] # 存放需要遍历的节点
while queue: # 列表为空退出循环（个人没发现有用，直接死循环就可以，因为总会找到子树为空的节点，然后return）
cur_node = queue.pop(0) # 从头读取
if cur_node.left is None:
cur_node.left = node
return
else:
queue.append(cur_node.left) # 放到队尾继续遍历
if cur_node.right is None:
cur_node.right = node
return
else:
queue.append(cur_node.right)
首先创建一个用于保存节点信息的类，包含节点的值左节点和右节点的信息，然后创建二叉树，root用于保存根节点的信息，通过add函数向二叉树中添加节点，如果是第一次添加元素，也就是添加第一个节点，那么将其赋予根节点。然后创建一个队列queue，先将根节点放入其中，从队列中取出队的节点开始遍历，如果被遍历的节点左子节点为空，那么就把新添加的节点赋予左子节点，否则就把左子节点放入队列尾部，之后再对其进行遍历，直到遍历到子树为空的节点然后结束遍历。
遍历二叉树
遍历二叉树的方式有三种：前序遍历、中序遍历、后序遍历
前序遍历是先遍历节点本身，然后遍历左子树，然后遍历右子树。中序遍历是先遍历左子树再遍历节点本身，然后遍历右子树。后序遍历是先遍历左子树然后遍历右子树最后再遍历节点本身。
二叉树的层序遍历：
def breadth_travel(self):
if self.root is None:
return
queue = [self.root]
while queue:
cur_node = queue.pop(0)
print(cur_node.val)
if cur_node.left is not None:
queue.append(cur_node.left)
if cur_node.right is not None:
queue.append(cur_node.right)
二叉树的层序遍历实则就是广度优先遍历，其过程与二叉树的创建类似，首先创建一个队列，循环从队列中取出节点，输出节点的值。把非叶子节点的节点放入队列中，之后再遍历。直到队列中不存在非数据，也就是遍历完所有非叶子节点。
二叉树的前序遍历
def preorder(self, node):
if node is None:
return
print(node.val)
self.preorder(node.left)
self.preorder(node.right)
二叉树的中序遍历
def inorder(self, node):
if node is None:
return
self.inorder(node.left)
print(node.val)
self.inorder(node.right)
二叉树的后序遍历
def postorder(self, node):
if node is None:
return
self.postorder(node.left)
self.postorder(node.right)
print(node.val)
完整代码：
class Node:
"""节点信息"""
def __init__(self, item):
self.val = item
self.left = None
self.right = None
class Tree:
"""二叉树"""
def __init__(self):
self.root = None
def add(self, item):
node = Node(item)
if self.root is None:
self.root = node
return
queue = [self.root] # 存放需要遍历的节点
while 1: # 列表为空退出循环
cur_node = queue.pop(0) # 从头读取
if cur_node.left is None:
cur_node.left = node
return
else:
queue.append(cur_node.left) # 放到队尾继续遍历
if cur_node.right is None:
cur_node.right = node
return
else:
queue.append(cur_node.right)
def breadth_travel(self):
if self.root is None:
return
queue = [self.root]
while queue:
cur_node = queue.pop(0)
print(cur_node.val)
if cur_node.left is not None:
queue.append(cur_node.left)
if cur_node.right is not None:
queue.append(cur_node.right)
def preorder(self, node):
if node is None:
return
print(node.val)
self.preorder(node.left)
self.preorder(node.right)
def inorder(self, node):
if node is None:
return
self.inorder(node.left)
print(node.val)
self.inorder(node.right)
def postorder(self, node):
if node is None:
return
self.postorder(node.left)
self.postorder(node.right)
print(node.val)
if __name__ == "__main__":
tree = Tree()
for i in range(11):
tree.add(i)
# tree.breadth_travel()
# tree.preorder(tree.root)
# tree.inorder(tree.root)
# tree.postorder(tree.root)
二叉搜索树
也叫二叉查找树亦称二叉排序树，它或者时一棵空树，或者是具有下列特性的二叉树
- 若它的左子树不为空，则左子树上所有节点的值均小于它的根结构的值
- 若它的右子树不为空，则右子树上所有节点的值均大于它的根结构的值
- 它的左右子树也分别是二叉排序树（递归）
当下我们存在一个序列[70, 105 , 115, 104, 67, 46, 99, 111, 109] 我们构建如下的二叉搜索树
构建过程：
- 我们把列表中的第一个元素70放在根节点位置
- 然后我们取第二个元素，因为第二个元素大于70，所以105放在70的右子树上
- 然后我们取第三个元素，因为第三个元素大于70，放在70的右子树上，又因为115大于105所以放到105的右子树上
- 然后取第四个元素，因为104大于70，放在70的右子树上，又因为104小于105，放在105的左子树上
- 第五个元素67小于70，放到70的左子树上
- 第六个元素46小于70小于67，放在67的左子树上
- 第七个元素99大于70小于105，小于104，放在104的左子树上
- 第八个元素111大于70，大于105，小于115，放在115的左子树上
- 第九个元素109大于70，大于105，小于115，小于111放在111的左子树上
代码创建二叉搜索树
tree = [70, 105 , 115, 104, 67, 46, 99, 111, 109]
class Node:
def __init__(self, item):
self.val = item
self.left = None
self.right = None
class Tree:
def __init__(self):
self.root = Node(tree[0])
for i in range(1, len(tree)):
self.createtree(self.root,tree[i])
def createtree(self, node, code):
if code > node.val:
if node.right is not None:
self.createtree(node.right, code)
else:
node.right = Node(code)
else:
if node.left is not None:
self.createtree(node.left,code)
else:
node.left = Node(code)
if __name__ == "__main__":
t = Tree()
查找对应元素
其中node首先传入根节点，num是需要查找的值
def search(self, node, num):
if node.val < num:
if node.right is None:
return
return self.search(node.right,num)
elif node.val > num:
if node.left is None:
return
return self.search(node.left,num)
else:
return node.val
二叉平衡树
平衡二叉树又称AVL树。它维持二叉树搜索树平衡的根本也在于持续维护这个性质：二叉搜索树中，每个节点的左右子树深度差绝对值不大于1。
LL型
LR型
RR型
RL型
更加复杂情况
下图的调整方法思路为：
- 首先找到导致不平衡的最长路径 A->C->D->F
- 然后我们只看前三个节点，来确定其是上年四个基本类型的哪种类型，RL型
- 然后我们像RL型一样调整，把三个节点的中间节点以及其子节点，看作RL类型的中间节点 也就是把C和E当作 一个节点，把三个节点的最下面的节点及其子节点看作RL类型中的最下面的节点，也就是把D和F当作一个节点
-
然后向RL第一步调整那样调整，CE同时下移，D,F同时上移，这时我们发现，D的右子树F，会与下移之后的CE节点发生碰撞，这时我们只需要比较F与C的大小，E的大小来确定其位置就可以。
做题快速方法（不明白原理，仅适合做题）
- 首先找到导致不平衡的最长路径 31->25->28->26
- 还是看前三个点，31、25、28，找出值位于中间的节点也就是28作为根节点，然后把其它的两个节点根据值的大小分别放在左右两侧，25位于左侧，31位于右侧，构建出第一步的图
- 然后位于两侧节点的左右子树位置不变，16原来位于25左子树，现在仍然在25左子树，47原来在31的右子树现在还在47的右子树，构建出第二步的图
- 最后剩下的29原来位于28的右子树但是冲突，就依次比较放在对应位置，就构建处第三步的图。
红黑树
红黑树是一种自平衡二叉查找树，是计算机科学中用到的一种数据结构。它是一种特殊的二叉查找 树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红或黑
红黑树的特性
- 节点是红色或黑色
- 跟节点是黑色
- 每个叶节点（NIL节点，空节点是黑色）
- 每个红色节点的两个子节点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色节点）
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
红黑树的性质 重点
- 每个节点不是红色就是 黑色
- 不可能有连在一起的红色节点
- 根节点都是黑色
- 每个红色节点的两个子节点都是黑色。叶子节点都是黑色：出度为0满足性质就可以近似的平衡了，不一定要红黑，也可以为其它的。
变换规则
旋转和颜色变换规则：所有插入的点默认是红色
- 变颜色的情况：当前节点的父亲是红色，且它的祖父节点的另一个子节点（叔叔节点）也是红色 ：
- 把父节点设为黑色
- 把叔叔节点也设为黑色
- 把祖父节点（爷爷节点）设为红色
- 把指针定义到祖父节点，设为当前要操作变换的点
- 左旋：当父节点是红色，叔叔是黑色的时候，且当前的节点是右子树。左旋以父节点作为左旋
- 右旋：当父节点是红色，叔叔是黑色的时候，且当前的节点是左子树。右旋
- 把父节点变为黑色
- 把祖父节点变为红色（爷爷）
- 以祖父节点旋转（爷爷）
示例
