【Data Structure】树 - 平衡二叉查找树（Balanced Binary Search Tree） - 有了二叉查找树、AVL 树为啥还需要红黑树？

二叉查找树的缺点

二叉查找树，相信大家都接触过，二叉查找树的特点就是左子树的节点值比父亲节点小，而右子树的节点值比父亲节点大，如图：

基于二叉查找树的这种特点，我们在查找某个节点的时候，可以采取类似于二分查找的思想，快速找到某个节点。n 个节点的二叉查找树，正常的情况下，查找的时间复杂度为 $O(log_2n)$。

之所以说是正常情况下，是因为二叉查找树有可能出现一种极端的情况，例如

这种情况也是满足二叉查找树的条件，然而，此时的二叉查找树已经近似退化为一条链表，这样的二叉查找树的查找时间复杂度顿时变成了 O(n)，可想而知，我们必须不能让这种情况发生，为了解决这个问题，于是我们引申出了平衡二叉树。

...

Posted by Wei on 2019-08-01, Last Modified on 2025-08-11

【Microservices】微服务架构（Microservice Architecture）

Monolithic Architecture

To start explaining the microservice style it’s useful to compare it to the monolithic style: a monolithic application built as a single unit. Enterprise Applications are often built in three main parts: a client-side user interface (consisting of HTML pages and javascript running in a browser on the user’s machine) a database (consisting of many tables inserted into a common, and usually relational, database management system), and a server-side application. The server-side application will handle HTTP requests, execute domain logic, retrieve and update data from the database, and select and populate HTML views to be sent to the browser. This server-side application is a monolith - a single logical executable. Any changes to the system involve building and deploying a new version of the server-side application.

Such a monolithic server is a natural way to approach building such a system. All your logic for handling a request runs in a single process, allowing you to use the basic features of your language to divide up the application into classes, functions, and namespaces. With some care, you can run and test the application on a developer’s laptop, and use a deployment pipeline to ensure that changes are properly tested and deployed into production. You can horizontally scale the monolith by running many instances behind a load-balancer.

以Java为例，所有的功能打包在一个 WAR包里，基本没有外部依赖（除了容器），部署在一个JEE容器（Tomcat，JBoss，WebLogic）里，包含了 DO/DAO，Service，UI等所有逻辑。

...

Posted by Wei on 2019-07-31, Last Modified on 2025-08-11

【Database】读写分离（Read/Write Splitting）

读写分离（Read/Write Splitting）+ 主从复制（Master-slave Replication）

**读写分离（Read/Write Splitting）**的基本思想：让集群中的主数据库负责增（insert）、删（delete）和改（update）事务操作，而集群中的从数据库负责查询操作（select）；并且，数据库后台会自动将因在主数据库中进行的事务操作导致的数据变更，同步到集群中的各个从数据库中。

MySQL的主从复制和MySQL的读写分离两者有着紧密联系，首先部署主从复制，只有主从复制完了，才能在此基础上进行数据的读写分离。简单来说，读写分离就是只在主服务器上写，只在从服务器上读，基本的原理是让主数据库处理事务性查询，而从数据库处理select查询。当业务量非常大时，一台服务器的性能无法满足需求，就可以通过配置主从复制实现写分离来分摊负载，避免因负载太高而造成无法及时响应请求。

读写分离的方式，扩展了数据库对读数据的处理能力，但写能力并没有任何提升。

而且，数据库中单表的数据量是有限制的，当数据库中单表的数据量到达一定程度后，数据库的性能会显著下降。

使用原因

大部分互联网业务读多写少，数据库的读往往最先成为性能瓶颈，如果希望：

线性提升数据库读性能
通过消除读写锁冲突提升数据库写性能

此时可以使用分组架构。

一句话，分组主要解决“数据库读性能瓶颈”问题，在数据库扛不住读的时候，通常读写分离，通过增加从库线性提升系统读性能。

适用场景

读写分离适用与读远大于写的场景，如果只有一台服务器，当select很多时，update和delete会被这些select阻塞，因此并发性能不高。对于写和读比例相近的应用，应该部署双主相互复制。

...

Posted by Wei on 2019-07-31, Last Modified on 2023-02-21

