数据结构与算法树（B树，B+树，红黑树待完善）

来源：图艺博知识网

二叉树的介绍

二叉树的节点代码

class TreeNode:
    def __init__(self, value) -> None:
        self.val = value
        self.left = None
        self.right = None

节点的「深度 depth」：从根节点到该节点所经过的边的数量。
节点的「高度 height」：从最远叶节点到该节点所经过的边的数量。

二叉树的类型

「完美二叉树 perfect binary tree」除了最底层外，其余所有层的节点都被完全填满。在完美二叉树中，叶节点的度为 0 ，其余所有节点的度都为 2 ；若树高度为 ℎ ，则节点总数为 2ⁿ⁺¹−1 ，呈现标准的指数级关系，反映了自然界中常见的细胞现象。
「完全二叉树 complete binary tree」只有最底层的节点未被填满，且最底层节点尽量靠左填充。
「完满二叉树 full binary tree」除了叶节点之外，其余所有节点都有两个子节点。
「平衡二叉树 balanced binary tree」中任意节点的左子树和右子树的高度之差的绝对值不超过 1 。

链表二叉树的遍历

层序遍历(广度优先遍历breadth‑first traversal) BFT/BFS

从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。

from collections import deque

def level_order(root):

    queue = deque()

    queue.append(root)

  

    res = []

    while queue:

        node = queue.popleft()

        res.append(node.val)

        if node.left is not None:

            queue.append(node.left)

        if node.right is not None:

            queue.append(node.right)

    return res

前序、中序、后序遍历（深度优先遍历）DFT/DFS

前序:访问优先级：根节点 -> 左子树 -> 右子树
中序:访问优先级：左子树 -> 根节点 -> 右子树
后序:访问优先级：左子树 -> 右子树 -> 根节点

class TreeOrder:

    def __init__(self) -> None:

        self.res = []

  

    def pre_order_need(self, root):

        if root is None:

            return None

        self.res.append(root.val)

        self.pre_order_need(root.left)

        self.pre_order_need(root.right)

  

    def pre_order(self, root):

        self.res = []

        self.pre_order_need(root)

  

    def in_order_need(self, root):

        if root is None:

            return None

        self.in_order_need(root.left)

        self.res.append(root.val)

        self.in_order_need(root.right)

  

    def in_order(self, root):

        self.res = []

        self.in_order_need(root)

  

    def post_order_need(self, root):

        if root is None:

            return None

        self.post_order_need(root.left)

        self.post_order_need(root.right)

        self.res.append(root.val)

  

    def post_order(self, root):

        self.res = []

        self.post_order_need(root)

复杂度分析

时间复杂度 𝑂(𝑛) ：所有节点被访问一次，使用 𝑂(𝑛) 时间。
空间复杂度 𝑂(𝑛) ：在最差情况下，即树退化为链表时，递归深度达到 𝑛 ，系统占用 𝑂(𝑛) 栈帧空间。

数组二叉树的构造

class ArrayTree:

    def __init__(self, arr) -> None:

        self.__tree = list(arr)

        self.res = []

  

    def size(self):

        return len(self.__tree)

    def val(self, ix):

        if ix < 0 or ix >= self.size():

            return None

        else:

            return self.__tree[ix]

    def left(self, ix):

        return 2*ix + 1

  

    def right(self, ix):

        return 2*ix + 2

    def parent(self, ix):

        return (ix -1)//2

    def level_order(self):

        self.res = []

        for i in range(self.size()):

            if self.val(i) is not None:

                self.res.append(self.val(i))

        return self.res

    def __dfs(self, ix, order):

        if self.val(ix) is None:

            return None

        if order == 'pre':

            self.res.append(self.val(ix))

        self.__dfs(self.left(ix), order)

        if order == 'in':

            self.res.append(self.val(ix))

        self.__dfs(self.right(ix), order)

        if order == 'post':

            self.res.append(self.val(ix))

  

    def pre_order(self):

        self.res = []

        self.__dfs(0, order='pre')

        return self.res

    def in_order(self):

        self.res = []

        self.__dfs(0, order='in')

        return self.res

    def post_order(self):

        self.res = []

        self.__dfs(0, order='post')

        return self.res

lst = [1,2,3,4,None,6,7,8,9,None,None,12,None,None,15]

tree = ArrayTree(lst)

tree.level_order()
tree.pre_order()
tree.in_order()
tree.post_order()

