红黑树是一种重要的数据结构，它常作为各种系统中关联数组的实现，比如C++STL中的map和set，JDK中的 TreeMap以及Linux内核都用到了红黑树，因此很有必要研究清楚。但在学习红黑树之前，我们最好先理解另 一种树——2-3-4树，它将有助于我们理解红黑树的平衡原理 2-3-4树 2-3-4树是4阶的B-树，根据定义，它具有以下几点性质： 每个结点都是m-结点，其中\(m \in \{2, 3, 4\}\)（m-结点：包含m-1个元素和m个孩子） 所有叶子结点的深度相同 结点之间以及结点内部的元素都是有序的 插入 和二叉搜索树一样，第一步需要找到新元素的位置...
在计算机底层所有的数据都是二进制表示的，在C语言中，基本数据类型大致有以下几种： char short int long float double 定点数的二进制表示 定点数的二进制表示很好理解，计组书上说过有符号整数的二进制表示法大致有四种： 原码 反码 补码 移码 现代计算机基本都采用补码来表示有符号数，而浮点数用到了移码，今天就来具体研究一下 下面的代码用于打印有符号整数的bit位 #include <stdio.h> #include <string.h> void pretty_print(char* str) { ...
二分查找 对于已排序的数组，通过二分查找可以在\(O(log(n))\)的时间复杂度内判断某个元素是否存在，并得到 元素的下标 int binary_search(int arr[], int length, int key) { int low = 0; int high = length - 1; int mid; while (low <= high) { mid = low + (high - low) / 2; if (key < arr[mid]) { high = mid - 1; } else if (ke...
简单排序 选择排序 简单选择排序每次找出最小（最大）的元素，并依次排列 void selection_sort(int arr[], int length) { int min; for (int i = 0; i < length; i++) { min = i; for (int j = i + 1; j < length; j++) { if (arr[j] < arr[min]) { min = j; } } swap(arr[i], arr[min]); } } 简单选...
Question Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999. Solution #include <string> #include <map> using namespace std; map<char, int> table; class Solution { public: Solution() { table['I'] = 1; ...