什么是数据结构？
# 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。 简单来说，数据结构就是设计数据以何种方式组织并存储在计算机中。 比如：列表、集合与字典等都是一种数据结构。 N.Wirth: “程序=数据结构+算法”
数据结构的分类？
# 数据结构按照其逻辑结构可分为线性结构、树结构、图结构 线性结构：数据结构中的元素存在一对一的相互关系 树结构：数据结构中的元素存在一对多的相互关系 图结构：数据结构中的元素存在多对多的相互关系
列表
# 列表：在其他编程语言中称为“数组”，是一种基本的数据结构类型。 关于列表的问题： 列表中元素使如何存储的？ 列表提供了哪些基本的操作？ 这些操作的时间复杂度是多少？ 扩展：Python的列表是如何实现的？
列表和数组的区别
列表（线性表） 数组：（其他语言的）连续的一段内存， 大小固定（确定了之后就不能扩展了，系统不支持）， 类型一致 # 存值：内存中直接存的就是数值 列表(python)： # 存值:开20字节长度的内存，存的是对应关系，所以可以是不同类型的数值 取值：先找地址，再通过地址找值 改变数值：另找一块内存用来存值，将指针指向原来的位置 添加：另外复制一块一样大小的内存去存放对应关系。（省了时间，空间有所浪费，动态扩张） 装载因子：<=0.5,动态收缩
栈
# 栈(Stack)是一个数据集合，可以理解为只能在一端进行插入或删除操作的列表。 # 栈的特点：后进先出（last-in, first-out） 栈的概念： 栈顶 栈底 栈的基本操作： 进栈（压栈）：push 出栈：pop 取栈顶：gettop
实例1
# 进栈序列ABC，哪个出栈不可能 CAB """ CBA ABC ACB BCA BAC CAB """ # 进栈顺序为1-n，出栈顺序的个数是（卡特兰数）
栈的Python实现
# 不需要自己定义，使用列表结构即可。 进栈函数：append 出栈函数：pop 查看栈顶函数：li[-1]
栈的应用——括号匹配问题
括号匹配问题：给一个字符串，其中包含小括号、中括号、大括号，求该字符串中的括号是否匹配。
例如：
()()[]{} 匹配
([{()}]) 匹配
[]( 不匹配
[(]) 不匹配
代码实现
def match_brace(s): stack = [] d = {')': '(', ']': '[', '}': '{'} # 右括号为键，左括号为值 for ch in s: if ch in {'(', '[', '{'}: stack.append(ch) # 进栈 elif len(stack) == 0: print("多余的右括号") return False elif d[ch] == stack[-1]: stack.pop() # 出栈 else: print("不匹配") return False if len(stack) == 0: return True else: print("多余的左括号") return False print(match_brace("{(){}[]}")) # 计算器中括号的优先级也是根据栈来做的
队列
# 队列(Queue)是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除。 进行插入的一端称为队尾(rear)，插入动作称为进队或入队 进行删除的一端称为队头(front)，删除动作称为出队 队列的性质：先进先出(First-in, First-out) # 双向队列：队列的两端都允许进行进队和出队操作。
队列的实现
队列能否简单用列表实现？为什么？ 初步设想：列表+两个下标指针 创建一个列表和两个变量，front变量指向队首，rear变量指向队尾。初始时，front和rear都为0。 进队操作：元素写到li[rear]的位置，rear自增1。 出队操作：返回li[front]的元素，front自减1。
队列的实现原理——环形队列
# 环形队列：当队尾指针front == Maxsize + 1时，再前进一个位置就自动到0。 # 实现方式：求余数运算 队首指针前进1：front = (front + 1) % MaxSize 队尾指针前进1：rear = (rear + 1) % MaxSize 队空条件：rear == front 队满条件：(rear + 1) % MaxSize == front
队列的内置模块
使用方法：from collections import deque 创建队列：queue = deque(li) 进队：append 出队：popleft 双向队列队首进队：appendleft 双向队列队尾进队：pop
栈的应用——迷宫问题
# 给一个二维列表，表示迷宫（0表示通道，1表示围墙）。给出算法，求一条走出迷宫的路径。 """ 在一个迷宫节点(x,y)上，可以进行四个方向的探查：maze[x-1][y], maze[x+1][y], maze[x][y-1], maze[x][y+1] 思路：从一个节点开始，任意找下一个能走的点，当找不到能走的点时，退回上一个点寻找是否有其他方向的点。 方法：创建一个空栈，首先将入口位置进栈。当栈不空时循环：获取栈顶元素，寻找下一个可走的相邻方块，如果找不到可走的相邻方块， 说明当前位置是死胡同，进行回溯（就是讲当前位置出栈，看前面的点是否还有别的出路） """
代码实现
maze = [ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 1, 0, 0, 0, 1, 0, 1], [1, 0, 0, 1, 0, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 1, 1, 0, 0, 1], [1, 0, 1, 1, 1, 0, 0, 0, 0, 1], [1, 0, 0, 0, 1, 0, 0, 0, 0, 1], [1, 0, 1, 0, 0, 0, 1, 0, 0, 1], [1, 0, 1, 1, 1, 0, 1, 1, 0, 1], [1, 1, 0, 0, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ] dirs = [ # 四个方向 lambda x, y: (x, y + 1), lambda x, y: (x + 1, y), lambda x, y: (x, y - 1), lambda x, y: (x - 1, y) ] # DFS depth first search def solve_maze_with_stack(x1, y1, x2, y2): stack = [] stack.append((x1, y1)) maze[x1][y1] = 2 while len(stack) > 0: # 栈不空时循环 cur_node = stack[-1] # 查看栈顶元素 if cur_node == (x2, y2): # 到达终点 print(stack) return True for d in dirs: next_node = d(*cur_node) if maze[next_node[0]][next_node[1]] == 0: # 找到了下一个方块 stack.append(next_node) maze[next_node[0]][next_node[1]] = 2 # 标记为已经走过 break else: stack.pop() else: print('没有出路') return False solve_maze_with_stack(1, 1, 8, 8)
队列的应用——迷宫问题
""" 思路：从一个节点开始，寻找所有下面能继续走的点。继续寻找，直到找到出口。 方法：创建一个空队列，将起点位置进队。在队列不为空时循环：出队一次。 如果当前位置为出口，则结束算法；否则找出当前方块的4个相邻方块中可走的方块，全部进队。 """
代码实现
from collections import deque maze = [ [1,1,1,1,1,1,1,1,1,1], [1,0,0,1,0,0,0,1,0,1], [1,0,0,1,0,0,0,1,0,1], [1,0,0,0,0,1,1,0,0,1], [1,0,1,1,1,0,0,0,0,1], [1,0,0,0,1,0,0,0,0,1], [1,0,1,0,0,0,1,0,0,1], [1,0,1,1,1,0,1,1,0,1], [1,1,0,0,0,0,0,0,0,1], [1,1,1,1,1,1,1,1,1,1] ] dirs = [ lambda x,y:(x, y+1), lambda x,y:(x+1, y), lambda x,y:(x, y-1), lambda x, y: (x - 1, y) ] # 广度优先 def solve_maze_with_queue(x1,y1,x2,y2): q=deque() q.append((x1,y1,-1)) maze[x1][y1]=2 path=[] while len(q)>0: cur_node=q.popleft() path.append(cur_node) if cur_node[:2]==(x2,y2): # for i,v in enumerate(path): # print(i,v) real_path=[] i = len(path)-1 while i>=0: real_path.append(path[i][:2]) i= path[i][2] real_path.reverse() print(real_path) return True for d in dirs: next_x,next_y=d(cur_node[0],cur_node[1]) if maze[next_x][next_y]==0: q.append((next_x,next_y,len(path)-1)) maze[next_x][next_y]=2 else: print('没有通路') return False solve_maze_with_queue(1,1,8,8)
链表
# 定义 """ 链表中每一个元素都是一个对象(在内存中不一定是连续的)，每个对象称为一个节点，包含有数据域key和指向下一个节点的指针next。 通过各个节点之间的相互连接，最终串联成一个链表。 """
节点的定义
class Node(object): def __init__(self, data): self.item = data self.next = None
无头节点
a=Node('a') b=Node('b') c=Node('c') a.next=b b.next=c p=a while p: # 遍历链表 print(p.data) p=p.next
有头节点
head = Node(None) a=Node('a') b=Node('b') c=Node('c') head.next=a a.next=b b.next=c p=head.next while p: # 遍历链表 print(p.data) p=p.next
建立链表
链表的遍历
头插法
class Node: def __init__(self, data=None): self.data = data self.next = None # 头插法 带头结点的链表，head.next每次指向的都是刚刚插入的数据，得到的链表是倒序的，如果想插入到第一个数据，需要循环到最后，麻烦 def create_linklist(li): head = Node(None) # 创建一个空的链表 for val in li: p = Node(val) # 创建一个节点p p.next = head.next # 将p.next指向head.next head.next = p # 再将p节点连到头的后边（head.next指向p节点），不写上一步的话，就找不到p节点之前的数据了 return head # 头节点代表着链表 def traverse_linklist(head): # 链表的遍历 p = head.next while p: print(p.data) p = p.next head = create_linklist([1,2,3,4,5]) traverse_linklist(head) # 执行结果[5,4,3,2,1]
尾插法：
class Node: def __init__(self, data=None): self.data = data self.next = None def create_linklist_tail(li): head = Node(None) tail = head # 最开始，尾巴等于头 for val in li: p = Node(val) tail.next = p # 虚拟一个尾部，将尾部的下一个元素指向新节点p tail = p # 更新tail return head def traverse_linklist(head): # 链表的遍历 p = head.next while p: print(p.data) p = p.next head = create_linklist_tail([1,2,3,4,5]) traverse_linklist(head) # 执行结果[1,2,3,4,5]
链表节点的插入和删除
# 插入： p.next = curNode.next curNode.next = p # 删除： p = curNode.next curNode.next = curNode.next.next del p
插入前图示：
插入后图示
双链表
双链表中每个节点有两个指针：一个指向后面节点、一个指向前面节点。
节点定义：
class BiNode: def __init__(self,data): self.data=data self.next=None self.prior=None
双链表插入代码
class BiNode: def __init__(self,data): self.data=data self.next=None self.prior=None def create_bilinklist(li): # 头插法 head=BiNode(None) tail=BiNode(None) head.next=tail # 初始情况 tail.prior=head for val in li: p=BiNode(val) p.next=head.next head.next.prior=p head.next=p p.prior=head return head # 也可以返回tail def create_bilinklist_tail(li): # 尾插法 head=BiNode(None) tail=BiNode(None) head.next=tail # 初始情况 tail.prior=head for val in li: p=BiNode(val) p.next=tail p.prior=tail.prior tail.prior.next=p tail.prior=p return head # 也可以返回tail def traverse_linklist(head): # 链表的遍历 p = head.next while p: print(p.data) p = p.next head = create_bilinklist([1,2,3,4,5]) # 头插法 traverse_linklist(head) # [5,4,3,2,1] head = create_bilinklist([1,2,3,4,5]) # 尾插法 traverse_linklist(head) # [1,2,3,4,5]
双链表节点的插入和删除
# 插入： p.next = curNode.next curNode.next.prior = p p.prior = curNode curNode.next = p # 删除： p = curNode.next curNode.next = p.next p.next.prior = curNode del p
插入前图示
插入后图示
链表-复杂度分析
""" 列表与链表 按元素值查找 都是O(n) 按下标查找 列表 O(1) 链表 O(n) 在某元素后插入 列表 O(n) 链表 O(1) 删除某元素 列表 O(n) 链表 O(1) 链表在插入和删除的操作上明显快于顺序表 链表的内存可以更灵活的分配(空间不够，加一个即可，不用完全连续。next就可以找到) 试利用链表重新实现栈和队列 链表这种链式存储的数据结构对树和图的结构有很大的启发性 """
哈希表
哈希表一个通过哈希函数来计算数据存储位置的数据结构，通常支持如下操作： insert(key, value)：插入键值对(key,value), # 只有键，就是集合 get(key)：如果存在键为key的键值对则返回其value，否则返回空值 delete(key)：删除键为key的键值对
直接寻址表
# 当关键字的全域U比较小时，直接寻址是一种简单而有效的方法。 # 直接寻址技术缺点： 当域U很大时，需要消耗大量内存，很不实际 如果域U很大而实际出现的key很少，则大量空间被浪费 无法处理关键字不是数字的情况
哈希：给一个东西，算出来一个值
直接寻址表：key为k的元素放到k位置上
改进直接寻址表：哈希（Hashing）
构建大小为m的寻址表T
key为k的元素放到h(k)位置上
h(k)是一个函数，其将域U映射到表T[0,1,...,m-1]
哈希表
哈希表（Hash Table，又称为散列表）， 是一种线性表的存储结构。 哈希表由一个直接寻址表和一个哈希函数组成。 哈希函数h(k)将元素关键字k作为自变量，返回元素的存储下标。 简单哈希函数： 除法哈希：h(k) = k mod m 乘法哈希：h(k) = floor(m(kA mod 1)) 0<A<1
假设有一个长度为7的数组，哈希函数h(k)=k mod 7。元素集合{14,22,3,5}的存储方式如下图。
哈希冲突
""" 由于哈希表的大小是有限的，而要存储的值的总数量是无限的，因此对于任何哈希函数，都会出现两个不同元素映射到同一个位置上的情况，这种情况叫做哈希冲突。 比如：h(k)=k mod 7, h(0)=h(7)=h(14)=... """
解决哈希冲突——开放寻址法
开放寻址法：如果哈希函数返回的位置已经有值，则可以向后探查新的位置来存储这个值。 线性探查：如果位置i被占用，则探查i+1, i+2,……, # 装载因子：假如是2/3，不够的话，就动态扩张 # 存在问题：有可能大量的数在一起（空位存在一起，也就是余数相同的数比较多） # 在https://visualgo.net/en/hashtable里面演示 二次探查：如果位置i被占用，则探查i+1的平方,i-1的平方,i+2的平方,i-2的平方,…… 二度哈希：有n个哈希函数，当使用第1个哈希函数h1发生冲突时，则尝试使用h2,h3,……
解决哈希冲突——拉链法
拉链法：哈希表每个位置都连接一个链表，当冲突发生时，冲突的元素将被加到该位置链表的最后。 # 要控制装载因子，可以大于1
哈希表在Python中的应用
# 字典与集合都是通过哈希表来实现的。 在Python中的字典： a = {'name': 'xiaoming', 'age': 18, 'gender': 'Man'} # 键不是数字解决方法：计算机存储都是二进制，把二进制转化为相应的整数即可 使用哈希表存储字典，通过哈希函数将字典的键映射为下标。 假设h(‘name’) = 3, h(‘age’) = 1, h(‘gender’) = 4， 则哈希表存储为[None, 18, None, ’xiaoming’, ‘Man’]
二叉树
存二叉树的链式储：将二叉树的节点定义为一个对象，节点之间通过类似链表的链接方式来连接。
节点定义：
from collections import deque class BiTreeNode: # 节点的定义 def __init__(self, data): self.data = data self.lchild = None self.rchild = None a = BiTreeNode('A') b = BiTreeNode('B') c = BiTreeNode('C') d = BiTreeNode('D') e = BiTreeNode('E') f = BiTreeNode('F') g = BiTreeNode('G') e.lchild = a e.rchild = g a.rchild = c c.lchild = b c.rchild = d g.rchild = f root = e
二叉树的遍历
前序遍历：# 深度优先，从上到下，从左到右，按照进栈的顺序输出（中间，左边，右边） EACBDGF 前序定根E 中序遍历：# 按照出栈的顺序输出（左边，中间，右边） ABCDEGF 中序定左右ABCD GF 后序遍历：# （按照左，右，中间的顺序输出，右孩子完了再输出） BDCAFGE 层次遍历：# 广度优先遍历 EAGCFBD
代码实现
def pre_order(root): # 前序遍历，深度优先，类似于栈（递归和栈是对应的） if root: print("%s" % root.data, end='') pre_order(root.lchild) pre_order(root.rchild) def in_order(root): # 中序遍历 if root: in_order(root.lchild) print("%s" % root.data, end='') in_order(root.rchild) def post_order(root): if root: post_order(root.lchild) post_order(root.rchild) print("%s" % root.data, end='') def level_order(root): # 广度优先遍历 q = deque() q.append(root) while len(q) > 0: p = q.popleft() print(p.data, end='') if p.lchild: q.append(p.lchild) if p.rchild: q.append(p.rchild) level_order(root)
二叉搜索树
二叉搜索树是一颗二叉树且满足性质：
设x是二叉树的一个节点。
如果y是x左子树的一个节点，那么y.key ≤ x.key；
如果y是x右子树的一个节点，那么y.key ≥ x.key.
二叉搜索树的创建
二叉搜索树的遍历（中序序列）
二叉搜索树的查询、插入、删除
二叉搜索树——插入操作
class BiTreeNode: def __init__(self, data): self.data = data self.lchild = None self.rchild = None class BST: def __init__(self, li=None): self.root = None if li: self.root = self.insert(li[0]) for val in li[1:]: self.insert(self.root, val) def insert(self, val): p = self.root if not p: self.root = BiTreeNode(val) return while True: if val < p.data: if p.lchild: p = p.lchild else: p.lchild = BiTreeNode(val) break else: if p.rchild: p = p.rchild else: p.rchild = BiTreeNode(val) break def query_no_rec(val): p = self.root while p: if p.data == val: return True elif p.data > val: p = p.lchild else: p = p.rchild return False def in_order(self, root): if root: self.in_order(root.lchild) print(root.data, end=',') self.in_order(root.rchild) tree = BST() for i in [1, 5, 9, 8, 7, 6, 4, 3, 2]: tree.insert_no_rec(i) tree.in_order(tree.root) # print(tree.query_no_rec(12))
二叉搜索树——删除操作
三种情况 # 1.叶子节点 直接删除 # 2.只有一个孩子 将此节点的父亲与孩子连接，然后删除该节点。 # 3.有两个孩子 将其右子树的最小节点（该节点最多有一个右孩子）删除，并替换当前节点。
代码实现
import random class BiTreeNode: def __init__(self, data): self.data = data self.lchild = None self.rchild = None self.parent = None class BST: def __init__(self, li=None): self.root = None if li: for val in li: self.insert_no_rec(val) def insert(self, root, val): if root is None: root = BiTreeNode(val) elif val < root.data: root.lchild = self.insert(root.lchild, val) root.lchild.parent = root elif val > root.data: root.rchild = self.insert(root.rchild, val) root.rchild.parent = root return root def insert_no_rec(self, val): p = self.root if not p: self.root = BiTreeNode(val) return while True: if val < p.data: if p.lchild: p = p.lchild else: p.lchild = BiTreeNode(val) p.lchild.parent = p break elif val > p.data: if p.rchild: p = p.rchild else: p.rchild = BiTreeNode(val) p.rchild.parent = p break else: return def query(self, root, val): if not root: return None if root.data == val: return root elif root.data > val: return self.query(root.lchild, val) else: return self.query(root.rchild, val) def query_no_rec(self, val): p = self.root while p: if p.data == val: return p elif p.data > val: p = p.lchild else: p = p.rchild return None def in_order(self, root): if root: self.in_order(root.lchild) print(root.data, end=',') self.in_order(root.rchild) def pre_order(self, root): if root: print(root.data, end=',') self.pre_order(root.lchild) self.pre_order(root.rchild) def _remove_node_1(self, node): if not node.parent: # 根节点 self.root = None elif node == node.parent.lchild: # 是父亲的左孩子 node.parent.lchild = None else: # 是父亲的右孩子 node.parent.rchild = None def _remove_node_21(self, node): if not node.parent: # 根节点 self.root = node.rchild self.root.parent = None elif node == node.parent.lchild: node.parent.lchild = node.rchild node.rchild.parent = node.parent else: node.parent.rchild = node.rchild node.rchild.parent = node.parent def _remove_node_22(self, node): if not node.parent: # 根节点 self.root = node.lchild self.root.parent = None elif node == node.parent.lchild: node.parent.lchild = node.lchild node.lchild.parent = node.parent else: node.parent.rchild = node.lchild node.lchild.parent = node.parent def delete(self, val): if self.root: # 不是空树 node = self.query_no_rec(val) if not node: # 如果不存在该节点 return False if not node.lchild and not node.rchild: # 1.叶子节点 self._remove_node_1(node) elif not node.lchild: # 2.1 只有一个右孩子 self._remove_node_21(node) elif not node.rchild: # 2.2 只有一个左孩子 self._remove_node_22(node) else: # 3. 有两个孩子 # 找到右子树中的最小节点 min_node = node.rchild while min_node.lchild: min_node = min_node.lchild node.data = min_node.data # 删除该节点 if min_node.rchild: self._remove_node_21(min_node) else: self._remove_node_1(min_node) # li = [7,0,3,8,6,2,9,4,1,5] # tree = BST(li) # # tree.delete(7) # tree.delete(0) # # # tree.in_order(tree.root) #print(tree.query_no_rec(12))
二叉搜索树的效率
平均情况下，二叉搜索树进行搜索的时间复杂度为O(nlogn)。
最坏情况下，二叉搜索树可能非常偏斜。
解决方案：
随机化插入
AVL树
AVL树（了解）
AVL树：AVL树是一棵自平衡的二叉搜索树。
AVL树具有以下性质：
根的左右子树的高度之差的绝对值不能超过1
根的左右子树都是平衡二叉
AVL树——插入操作
插入一个节点可能会破坏AVL树的平衡，可以通过旋转操作来进行修正。
插入一个节点后，只有从插入节点到根节点的路径上的节点的平衡可能被改变。我们需要找出第一个破坏了平衡条件的节点，称之为K。K的两颗子树的高度差2。
不平衡的出现可能有4种情况
1.不平衡是由于对K的右孩子的右子树插入导致的：左旋
2.不平衡是由于对K的左孩子的左子树插入导致的：右旋
3.不平衡是由于对K的右孩子的左子树插入导致的：右旋-左旋
4.不平衡是由于对K的左孩子的右子树插入导致的：左旋-右旋
代码实现
from bst import BST, BiTreeNode class AVLNode(BiTreeNode): def __init__(self, data): BiTreeNode.__init__(self, data) self.bf = 0 class AVLTree(BST): def __init__(self, li=None): BST.__init__(self, li) def rotate_left(self, p, c): s2 = c.lchild p.rchild = s2 if s2: s2.parent = p c.lchild = p p.parent = c # 更新bf if c.bf == 0: p.bf = 1 c.bf = -1 else: p.bf = 0 c.bf = 0 return c def rotate_right(self, p, c): s2 = c.rchild p.lchild = s2 if s2: s2.parent = p c.rchild = p p.parent = c # update bf if c.bf == 0: p.bf = -1 c.bf = 1 else: p.bf = 0 c.bf = 0 return c def rotate_right_left(self, p, c): g = c.lchild s3 = g.rchild c.lchild = s3 if s3: s3.parent = c g.rchild = c c.parent = g s2 = g.lchild p.rchild = s2 if s2: s2.parent = p g.lchild = p p.parent = g # 更新 bf if g.bf > 0: # g.bf == 1 p.bf = -1 c.bf = 0 elif g.bf == 0: p.bf = 0 c.bf = 0 else: # g.bf == -1 p.bf = 0 c.bf = 1 g.bf = 0 return g def rotate_left_right(self, p, c): g = c.rchild s3 = g.lchild c.rchild = s3 if s3: s3.parent = c g.lchild = c c.parent = g s2 = g.rchild p.lchild = s2 if s2: s2.parent = p g.rchild = p p.parent = g # 更新 bf if g.bf < 0: # g.bf == 1 p.bf = 1 c.bf = 0 elif g.bf == 0: p.bf = 0 c.bf = 0 else: # g.bf == -1 p.bf = 0 c.bf = -1 g.bf = 0 return g def insert_no_rec(self, val): p = self.root if not p: self.root = AVLNode(val) return while True: if val < p.data: if p.lchild: p = p.lchild else: p.lchild = AVLNode(val) p.lchild.parent = p node = p.lchild break elif val > p.data: if p.rchild: p = p.rchild else: p.rchild = AVLNode(val) p.rchild.parent = p node = p.rchild break else: return # 更新bf while node.parent: if node.parent.lchild == node: # 左孩子 if node.parent.bf < 0: # node.parent.bf=-2 左边深 g = node.parent.parent if node.bf > 0: n = self.rotate_left_right(node.parent, node) else: n = self.rotate_right(node.parent, node) elif node.parent.bf > 0: node.parent.bf = 0 break else: node.parent.bf = -1 node = node.parent continue else: # 右孩子 if node.parent.bf > 0: # node.parent.bf=2 右边深 g = node.parent.parent if node.bf < 0: n = self.rotate_right_left(node.parent, node) else: n = self.rotate_left(node.parent, node) elif node.parent.bf < 0: node.parent.bf = 0 break else: node.parent.bf = 1 node = node.parent continue # 旋转结束后 # 连接旋转后的子树的根和原来的树 n.parent = g if g: if node.parent == g.lchild: g.lchild = n else: g.rchild = n break else: self.root = n break tree = AVLTree([7,3,5,4,2,8,6,9,1]) tree.pre_order(tree.root) print("") tree.in_order(tree.root)
二叉搜索树——扩展（了解）
# B树(B-Tree)：B树是一棵自平衡的多路搜索树。常用于数据库的索引。 # 自平衡是9种情况 """ 每个节点放到一个磁盘块上，块和块之间通过链表连起来。做查询，O(logn)的时间复杂度 """
123