<p>这一次，小灰把两篇文章做了整合，并且修正了红黑树删除部分的图片错误，感谢大家的指正。</p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-9bbb441dc6a3f5b552dcb0d016dc4470"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-638684b6bf6a5150bd0a64731c2f0084"></p>
<p><strong>————— 第二天 —————</strong></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-512bf8002d3ce72f128b699faf942c9b"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-70287db0e296ac1bd2f78921af45ca4a"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-9502b32c283d2df271e9775fd02c7596"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-6e03071a2e49f20002f8eda66f045a74"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-f8863d2307091893f351f7bf1fa005af"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-ffe9951098e151856cbbf7ed1f3363bb"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-aee74822f660c598392908eab07249ba"></p>
<p>————————————</p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-e662c6dee1f2c5d53c54849ff641f776"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-1d52ff871875937ed1d3beefb920d798"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-06c6c114a60e12b6f9b5843e8de503ba"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-6dde934ec55bd8f727c18c1b289f2eb5"></p>
<p>二叉查找树（BST）具备什么特性呢？</p>
<p>1.<strong>左</strong>子树上所有结点的值均<strong>小于或等于</strong>它的根结点的值。</p>
<p>2.<strong>右</strong>子树上所有结点的值均<strong>大于或等于</strong>它的根结点的值。</p>
<p>3.左、右子树也分别为二叉排序树。</p>
<p>下图中这棵树，就是一颗典型的二叉查找树：</p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-ecc313904c4e9357e34669fe53cc957f"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-e8483b678ab19ff26b5f29d4ee8edc33"></p>
<p>1.查看根结点<strong>9</strong>：</p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-8fd221659e25f2abd2a716e8429d1644"></p>
<p>2.根据二叉查找树左子树小、右子树大的特性，<strong>10 > 9</strong>，因此值为10的结点只可能在根结点的右子树当中，我们查看右孩子结点<strong>13</strong>：</p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-719a66afafc20b70fa506cf49223668a"></p>
<p>3.由于<strong>10 < 13</strong>，因此查看左孩子<strong>11</strong>：</p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-a0ef63092b2319031a797a23cec830a1"></p>
<p>4.由于<strong>10 < 11</strong>，因此查看左孩子<strong>10</strong>，发现10正是要查找的结点：</p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-d6a1b21fa206cd4dc2e062889e102a1f"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-92eb983cafee0b474c6fde672104c77b"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-09e2715dda31ad4837194a55e62eb085"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-015185982bf6f3db663edff4685ede1e"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-0c222d9cc8678d98a20175ce76d6d880"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-d919ed117020115213a8f743de0cc1e7"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-a85b5a86dd704878487810eafa69b2b2"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-e34973b969b3f6a05b8879c82d097c54"></p>
<p>假设初始的二叉查找树只有三个结点，根结点值为9，左孩子值为8，右孩子值为12：</p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-9290a2102ad1a3ea4bb8a1cfd0888c23"></p>
<p>接下来我们依次插入如下五个结点：7,6,5,4,3。依照二叉查找树的特性，结果会变成什么样呢？</p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-d030da06a7aa90618f91987551d7c4a4"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-d60325bd038c3eb18241c9df0c2e7641"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-6baf99e244508f305a53b99f02a8382e"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-61bc93e657ebfb6794500a1b85a78027"></p>
<p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-35283b5b89dc1a6bd45af827d12b4af5"></p>
<p>1.结点是红色或黑色。</p>
<p>2.根结点是黑色。</p>
<p>3.每个叶子结点都是黑色的空结点（NIL |
|
转播
