63rabbits

{{pagename}} - {{sitename}}

# 平衡二分探索木（self-balancing binary search tree）


:notebook: Contents

$lsx(depth=1)

---

二分探索木の探索の時間計算量は、木の高さで決まる。
そこで、なるべく木の高さを低く保つようにすることが肝要であり、
そうした木を平衡二分木という。
※ノード数をｎとすると木の高さは最も低いものでもlog\ nとなる。

平衡の度合いはHB(k)で表す。(HB : Height Balance)
ｋ=｜左部分木の高さ ― 右部分木の高さ｜であり平衡因子と呼ばれ、
ｋ値が大きくなるほど平衡性が崩れていると言える。

``` drawio
7VlLc9owEP41PpLxA/M4BpI0h3QmUw5tTx1hC1uNsFxZBOiv78qSH7JNYcCk00zggLWSV6vv25eN5c3Xu08cpfFnFmJquXa4s7w7y3Udb+zDj5TslWQ81YKIk1AvqgQL8htroa2lGxLizFgoGKOCpKYwYEmCA2HIEOdsay5bMWrumqIItwSLANG29CsJRaykE3dcyR8xieJiZ2c0VTNrVCzWJ8liFLJtTat3b3lzzphQV+vdHFMJXoGLuu/hwGxpGMeJOOUGV93wiuhGn03bJfbFYTnbJCGW623Lm21jIvAiRYGc3QK9IIvFmsLIgcsVoXTOKOMwTlgCi2aZ4OwFN4RtO7Xpr5gLvGsCAp6E2RoLvocl2wryoYYxrqFdyJAmOSrvrHCACw1FNyzefwhLMWvbGoA3wKnQcRAXxkXMIpYg+sRYqtH4iYXY66hGG8FMrHAS3soYrVAByQORNuQqARq+/1YffK8P7iQOfjXc1yefMSdwSMy18CDeGdvwQJ9opDMM4hHWq7yJkuHQSBRtUjimSJBXM29chLjTQlwasdBDjVgPJPQH8jFCzyZh+q9IGHWkhxEFs2ZLuIhEfiglWDE4VJ2u0a8NKyYGWY7/LSxw/HRXTRZavshCoDWBUUqZuQGIa5s2XYNSqIn4eILqIfGUyaCWdybXys+T4wlaWk6gZj+hJabPLCOCsASmlkwItoYzFwtuKYnkhGANUKA4p1LZehfJPuZmiTIS3KBgI/APwQlKIrnXLO9r7Bu/kect11v58ttK9jAzyj/aDWpy9empEvga6b1JRo0fx+4gyBn1wdD0g6GjDHnO8DyG3D5qd1fvV2axczPWE16VGWvJC2m2WQqO8Uk5C7ATJstI0x8A0rKqtPxiTcIwJ5pjsA8tc1WytKSMJCLHyJ9Z/p3UBaVOnUE50LW6sJFvMOuM29SOr9WUdXWvFxP7JTfyg1nPnZrMdpS9qzE7PJ5Ua91WQFEG+TAHA3HRFtczaQ5X8TT71/x2tN+qIeF3IFHITm7L9A7PkvJaiLlmeWshrNpHfVf9GfiIoklDj+o5W3pysspTn8bf+K0ax0d6UdsIDOdF+XrRSqX6GQpeovxZ5Wiclq7fDNTyLY/eztKvPA4G8MC+KV9AXeiCA8/0nEHTBdlqleGLvcb/iPoS8uGwEfX2mVHfVHTFqO96WLlO1PP3FvWF6/cR9a7jmaXb7cUjPdfMAe41UsDhNw5ZipLzPabliC+wNFdjW2Mwy5aFxB7IC17IulyplClz3nMDCKnM9KLpiU9tZzy0wbD6L0D5TfWPinf/Bw==
```






# :earth_asia: Map


| same layer | lower layer |
| ---- | ---- |
| $lsx(../, depth=1)     |   $lsx(./, depth=1)    |



07.平衡二分探索木

平衡二分探索木（self-balancing binary search tree）

🌏 Map