数组二叉树的优缺点

二叉树的数组表示主要有以下优点。

数组存储在连续的内存空间中，对缓存友好，访问与遍历速度较快。
不需要存储指针，比较节省空间。
允许随机访问节点。
然而，数组表示也存在一些局限性。
数组存储需要连续内存空间，因此不适合存储数据量过大的树。
增删节点需要通过数组插入与删除操作实现，效率较低。
当二叉树中存在大量 None 时，数组中包含的节点数据比重较低，空间利用率较低。

二叉搜索树

「二叉搜索树 binary search tree」满足以下条件：

二叉搜索树的构造

二叉搜索树的中序遍历序列是升序的。在二叉搜索树中获取有序数据仅需 𝑂(𝑛)时间

class binary_search_tree:

    def __init__(self, root) -> None:

        self.__root = root

        self.res = []

    def search(self, num):

        cur = self.__root

        while cur is not None:

            if cur.val == num:

                return cur

            elif cur.val < num:

                cur = cur.right

            elif cur.val > num:

                cur = cur.left

        else:

            return None

    def insert(self, num):

        node = TreeNode(num)

        if self.__root is None:

            self.__root = node

        pre = None

        cur = self.__root

        while cur is not None:

            if cur.val == num:

                return ValueError('值重复')

            elif cur.val < num:

                pre = cur

                cur = cur.right

            elif cur.val > num:

                pre = cur

                cur = cur.left

        if pre.val < num:

            pre.right = node

        else:

            pre.left = node

  

    def remove(self, num):

        cur = self.__root

        pre = None

        while cur is not None:

            if cur.val == num:

                break

            elif cur.val < num:

                pre = cur

                cur = cur.right

            elif cur.val > num:

                pre = cur

                cur = cur.left

        else:

            raise ValueError('没有这个值')

        if cur.left is None or cur.right is None:

            child = cur.left or cur.right

            if pre is None:

                self.__root = None

            if pre.left == cur:

                pre.left = child

            elif pre.right == cur:

                pre.right = child

        else:

            tem = cur.left

            while tem.right is not None:

                tem = tem.right

            self.remove(tem.val)

            cur.val = tem.val

  
  
  

    def __dfs(self, node, order):

        if node is None:

            return None

        if order == 'pre':

            self.res.append(node.val)

        self.__dfs(node.left, order)

        if order == 'in':

            self.res.append(node.val)

        self.__dfs(node.right, order)

        if order == 'post':

            self.res.append(node.val)

  

    def pre_order(self):

        self.res = []

        self.__dfs(self.__root, 'pre')

        return self.res

    def in_order(self):

        self.res = []

        self.__dfs(self.__root, 'in')

        return self.res

    def post_order(self):

        self.res = []

        self.__dfs(self.__root, 'post')

        return self.res


node_1 = TreeNode(8)

node_2 = TreeNode(4)

node_3 = TreeNode(12)

node_4 = TreeNode(3)

node_5 = TreeNode(6)

node_6 = TreeNode(10)

node_7 = TreeNode(14)

  

node_1.left = node_2

node_1.right = node_3

node_2.left = node_4

node_2.right = node_5

node_3.left = node_6

node_3.right = node_7

二叉搜索树的效率

给定一组数据，我们考虑使用数组或二叉搜索树存储。观察表 7‑2 ，二叉搜索树的各项操作的时间复杂度都是对数阶，具有稳定且高效的性能表现。只有在高频添加、低频查找删除的数据适用场景下，数组比二叉搜索树的效率更高。在理想情况下，二叉搜索树是“平衡”的，这样就可以在 log 𝑛 轮循环内查找任意节点。然而，如果我们在二叉搜索树中不断地插入和删除节点，可能导致二叉树退化为图 7‑23 所示的链表，这时各种操作的时间复杂度也会退化为 𝑂(𝑛) 。

AVL树

