二叉查找树

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低为O(log(n))。
二叉查找树是基础性数据结构,用于构建更为抽象的数据结构,如集合、多重集、关联数组等。

查找

1
2
3
4
5
6
7
8
9
10
def search(tree, key):
if not tree:
return

if tree.key == key:
return tree
elif key < tree.key:
return search(tree.left, key)
elif key > tree.key:
return search(tree.right, key)

二叉树遍历

定义

二叉树(binary tree)是指树中节点的度不大于2的有序树,树节点的子节点称作左节点和右节点。

可以用类对象简单定义出一个树节点,如下:

1
2
3
4
5
6
class TreeNode:

def __init__(self):
self.left = None
self.right = None
self.value = None

细分

斜树

  • 所有节点都只有左节点的树称为左斜树
  • 所有节点都只有右节点的树称为右斜树

(本质上可以视为链表)

满二叉树/完美二叉树

所有非叶子节点都有两个子节点,且子节点都在同一层次上(即左右子数高度相等)

完全二叉树

所有非叶子节点都有两个子节点,但不要求子节点都在同一层次上

二叉查找树 - BST

二叉查找树是空树满足以下性质的二叉树,

  • 若任意节点的左子树不为空,则左子树上的所有节点的值都小于它根节点的值
  • 若任意节点的右子树不为空,则右子树上的所有节点的值都大于它根节点的值
  • 任意左子树和右子树也都为二叉查找树
  • 节点的值不相等。

红黑树

红黑树是一种自平衡的二叉查找树

  • 每个节点要么是红,要么是黑
  • 根节点是黑的。
  • 叶节点是黑的。
  • 如果一个节点是红,则两个子节点为黑。
  • 对于任意节点,其到叶节点空指针的每天路径都包含相同数目的黑节点。

用法最广:

  • Java ConcurrentHashMap & TreeMap
    C++ STL: map & set
    linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块
    epoll在内核中的实现,用红黑树管理事件块
    nginx中,用红黑树管理timer等

哈夫曼树

又称最优二叉树。是一种带权路径长度最短的二叉树。

一般按如下方式构建,

  • 将左右子树都为空的作为根节点
  • 在森林中选出两棵根节点权值最小的树作为一棵新树的左右子树,且置新树的附加根节点的权值为左右子树的权值之和

B树

B+树

R树

遍历

二叉树的遍历依据遍历行进的方向主要分为深度优先广度优先(层次遍历)。其中,
深度遍历又分为:前序,中序,后序。

四种主要的遍历思想为:

  • 前序遍历(preOrderTraverse):根 -> 左 -> 右
  • 后序遍历(postOderTraverse):左 -> 右 -> 根
  • 中序遍历(inOrderTraverse):左 -> 根 -> 右
  • 层次遍历:上 -> 下,每一层

对下面二叉树进行遍历:

前序遍历

结果:1->2->4->5->7->8->3->6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def pre_order_traverse(node: TreeNode):
res = []
if node is None:
return res

res.append(node.value)

if node.left:
res += pre_order_traverse(node.left)

if node.right:
res += pre_order_traverse(node.right)

return res

使用迭代方式遍历

使用迭代方式进行前序遍历需要借助与结构,原因如下:

整体上,前序遍历的过程是,从根节点开始,先记录自身值,然后始终有限从左节点开始访问。

https://zhuanlan.zhihu.com/p/376166992

后序遍历

结果: 4->7->8->5->2->6->3->1

1
2
3
4
5
6
7
8
9
10
11
12
13
def post_order_traverse(node: TreeNode):
res = []
if node is None:
return res

if node.left:
res += post_order_traverse(node.left)

if node.right:
res += post_order_traverse(node.right)

res.append(node.value)
return res

中序遍历

结果: 4->2->7->5->8->1->6->3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def in_order_traverse(node: TreeNode):
res = []
if node is None:
return res

if node.left:
res += in_order_traverse(node.left)

res.append(node.value)

if node.right:
res += in_order_traverse(node.right)

return res

层次遍历

层次遍历通常不采用递归来实现,一般对借用队列结构,从根节点开始排队进入队列。

结果:1->2->3->4->5->6->7->8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def level_traverse(node: TreeNode):
res = []
if node is None:
return res

from queue import Queue

queue = Queue()
queue.put(node)

while not queue.empty():
node = queue.get()
res.append(node.value)

if node.left:
queue.put(node.left)

if node.right:
queue.put(node.right)

return res