【Data Structure】优先队列（Priority Queue）

Background

队列（Queue）

队列的特点是什么？

聪明的小伙伴们都知道，是先进先出（FIFO）。

...

Posted by Wei on 2019-07-31, Last Modified on 2025-08-11

【Algorithm】排序算法 - 桶排序（Bucket Sort）

Idea

Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm.

思路

设置固定空桶数
将数据放到对应的空桶中
将每个不为空的桶进行排序
拼接不为空的桶中的数据，得到结果

步骤演示

假设一组数据（长度为20）为

[63,157,189,51,101,47,141,121,157,156,194,117,98,139,67,133,181,13,28,109]

现在需要按5个分桶，进行桶排序，实现步骤如下:

找到数组中的最大值194和最小值13，然后根据桶数为5，计算出每个桶中的数据范围为(194-13+1)/5=36.4；
遍历原始数据，以第一个数据63为例，先找到该数据对应的桶序列（Math.floor(63 - 13) / 36.4) =1），然后将该数据放入序列为1的桶中（从0开始算）；
当向同一个桶中第二次插入数据时，判断桶中已存在的数字与新插入的数字的大小，按从左到右，从小打大的顺序插入。如第一个桶已经有了63，再插入51，67后，桶中的排序为(51,63,67) ，一般通过链表来存放桶中数据。
全部数据装桶完毕后，按序列，从小到大合并所有非空的桶（0，1，2，3，4桶）
合并完之后就是排序好的数据了

...

Posted by Wei on 2019-07-30, Last Modified on 2025-08-11

【Algorithm】TopK 问题

有1亿个浮点数，如果找出期中最大的10000个？

排序

最容易想到的方法是将数据全部排序，然后在排序后的集合中进行查找，最快的排序算法的时间复杂度一般为O（nlogn），如快速排序。

但是在32位的机器上，每个float类型占4个字节，1亿个浮点数就要占用400MB的存储空间，对于一些可用内存小于400M的计算机而言，很显然是不能一次将全部数据读入内存进行排序的。其实即使内存能够满足要求（我机器内存都是8GB），该方法也并不高效，因为题目的目的是寻找出最大的10000个数即可，而排序却是将所有的元素都排序了，做了很多的无用功。

局部淘汰法

第二种方法为局部淘汰法，该方法与排序方法类似，用一个容器保存前10000个数，然后将剩余的所有数字——与容器内的最小数字相比，如果所有后续的元素都比容器内的10000个数还小，那么容器内这个10000个数就是最大10000个数。

如果某一后续元素比容器内最小数字大，则删掉容器内最小元素，并将该元素插入容器，最后遍历完这1亿个数，得到的结果容器中保存的数即为最终结果了。此时的时间复杂度为$O（n+m^2）$，其中m为容器的大小，即10000。

分治法

第三种方法是分治法，将1亿个数据分成100份，每份100万个数据，找到每份数据中最大的10000个，最后在剩下的100*10000个数据里面找出最大的10000个。

如果100万数据选择足够理想，那么可以过滤掉1亿数据里面99%的数据。100万个数据里面查找最大的10000个数据的方法如下：用快速排序的方法，将数据分为2堆，如果大的那堆个数N大于10000个，继续对大堆快速排序一次分成2堆，如果大的那堆个数N大于10000个，继续对大堆快速排序一次分成2堆，如果大堆个数N小于10000个，就在小的那堆里面快速排序一次，找第10000-n大的数字；递归以上过程，就可以找到第1w大的数。参考上面的找出第1w大数字，就可以类似的方法找到前10000大数字了。此种方法需要每次的内存空间为10^6*4=4MB，一共需要101次这样的比较。

...

Posted by Wei on 2019-07-30, Last Modified on 2025-08-11

【Java】I/O - 读取数据

Java Scanner 类

java.util.Scanner 是 Java5 的新特征，我们可以通过 Scanner 类来获取用户的输入。

下面是创建 Scanner 对象的基本语法：

Scanner s = new Scanner(System.in);

接下来我们演示一个最简单的数据输入，并通过 Scanner 类的 next() 与 nextLine() 方法获取输入的字符串，在读取前我们一般需要使用 hasNext 与 hasNextLine 判断是否还有输入的数据。