class AVL:

    def __init__(self, root) -> None:

        self.root = root

        self.res = []

  
  

    def height(self, node):

        if node is not None:

            return node.height

        else:

            return -1

    def __update_height(self, node):

        node.height = max(node.left.height, node.right.height) + 1

  

    def balance_factor(self, node):

        if node is None:

            return 0

        else:

            return self.height(node.left) - self.height(node.right)

    def __right_rotate(self, node):

        child = node.left

        grand_child = child.right

  

        child.right = node

        node.left = grand_child

  

        self.__update_height(node)

        self.__update_height(child)

        return child

    def __left_rotate(self, node):

        child = node.right

        grand_child = child.left

  

        child.left = node

        node.right = grand_child

  

        self.__update_height(node)

        self.__update_height(child)

        return child

    def __rotate(self, node):

        balance_factor = self.balance_factor(node)

        if balance_factor > 1:

            if self.balance_factor(node.left) >= 0:

                return self.__right_rotate(node)

            else:

                node.left = self.__left_rotate(node.left)

                return self.__right_rotate(node)

        elif balance_factor < -1:

            if self.balance_factor(node.right) <= 0:

                return self.__left_rotate(node)

            else:

                node.right = self.__right_rotate(node.right)

                return self.__left_rotate(node)

        return node

    def __insert_helper(self, node, val):

        if node is None:

            return TreeNode(val)

        if val < node.val:

            node.left = self.__insert_helper(node.left, val)

        elif val > node.val:

            node.right = self.__insert_helper(node.right, val)

        else:

            return node

        self.__update_height(node)

        return self.__rotate(node)

    def insert(self, val):

        self.root = self.__insert_helper(self.root, val)

  

    def __remove_helper(self, node, val):

        if node is None:

            return None

        if val < node.val:

            node.left = self.__remove_helper(node.left, val)

        elif val > node.val:

            node.right = self.__remove_helper(node.right, val)

        else:

            if node.left is None or node.right is None:

                child = node.left or node.right

                if child is None:

                    return None

                else:

                    node = child

            else:

                temp = node.left

                while temp.right:

                    temp = temp.right

                node.left = self.__remove_helper(node.left, temp.val)

                node.val = temp.val

        self.__update_height(node)

        return self.__rotate(node)

    def remove(self, val):

        self.root = self.__remove_helper(self.root, val)

  

    def __dfs(self, node, order):

        if node is None:

            return None

        if order == 'pre':

            self.res.append(node.val)

        self.__dfs(node.left, order)

        if order == 'in':

            self.res.append(node.val)

        self.__dfs(node.right, order)

        if order == 'post':

            self.res.append(node.val)

  

    def pre_order(self):

        self.res = []

        self.__dfs(self.root, 'pre')

        return self.res

    def in_order(self):

        self.res = []

        self.__dfs(self.root, 'in')

        return self.res

    def post_order(self):

        self.res = []

        self.__dfs(self.root, 'post')

        return self.res

    def search(self, value):

        cur = self.root

        while cur:

            if cur.val == value:

                break

            elif cur.val < value:

                cur = cur.right

            elif cur.val > value:

                cur = cur.left

        else:

            raise ValueError('这个值不存在')

        return cur

重点回顾

二叉树是一种非线性数据结构，体现“一分为二”的分治逻辑。每个二叉树节点包含一个值以及两个指针，分别指向其左子节点和右子节点。
对于二叉树中的某个节点，其左（右）子节点及其以下形成的树被称为该节点的左（右）子树。
二叉树的相关术语包括根节点、叶节点、层、度、边、高度和深度等。
二叉树的初始化、节点插入和节点删除操作与链表操作方法类似。
常见的二叉树类型有完美二叉树、完全二叉树、满二叉树和平衡二叉树。完美二叉树是最理想的状态，而链表是退化后的最差状态。
二叉树可以用数组表示，方法是将节点值和空位按层序遍历顺序排列，并根据父节点与子节点之间的索引映射关系来实现指针。
二叉树的层序遍历是一种广度优先搜索方法，它体现了“一圈一圈向外”的分层遍历方式，通常通过队列来实现。
前序、中序、后序遍历皆属于深度优先搜索，它们体现了“走到尽头，再回头继续”的回溯遍历方式，通常使用递归来实现。
二叉搜索树是一种高效的元素查找数据结构，其查找、插入和删除操作的时间复杂度均为 𝑂(log 𝑛) 。
当二叉搜索树退化为链表时，各项时间复杂度会劣化至 𝑂(𝑛) 。
AVL 树，也称为平衡二叉搜索树，它通过旋转操作，确保在不断插入和删除节点后，树仍然保持平衡。
AVL 树的旋转操作包括右旋、左旋、先右旋再左旋、先左旋再右旋。在插入或删除节点后，AVL 树会从底向顶执行旋转操作，使树重新恢复平衡。

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

数据结构与算法 树（B树，B+树，红黑树待完善）