数据结构
- 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成
- 简单来说，数据结构就是设计数据以何种方式组织并存储在计算机中
- 比如：列表、集合和字典等都是一种数据结构（他们在内存中存储方式不同）
- N.Wirth: ”程序 = 数据结构 + 算法“
数据结构的分类
- 数据结构按照其逻辑结构可分为线性结构、树结构、图结构
- 线性结构：数据结构中的元素存在一对一的相互关系
- 树结构：数据结构中的元素存在一对多的相互关系
- 图结构：数据结构中的元素存在多对多的相互关系
列表/数组
- 列表(其他语言称数组) 是一种基本数据类型
- 关于列表的问题：
- 列表中的元素是如何存储的？
- 列表的基本操作：按下标查找、插入元素、删除元素.......
- 这些操作的时间复杂度是多少？
- 扩展：Python的列表是如何实现的？
栈
- 栈(Stack)是一个数据集合，可以理解为只能在一端进行插入或删除操作的列表
- 栈的特点：后进先出 LIFO (last-in,first-out)
- 栈的概念：栈顶、栈底
- 栈的基本操作：
- 进栈(压栈)：push
- 出栈：pop
- 取栈顶：gettop
栈的实现
- 使用一般的列表结构即可实现栈
- 进栈：li.append
- 出栈：li.pop
- 取栈顶：li[-1]
栈的应用--括号匹配问题
- 括号匹配问题：给一个字符串，其中包含小括号、中括号、大括号，求该字符串中的括号是否匹配
- 例如：
- ()()[]{} 匹配
- ([{()}]) 匹配
- []( 不匹配
- [(]) 不匹配
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# Date: 24/12/2017
class Stack:
def __init__(self):
self.stack = []
def push(self, element):
self.stack.append(element)
def pop(self):
return self.stack.pop()
def get_top(self):
if len(self.stack) > 0:
return self.stack[-1]
else:
return None
def is_empty(self):
return len(self.stack) == 0
def brace_match(s):
match = {'}':'{', ']':"[", ')':'('}
stack = Stack()
for ch in s:
if ch in {'(','[','{'}:
stack.push(ch)
else: #ch in {'}',']',')'}
if stack.is_empty():
return False
elif stack.get_top() == match[ch]:
stack.pop()
else: # stack.get_top() != match[ch]
return False
if stack.is_empty():
return True
else:
return False
print(brace_match('[{()}(){()}[]({}){}]'))
print(brace_match('[]}'))
栈的应用 -- 函数调用堆栈
- Python的函数调用堆栈
- 栈与递归
队列
- 队列(Queue)是一个数据集合，仅允许在列表的一端进行插入，另一端进行删除
- 进行插入的一端称为队尾(rear)，插入动作称为进队或入队
- 进行删除的一端称为对头(front)，删除动作称为出队
- 队列的性质：先进先出（First-in，First-out）
双向队列
- 双向队列的两端都支持进队和出队操作
- 双向队列的基本操作：
- 队首进队
- 队首出队
- 队尾进队
- 队尾出队
队列的实现
- 队列能否用列表简单实现？为什么？
环形队列
- 环形队列：当队尾指针front==Maxsize+1时，在前进一个位置就自动到0
- 队首指针前进1：front = (front +1) % MaxSize
- 队尾指针前进1：rear = (rear + 1) % MaxSize
- 对空条件：rear == front
- 队满条件：(rear+1) % MaxSIze == front
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# Date: 24/12/2017
class Queue:
def __init__(self, size=100):
self.queue = [0 for _ in range(size)]
self.size = size
self.rear = 0 # 队尾指针
self.front = 0 # 队首指针
def push(self, element):
if not self.is_filled():
self.rear = (self.rear + 1) % self.size
self.queue[self.rear] = element
else:
raise IndexError("Queue is filled.")
def pop(self):
if not self.is_empty():
self.front = (self.front + 1) % self.size
return self.queue[self.front]
else:
raise IndexError("Queue is empty.")
# 判断队空
def is_empty(self):
return self.rear == self.front
# 判断队满
def is_filled(self):
return (self.rear + 1) % self.size == self.front
q = Queue(5)
for i in range(4):
q.push(i)
print(q.pop())
q.push(4)
查看文件最后多少行？
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# Date: 24/12/2017
from collections import deque
# q = deque([1,2,3,4,5], 5)
# q.append(6) # 队尾进队
# print(q.popleft()) # 队首出队
# 用于双向队列
# q.appendleft(1) # 队首进队
# q.pop() # 队尾出队
def tail(n):
with open('test.txt', 'r') as f:
q = deque(f, n)
return q
for line in tail(5):
print(line, end='')
栈和队列的应用 -- 迷宫问题
- 给一个二维列表，表示迷宫(0表示通道，1表示围墙)。给出算法，求一条走出迷宫的路径
栈 -- 深度优先搜索
- 回溯法
- 思路：从一个节点开始，任意找下一个能走的点，当找不到能走的点时，退回上一个点寻找是否有其他方向的点
- 使用栈存储当前路径
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# Date: 24/12/2017
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+1,y),
lambda x,y: (x-1,y),
lambda x,y: (x,y-1),
lambda x,y: (x,y+1)
]
def maze_path(x1,y1,x2,y2):
stack = []
stack.append((x1, y1))
while(len(stack)>0):
curNode = stack[-1] # 当前的节点
if curNode[0] == x2 and curNode[1] == y2:
# 走到终点了
for p in stack:
print(p)
return True
# x,y 四个方向 x-1,y; x+1,y; x,y-1; x,y+1
for dir in dirs:
nextNode = dir(curNode[0], curNode[1])
# 如果下一个节点能走
if maze[nextNode[0]][nextNode[1]] == 0:
stack.append(nextNode)
maze[nextNode[0]][nextNode[1]] = 2 # 2表示为已经走过
break
else:
maze[nextNode[0]][nextNode[1]] = 2
stack.pop()
else:
print("没有路")
return False
maze_path(1,1,8,8)
队列 -- 广度优先搜索
- 思路：从一个节点开始，寻找所有接下来能继续走的点，继续不断寻找，直到找到出口
- 使用队列存储当前正在考虑的节点
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# Date: 24/12/2017
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 + 1, y),
lambda x, y: (x - 1, y),
lambda x, y: (x, y - 1),
lambda x, y: (x, y + 1)
]
def print_r(path):
curNode = path[-1]
realpath = []
while curNode[2] == -1:
realpath.append(curNode[0:2])
curNode = path[curNode[2]]
realpath.append(curNode[0:2]) # 起点
realpath.reverse()
for node in realpath:
print(node)
def maze_path_queue(x1, y1, x2, y2):
queue = deque()
queue.append((x1, y1, -1))
path = []
while len(queue) > 0:
curNode = queue.pop()
path.append(curNode)
if curNode[0] == x2 and curNode[1] == y2:
# 终点
print_r(path)
return True
for dir in dirs:
nextNode = dir(curNode[0], curNode[1])
if maze[nextNode[0]][nextNode[1]] == 0:
queue.append((nextNode[0], nextNode[1], len(path) - 1)) # 后续节点进队，记录哪个节点带他来的
maze[nextNode[0]][nextNode[1]] = 2 # 标记为已经走过
else:
print("没有路")
return False
maze_path_queue(1, 1, 8, 8)
链表
- 链表是由一系列节点组成的元素集合。每个节点包含两部分，数据域item和指向下一个节点的指针next。通过节点之间的相互连接，最终串联成一个链表
class Node(object):
def __init__(self,item):
self.item = item
self.next = None
创建链表
- 头插法
- 尾插法
链表的遍历
链表节点的插入
- p.next = curNode.next
- curNode.next = p
链表节点的删除
- p = curNode.next
- curNode.next = curNode.next.next
- del p
双链表
- 双链表的每个节点有两个指针：一个指向后一个节点，另一个指向前一个节点
- 如何建立双链表？
class Node(object):
def __init__(self,item=None):
self.item = item
self.next = None
self.prior = None
双链表节点的插入
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
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# Date: 2018/3/17
class Node:
def __init__(self, item):
self.item = item
self.next = None
def create_linklist_head(li):
head = Node(li[0])
for element in li[1:]:
node = Node(element)
node.next = head
head = node
return head
def create_linklist_tail(li):
head = Node(li[0])
tail = head
for element in li[1:]:
node = Node(element)
tail.next = node
tail = node
return head
def print_linklist(lk):
while lk:
print(lk.item, end=',')
lk = lk.next
lk = create_linklist_tail([1,2,3,6,8])
print_linklist(lk)
链表 -- 复杂度分析
- 顺序表（列表/数组） 与 链表
- 按元素值查找
- 按下标查找
- 在某元素后插入
- 删除某元素
链表与顺序表
- 链表在插入与删除的操作上明显快于顺序表
- 链表的内存可以更灵活的分配
- 试利用链表重新实现栈和队列
- 链表这种链式存储的数据结构对树和图的结构有很大的启发性
哈希表
- 哈希表一个通过哈希函数来计算数据存储位置的数据结构，通常支持如下操作：
- 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作为自变量，返回元素的存储下标
- 假设有一个长度为7的哈希表，哈希函数h(k)=k%7。元素集合{14,22,3,5}的存储方式如下图
哈希冲突
- 由于哈希表的大小是有限的，而要存储的值的总数量是无限的，因此对于任何哈希函数，都会出现两个不同元素映射到同一个位置上的情况，这种情况叫做哈希冲突
- 比如 h(k)=k%7, h(0) = h(7) = h(14) = ...
解决哈希冲突
开放寻址法
开放寻址法：如果哈希函数返回的位置已经有值，则可以向后探查新的位置来存储这个值
- 线性探查：如果位置i被占用，则探查i+1,i+2.....
- 二次探查：如果位置i被占用，则探查i+1²，i-1²，i+2²，i-2²,....
- 二度哈希：有n个哈希函数，当使用第1个哈希函数h1发生冲突时，则尝试使用h2，h3，...
拉链法
- 拉链法：哈希表每个位置都连接一个链表，当冲突发生时，冲突的元素将被加到该位置链表的最后
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# Date: 2018/3/17
class LinkList:
class Node:
def __init__(self, item=None):
self.item = item
self.next = None
class LinkListIterator:
def __init__(self, node):
self.node = node
def __next__(self):
if self.node:
cur_node = self.node
self.node = cur_node.next
return cur_node.item
else:
raise StopIteration
def __iter__(self):
return self
def __init__(self, iterable=None):
self.head = None
self.tail = None
if iterable:
self.extend(iterable)
def append(self, obj):
s = LinkList.Node(obj)
if not self.head:
self.head = s
self.tail = s
else:
self.tail.next = s
self.tail = s
def extend(self, iterable):
for obj in iterable:
self.append(obj)
def find(self, obj):
for n in self:
if n == obj:
return True
else:
return False
def __iter__(self):
return self.LinkListIterator(self.head)
def __repr__(self):
return "<<"+", ".join(map(str, self))+">>"
# 类似于集合的结构
class HashTable:
def __init__(self, size=101):
self.size = size
self.T = [LinkList() for i in range(self.size)]
def h(self, k):
return k % self.size
def insert(self, k):
i = self.h(k)
if self.find(k):
print("Duplicated Insert.")
else:
self.T[i].append(k)
def find(self, k):
i = self.h(k)
return self.T[i].find(k)
ht = HashTable()
ht.insert(0)
ht.insert(1)
ht.insert(3)
ht.insert(102)
ht.insert(508)
#print(",".join(map(str, ht.T)))
print(ht.find(203))
常见哈希函数
- 除法哈希法：
- h(k) = k % m
- 乘法哈希法：
- h(k) = floor(m(Akey%1))
- 全域哈希法
- ha,b(k) = ((a*key + b) mod p) mod m a,b=1,2,...,p-1
哈希表应用
集合与字典
- 字典与集合都是通过哈希表来实现的
- a = {"name":"alex","age":18,"gender":"Man"}
- 使用哈希表存储字典，通过哈希函数将字典的键映射为下标。假设h("name")=3,h("age")=1,h("gender")=4,则哈希表存储为[None,18,None,"Alex","Man"]
- 如果发生哈希冲突，则通过拉链法或开放寻址法解决
- Python对字典的关键字有什么要求？如何使一个自定义类的对象成为字典的键？
- Python对集合中的元素有什么要求？如何利用集合对大量的对象去重？
二叉树
二叉树的链式存储：将二叉树的节点i定义为一个对象，节点之间通过类似链表的链接方式来连接
节点定义
class BiTreeNode:
def __init__(self,data):
self.data = data
self.lchild = None
self.rchild = None
二叉树的遍历
- 二叉树的遍历方式：
- 前序遍历：EACBDGF
- 中序遍历：ABCDEGF
- 后序遍历：BDCAFGE
- 层次遍历：EAGCFBD
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# Date: 2018/3/24
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
def pre_order(root):
if root:
print(root.data, end=',')
pre_order(root.lchild)
pre_order(root.rchild)
def in_order(root):
if root:
in_order(root.lchild)
print(root.data, end=',')
in_order(root.rchild)
def post_order(root):
if root:
post_order(root.lchild)
post_order(root.rchild)
print(root.data, end=',')
def level_order(root):
queue = deque()
queue.append(root)
while len(queue) > 0: # 只要队不空
node = queue.popleft()
print(node.data, end=',')
if node.lchild:
queue.append(node.lchild)
if node.rchild:
queue.append(node.rchild)
level_order(root)
二叉搜索树
- 二叉搜索树是一棵二叉树且满足性质：设x是二叉树的一个节点。如果y是x左子树的一个节点，那么y.key <= x.key;如果y是x右子树的一个节点，那么y.key>=x.key
- 二叉搜索树的操作：查询、插入、删除
删除操作
- 1、如果要删除的节点是叶子节点：直接删除
- 2、如果要删除的节点只有一个孩子：将此节点的父亲与孩子连接，然后删除该节点
- 3、如果要删除的节点有两个孩子：将其右子树的最小节点(该节点最多有一个右孩子)删除，并替换当前节点
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# Date: 2018/3/24
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, node, val):
if not node:
node = BiTreeNode(val)
elif val < node.data:
node.lchild = self.insert(node.lchild, val)
node.lchild.parent = node
elif val > node.data:
node.rchild = self.insert(node.rchild, val)
node.rchild.parent = node
return node
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
return
elif val > p.data:
if p.rchild:
p = p.rchild
else:
p.rchild = BiTreeNode(val)
p.rchild.parent = p
return
else:
return
def query(self, node, val):
if not node:
return None
if node.data < val:
return self.query(node.rchild, val)
elif node.data > val:
return self.query(node.lchild, val)
else:
return node
def query_no_rec(self, val):
p = self.root
while p:
if p.data < val:
p = p.rchild
elif p.data > val:
p = p.lchild
else:
return p
return None
def pre_order(self, root):
if root:
print(root.data, end=',')
self.pre_order(root.lchild)
self.pre_order(root.rchild)
def in_order(self, root):
if root:
self.in_order(root.lchild)
print(root.data, end=',')
self.in_order(root.rchild)
def post_order(self, root):
if root:
self.post_order(root.lchild)
self.post_order(root.rchild)
print(root.data, end=',')
def __remove_node_1(self, node):
# 情况1：node是叶子节点
if not node.parent:
self.root = None
if node == node.parent.lchild: #node是它父亲的左孩子
node.parent.lchild = None
else: #右孩子
node.parent.rchild = None
def __remove_node_21(self, node):
# 情况2.1：node只有一个左孩子
if not node.parent: # 根节点
self.root = node.lchild
node.lchild.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 __remove_node_22(self, node):
# 情况2.2：node只有一个右孩子
if not node.parent:
self.root = node.rchild
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 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.rchild: # 2.1 只有一个左孩子
self.__remove_node_21(node)
elif not node.lchild: # 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
# 删除min_node
if min_node.rchild:
self.__remove_node_22(min_node)
else:
self.__remove_node_1(min_node)
#
#
# tree = BST([1,4,2,5,3,8,6,9,7])
# tree.in_order(tree.root)
# print("")
#
# tree.delete(4)
# tree.delete(1)
# tree.delete(8)
# tree.in_order(tree.root)
二叉搜索树的效率
- 平均情况下，二叉搜索树进行搜索的时间复杂度为O(nlogn)
- 最坏情况下，二叉搜索树可能非常偏斜
- 解决方案：
- 随机化插入
- AVL树
AVL树
- AVL树：AVL树是一棵自平衡的二叉搜索树
- AVL树具有以下性质：
- 根的左右子树的高度之差的绝对值不能超过1
- 根的左右子树都是平衡二叉树
AVL插入
- 插入一个节点可能会被破坏AVL树的平衡，可以通过旋转操作来进行修正
- 插入一个节点后，只有从插入节点到根节点的路径上的节点的平衡可能被改变。我们需要找出第一个破坏了平衡条件的节点，称之为K。K的两颗子树的高度差2
- 不平衡的出现可能有4种情况
左旋
- 不平衡是由于对K的右孩子的右子树插入导致的：左旋
右旋
- 不平衡是由于对K的左孩子的左子树插入导致的：右旋
右旋-左旋
- 不平衡是由于对K的右孩子的左子树插入导致的：右旋-左旋
左旋-右旋
- 不平衡是由于对K的左孩子的右子树插入导致的：左旋-右旋
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# Date: 2018/3/24
from bst import BiTreeNode, BST
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
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
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:
p.bf = -1
c.bf = 0
elif g.bf < 0:
p.bf = 0
c.bf = 1
else: # 插入的是g
p.bf = 0
c.bf = 0
return g
def rotate_left_right(self, p, c):
g = c.rchild
s2 = g.lchild
c.rchild = s2
if s2:
s2.parent = c
g.lchild = c
c.parent = g
s3 = g.rchild
p.lchild = s3
if s3:
s3.parent = p
g.rchild = p
p.parent = g
# 更新bf
if g.bf < 0:
p.bf = 1
c.bf = 0
elif g.bf > 0:
p.bf = 0
c.bf = -1
else:
p.bf = 0
c.bf = 0
return g
def insert_no_rec(self, val):
# 1. 和BST一样，插入
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 # node 存储的就是插入的节点
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: # val == p.data
return
# 2. 更新balance factor
while node.parent: # node.parent不空
if node.parent.lchild == node: # 传递是从左子树来的，左子树更沉了
#更新node.parent的bf -= 1
if node.parent.bf < 0: # 原来node.parent.bf == -1, 更新后变成-2
# 做旋转
# 看node哪边沉
g = node.parent.parent # 为了连接旋转之后的子树
x = node.parent # 旋转前的子树的根
if node.bf > 0:
n = self.rotate_left_right(node.parent, node)
else:
n = self.rotate_right(node.parent, node)
# 记得：把n和g连起来
elif node.parent.bf > 0: # 原来node.parent.bf = 1，更新之后变成0
node.parent.bf = 0
break
else: # 原来node.parent.bf = 0，更新之后变成-1
node.parent.bf = -1
node = node.parent
continue
else: # 传递是从右子树来的，右子树更沉了
#更新node.parent.bf += 1
if node.parent.bf > 0: # 原来node.parent.bf == 1, 更新后变成2
# 做旋转
# 看node哪边沉
g = node.parent.parent # 为了连接旋转之后的子树
x = node.parent # 旋转前的子树的根
if node.bf < 0: # node.bf = 1
n = self.rotate_right_left(node.parent, node)
else: # node.bf = -1
n = self.rotate_left(node.parent, node)
# 记得连起来
elif node.parent.bf < 0: # 原来node.parent.bf = -1，更新之后变成0
node.parent.bf = 0
break
else: # 原来node.parent.bf = 0，更新之后变成1
node.parent.bf = 1
node = node.parent
continue
# 链接旋转后的子树
n.parent = g
if g: # g不是空
if x == g.lchild:
g.lchild = n
else:
g.rchild = n
break
else:
self.root = n
break
tree = AVLTree([9,8,7,6,5,4,3,2,1])
tree.pre_order(tree.root)
print("")
tree.in_order(tree.root)
二叉搜索树扩展应用 -- B树
- B树(B-Tree): B树是一棵自平衡的多路搜索树。常用于数据库的索引
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# Date: 2018/3/24
class Node:
def __init__(self, name, type='dir'):
self.name = name
self.type = type #"dir" or "file"
self.children = []
self.parent = None
# 链式存储
def __repr__(self):
return self.name
class FileSystemTree:
def __init__(self):
self.root = Node("/")
self.now = self.root
def mkdir(self, name):
# name 以 / 结尾
if name[-1] != "/":
name += "/"
node = Node(name)
self.now.children.append(node)
node.parent = self.now
def ls(self):
return self.now.children
def cd(self, name):
# "/var/python/"
if name[-1] != "/":
name += "/"
if name == "../":
self.now = self.now.parent
return
for child in self.now.children:
if child.name == name:
self.now = child
return
raise ValueError("invalid dir")
tree = FileSystemTree()
tree.mkdir("var/")
tree.mkdir("bin/")
tree.mkdir("usr/")
tree.cd("bin/")
tree.mkdir("python/")
tree.cd("../")
print(tree.ls())