next 方法

public class ScannerDemo {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        // 从键盘接收数据
 
        // next方式接收字符串
        System.out.println("next方式接收：");
        // 判断是否还有输入
        if (scan.hasNext()) {
            String str1 = scan.next();
            System.out.println("输入的数据为：" + str1);
        }
        scan.close();
    }
}

...

Posted by Wei on 2019-07-30, Last Modified on 2025-08-11

【Algorithm】排序算法 - 堆排序（Heap Sort）

堆排序（Heap Sort）

堆排序是利用**二叉堆（Binary Heap）这种数据结构而设计的一种排序算法，堆排序是一种选择排序，**它的最坏，最好，平均时间复杂度均为$O(nlog_2n)$，它是一种不稳定排序。首先简单了解下堆结构。

堆是具有以下性质的完全二叉树：

每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆（Max Heap）；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆（Min Heap）。如下图：

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

堆的存储

一般都用数组来表示堆，i结点的父结点下标就为(i – 1) // 2。它的左右子结点下标分别为2i + 1和 2i + 2。如第0个结点的左右子结点的下标分别为1和2。

...

Posted by Wei on 2019-07-30, Last Modified on 2025-08-11

【Data Structure】优先队列（Priority Queue）- 堆（Heap）- 二叉堆（binary heap）

Background

这里来说明一下满二叉树（full binary tree）的概念与完全二叉树（complete binary tree）的概念。

满二叉树（Full Binary Tree）

A full binary tree is a binary tree in which all of the nodes have either 0 or 2 offspring. In other terms, a full binary tree is a binary tree in which all nodes, except the leaf nodes, have two offspring.

可以看出：满二叉树所有的节点都拥有左孩子，又拥有右孩子。

...

Posted by Wei on 2019-07-29, Last Modified on 2025-08-11

【Algorithm】算法思想 - 动态规划（Dynamic Programming）

Background

介绍动态规划之前先介绍一下分治策略（Divide and Conquer）。

分治策略

将原问题分解为若干个规模较小但类似于原问题的子问题（Divide），「递归」的求解这些子问题（Conquer），然后再合并这些子问题的解来建立原问题的解。

因为在求解大问题时，需要递归的求小问题，因此一般用「递归」的方法实现，即自顶向下。

动态规划（Dynamic Programming）

动态规划其实和分治策略是类似的，也是将一个原问题分解为若干个规模较小的子问题，递归的求解这些子问题，然后合并子问题的解得到原问题的解。区别在于这些子问题会有重叠，一个子问题在求解后，可能会再次求解，于是我们想到将这些子问题的解存储起来，当下次再次求解这个子问题时，直接拿过来就是。其实就是说，动态规划所解决的问题是分治策略所解决问题的一个子集，只是这个子集更适合用动态规划来解决从而得到更小的运行时间。

...

Posted by Wei on 2019-07-29, Last Modified on 2025-08-11

西维蜀黍

【Data Structure】树 - 平衡二叉查找树（Balanced Binary Search Tree） - 有了二叉查找树、AVL 树为啥还需要红黑树？

二叉查找树的缺点

【Microservices】微服务架构（Microservice Architecture）

Monolithic Architecture

【Database】读写分离（Read/Write Splitting）

读写分离（Read/Write Splitting）+ 主从复制（Master-slave Replication）

使用原因

适用场景

【Data Structure】优先队列（Priority Queue）

Background

队列（Queue）

【Algorithm】排序算法 - 桶排序（Bucket Sort）

Idea

思路

步骤演示

【Algorithm】TopK 问题

有1亿个浮点数，如果找出期中最大的10000个？

排序

局部淘汰法

分治法

【Java】I/O - 读取数据

Java Scanner 类

next 方法

【Algorithm】排序算法 - 堆排序（Heap Sort）

堆排序（Heap Sort）

堆的存储

【Data Structure】优先队列（Priority Queue）- 堆（Heap）- 二叉堆（binary heap）

Background

满二叉树（Full Binary Tree）

【Algorithm】算法思想 - 动态规划（Dynamic Programming）

Background

分治策略

动态规划（Dynamic Programming）

FEATURED TAGS

ABOUT ME

FRIENDS