※ a<z でもできるけれど、左ノードに追加した方が平衡に戻す操作が少くて済みそうなきがする。
実際に追加すると木は次の図になる。

新しく赤ノード○aが追加された木は、left-leaning 赤黒木の追加条件 6 も含めて赤黒木の条件を全て崩すことなく追加できた。
<?xml-stylesheet type="text/xsl" href="transform.xsl"?><?xml version="1.0" encoding="utf-8"?>
<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns="http://www.w3.org/1999/xhtml">
<xsl:output
method="html"
encoding="utf-8"
omit-xml-declaration="no"
doctype-public="-//W3C//DTD XHTML 1.1//EN"
doctype-system="http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"/>
<xsl:template match="/">
<html xmlns="http://www.w3.org/1999/xhtml" lang="ja">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title></title>
<style type="text/css">
/* @import url("./style.css");*/
* {
font-size:100%;
font-family:Meiryo, MSPGothic, Sans-Serif;
}
p, pre { font-size:85%; }
dd { margin:0; }
</style>
</head>
<body>
<xsl:apply-templates select="node()" />
</body>
</html>
</xsl:template>
<xsl:template match="node()">
<xsl:copy>
<xsl:apply-templates select="@*|node()" />
</xsl:copy>
</xsl:template>
<xsl:template match="@*">
<xsl:copy />
</xsl:template>
</xsl:stylesheet>